In my previous posting, I forgot to mention something...
Vincent Johns wrote: > Will wrote: > >> William Elliot wrote: >> >> >>> Subject : Re: Functional equation >>> >>> On Mon, 23 May 2005, Will wrote: >>> >>> >>>> A function f(x) has the following properties: >>>> 1) f(1) = 1 >>>> 2) f(2x) = 4f(x) + 6 >>>> 3) f(x+2) = f(x) + 12x + 12 >>>> >>> >>> f(2x + 2) = 4f(x + 1) + 6 >>> f(2x + 2) = f(2x) + 12*2x + 12 = 4f(x) + 24x + 18 >>> f(x + 1) = f(x) + 6x + 3 >>> >>> f(x + 1) - f(x) = 6x + 3 >>> f(x) = 3x(x - 1) + 3x + c = 3x^2 + c >> >> ... >> >> I understand your argument up to and including the line: >> "f(x + 1) - f(x) = 6x + 3" >> >> But how do you conclude that: >> "f(x) = 3x(x - 1) + 3x + c = 3x^2 + c" ? >> [...] > > First differences: > Delta(x) := f(x + 1) - f(x) = 6x + 3 > > Second differences: > Delta^2(x) := Delta(x + 1) - Delta(x) > = (6*(x + 1) + 3) - (6*x + 3) > = (6*x + 9) - (6*x + 3) > = 6 > and since the 2nd difference is a constant value, we know that the > coefficient of the x^2 term is this divided by 2!, in other words = 6/2! > = 6/2 = 3, so the polynomial fitting the points has the form > p(x) := 3*x^2 + b*x + c [...]
(Incidentally, I used some sloppy notation -- instead of "Delta(x)" I should have written "Delta(f(x))", since I'm interested in the differences of the values of the function, not of x. Sorry.)
From here, instead of using Newton's polynomial-fitting formula as I suggested in my earlier post, you could (knowing that 3*x^2 is the highest term) just subtract off the 3*x^2 values, leaving something of the form
q(x) := b*x + c
which you can analyze the same way.
First, subtract 3*x^2 from each term, then compute another table of differences:
Aha! (It's probably kind of obvious how this function behaves, but I'll show the steps for the sake of illustration).
The coefficient of the linear term (value of b in p(x) = 3*x^2 + b*x + c) is the constant value of Delta(q(x)) divided by 1!, so in this case
b = 0/1! = 0/1 = 0
and if it weren't zero, for the next step we could subtract b*x from the values of (f(x) - 3*x^2) to find the constant term, c. But, since subtracting zero won't change the values much, it's probably apparent that c = -2.
So the (unique) polynomial fitting these values is