>> 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.