Just want to share one of my favorite bits of mathematics.
Consider the setof all sequences satisfying the linear recursion
Define addition and scalar multiplication on V by:
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 example, consider the a sequence that *just possibly* you may have heard of before:, with .
So the Fibonacci sequence F satisfiesfor 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 recursioncan 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