Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2014-03-18 12:32:17

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

Offline