|
|
Re: Which Polynomial?
Posted:
Jul 31, 2005 1:53 PM
|
|
>> No, no, Kirby. Look at the sequence f1^n+f2^n. Every
>> recursively-generated sequence has a generating
>> polynomial. f1 and f2 are the two roots.
>
> No really, the usual thing is to approach phi using two successive terms of
> the sequence. That's not to say your exercise is irrelevant though --
> although the sequence I'm getting from your instructions isn't
> 0,1,1,2,3,5,8,13... but 1,3,4,7,11,18,29...
>
f[n] = q^n satisfies the Fibonacci recurrence relation f[n] - f[n-1] -
f[n-2] = 0 (n=0,1,2,...) iff q^n - q^(n-1) - q^(n-2) = 0 (with q non zero)
that is, q^2 - q - 1 = 0.
The roots are then q(1) = (1+SQRT5)/2 and q(2) = (1-SQRT5)/2 both solutions
of the recurrence relation.
Since the relation is linear and homogeneous, the general solution is f[n] =
c(1)q(1)^n + c(2)q(2)^n for any choice of c(1) and c(2). In order to satisfy
the (two) initial values f(0) = 0 and f(1) = 1, we determine c(1) = 1/SQRT5
and c(2) = -1/SQRT5 which gives the correct formula for f[n] corresponding
to the initial values 0 and 1.
JP
|
|
