Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$

Somebody has any idea how to go about proving this result? I know a proof by mathematical induction, but that, in my opinion, will be a verification of this result only. I tried to find through the net, but in vain, if someone has some link or pointer to its proof, please provide, I'll appreciate that.

Thanks a lot!

share|improve this question
    
Eigendecompose the matrix being powered, take the $n$-th power of the resulting diagonal matrix, use Binet... something like that. –  J. M. Sep 5 '11 at 13:23
1  
What, in your opinion, is the difference between a verification and a proof? You might be interested in this post: math.stackexchange.com/questions/61541/…. –  joriki Sep 5 '11 at 13:24
    
IMHO a proof is to be preferred over a verification. Isn't verification mostly like checking an interesting example case by other means? You can eigendecompose the l.h.s., but isn't that just a way of deriving Binet's formula? Induction and recursion go hand in hand, and Fibonacci sequence more often than not screams for a proof by induction. –  Jyrki Lahtonen Sep 5 '11 at 13:41
2  
If I understand correctly, the question is: "how can one come up with that formula? Once it's there, it's easy enough to check it by induction but how does one find such an identity?" –  t.b. Sep 5 '11 at 13:46
3  
It's still unclear to me what the OP is looking for. What exactly is wrong with a proof by induction? You could also remark that if $a_{n+1} = a_n + a_{n-1}$ for some sequence $(a_n)$, then $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ maps a matrix $\begin{pmatrix}a_n&a_{n-1}\\a_{n-1}&a_{n-2}\end{pmatrix}$ to $\begin{pmatrix}a_{n+1}&a_n\\a_n&a_{n-1}\end{pmatrix}$. But again that is very similar to the proof by induction. –  TMM Sep 5 '11 at 14:08

3 Answers 3

up vote 4 down vote accepted

(I'm assuming here that what the OP really wants is to know how one would ever get the idea to try to prove this. He already has a proof by induction, which is a perfectly valid and respectable proof method; you won't get anything proofier than that, except perhaps methods that hide the induction within a general theorem).

One way to invent this relation is to start from the following fairly simple algorithm for computing Fibonacci numbers:

  • Start by setting $a=0$, $b=1$
  • Repeat the following until you reach the $F_n$ you want:
    • (Invariant: $a=F_{n-1}$ and $b=F_n$).
    • Set $c=a+b$
    • (Now $c=F_{n+1}$)
    • $a\leftarrow b$ and $b \leftarrow c$.

Now observe that the loop body computes the new $a$ and $b$ as linear combinations of the old $a$ and $b$. Therefore there's a matrix that represents each turn through the loop. Many turns through the loop become multiplication with a power of the matrix.

This reasoning gives you the matrix $M=\pmatrix{1&1\\1&0}$ and an informal argument that $M^n \pmatrix{1\\0} = \pmatrix{F_n\\F_ {n-1}}$. This gives us one column of $M^n$, and it is reasonable to hope that the other one will also be something about Fibonacci numbers. One can either repeat the previous argument with different starting $a$ and $b$, or simply compute the first few powers of $M$ by hand and then recognize the pattern to be proved formally later.

share|improve this answer
    
But that's merely a very special case of what I wrote. To comprehend the essence of the matter it is better to abstract away from concrete cases. –  Bill Dubuque Sep 5 '11 at 16:48
    
@Bill, true enough. I thought it might be helpful for the OP to see it spelled out concretely, though. –  Henning Makholm Sep 5 '11 at 16:50
    
Sure, I just prefer to nudge students toward generalizations to help them better understand different ways to view the "essence" of things. –  Bill Dubuque Sep 5 '11 at 16:51
3  
And there is nothing wrong with that. Perhaps the OP will find the combination of our answers more helpful than either one in isolation would be. –  Henning Makholm Sep 5 '11 at 17:08
    
I think both have their merits - I'm a great fan of generalization, but I've found they often just tend to muddle students who haven't quite gotten the details down pat yet. I prefer to generalize once it's clear they understand the specific situation at hand, or if generalization seems like it would be the best way of giving them that understanding, but the latter definitely isn't always so. –  Steven Stadnicki Sep 5 '11 at 17:24

Set $u_n = (F_{n+1} , F_{n} )^T$. Then $u_{n+1} = A u_n$, where $ A = \begin{pmatrix}1&1\\1&0\end{pmatrix} $ and so $ u_{n} = A^n \ u_0 $. Since $u_0 = (1 ,0)^T$, the first column of $A^n$ is $u_n$. If you define $F_{-1}=1$, then the second column of $A^n$ is $A^n (0,1)^T = A^n u_{-1} = A^{n-1}u_0$, and so is the first column of $A^{n-1}$, which is $u_{n-1}$, as we have seen.

share|improve this answer

HINT $\ $ The same works for any sequence $\rm\:\:f_i\:$ satisfying a constant coefficient linear $\rm\:k$'th order recurrence. Namely the shift map $\rm\: S\: (f_k,\:\ldots,f_2,f_1)\: =\: (f_{k+1},\ldots,f_3,f_2)\:$ has matrix being a constant coefficient companion matrix. So $\rm\:S^n,\:$ a shift by $\rm\:n,\:$ has matrix an $\rm\:n$'th power of said companion matrix. If the recurrence had nonconstant coefficients, i.e. coefficients depending on the index $\rm\:k\:,\:$ then said shift $\rm\:S^n$ would not be an $\rm\:n$'th power of a constant coefficient matrix but, rather, a product of $\rm\:n\:$ matrices with variable coefficients (i.e. depending on the index $\rm\:k\:)\:.$

Note that this matrix representation yields addition formulas and fast polynomial-time algorithms for computing the sequence by computing matrix powers by repeated squaring.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.