Consider the set

of all sequences satisfying the linear recursionfor some fixed .

Define addition and scalar multiplication on **V** by:

it is easy to see that

Now suppose

for some constant r. The recursion formula becomes

.

Divide by r^(n-k) to get

.

In other words, if r is a solution to this polynomial equation, then

.

Assuming that all the roots of the polynomial are unique, then we have the needed k independent sequences, so any sequence X in **V** is given by

for appropriate constants A_i, where the r_i are the roots. The constants A_i can be determined by solving a system of linear equations for the first k values of X.

For example, consider the a sequence that *just possibly* you may have heard of before:

, with .The polynomial equation that results from this recursion is

with solutions and .

So the Fibonacci sequence *F* satisfies

Solving, ,

So we have Binet's formula:

.Perhaps part of the reason this appeals to me is that I was able to figure it out myself. I had seen Binet's formula many times, but never a derivation, so I finally worked out how to prove it. What is really nice is that it generalizes. Any linear recursion sequence has a similar formula (though there is a twist thrown in if the polynomial has roots of multiplicity greater than one).

As a challenge (I do know the answer), what has to change if the polynomial does have a double or higher order root? Experimenting with the recursion

can be instructive.]]>