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

You are not logged in.

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

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

So the Fibonacci sequence F satisfies

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


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


Board footer

Powered by FluxBB