Math Is Fun Forum

eigenguy

Member

Registered: 2014-03-18

Posts: 78

Recursion formulas

Just want to share one of my favorite bits of mathematics.

Consider the set

of all sequences

satisfying the linear recursion

for some fixed

.

Define addition and scalar multiplication on V by:

it is easy to see that V is a vector space. It should also be obvious that each sequence X is determined by its first k values, so V is of dimension k. So if we can find k independent sequences in V, then all the other sequences are just linear combinations of them.

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

for some A, B. To find these values, note that

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.

---

"Having thus refreshed ourselves in the oasis of a proof, we now turn again into the desert of definitions." - Bröcker & Jänich