The neat trick
The core of the solution follows from a neat trick: replace the subscripts with superscripts. This is very powerful trick. Let’s see that in action.
We gamble and hope some of the solutions are of the following simple form: [rn | n = 1, 2, ...] = (r, r2, r3, ...) , where r is a to be determined (possibly complex) number.
Our claim is: if the number r is a solution to the polynomial equation (in x )
x2 = x + 1
then v = [rn | n = 1, 2, ...] satisfies
v n+2 = v n+1 + v n for n = 1, 2, ...
.
The polynomial is called “the characteristic polynomial” of the linear recurrence checks.
The “trick” to this is: if x = r is a root of, or satisfies, x2 = x + 1 , then it also satisfies xn+2 = xn+1 + xn (which is equivalent to xn x2 = xn x + xn 1 ) for all n ≥ 0 . So rn+2 = rn+1 + rn for all n ≥ 0 which is exactly the claim v = [rn | n = 1, 2, ...] is a solution to all of the subscripted v -checks. It pays to think of the characteristic polynomial p(x) as shorthand for the family of “check polynomials” xn p(x) for n = 0, 1, 2, ... . However, for some problems we will need to appeal directly to the family of check polynomials.
In our case, the roots, or solutions, to this polynomial equation are the roots x2 - x - 1 = 0 . By the quadratic formula:
r 1 = (1 + sqrt(5))/2
r 2 = (1 - sqrt(5))/2