16
$\begingroup$

$$\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!

$\endgroup$
11
  • 4
    $\begingroup$ 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/…. $\endgroup$
    – joriki
    Sep 5, 2011 at 13:24
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 5, 2011 at 13:41
  • 4
    $\begingroup$ 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?" $\endgroup$
    – t.b.
    Sep 5, 2011 at 13:46
  • 1
    $\begingroup$ @Jyrki: I guess it's "chicken-and-egg" all over again. :) You can use the exponentiation to derive Binet, or you can use Binet to verify the correctness of the exponentiation. Hmm... $\endgroup$ Sep 5, 2011 at 13:46
  • 5
    $\begingroup$ 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. $\endgroup$
    – TMM
    Sep 5, 2011 at 14:08

4 Answers 4

6
$\begingroup$

(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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 5, 2011 at 16:48
  • $\begingroup$ @Bill, true enough. I thought it might be helpful for the OP to see it spelled out concretely, though. $\endgroup$ Sep 5, 2011 at 16:50
  • $\begingroup$ Sure, I just prefer to nudge students toward generalizations to help them better understand different ways to view the "essence" of things. $\endgroup$ Sep 5, 2011 at 16:51
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 5, 2011 at 17:08
  • $\begingroup$ 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. $\endgroup$ Sep 5, 2011 at 17:24
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why you define $F_{-1}$ to be $1$? It's weird. $\endgroup$
    – ZFR
    Nov 28, 2017 at 15:51
  • 1
    $\begingroup$ @RFZ, it makes the recurrence work. It's not uncommon. See en.wikipedia.org/wiki/…. $\endgroup$
    – lhf
    Nov 28, 2017 at 16:42
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I agree with others that this question is more about the intuition behind the result rather than a proof, so here's how I like to think of it using elementary matrices. First, note that $$\begin{bmatrix}1&1\\1&0\\\end{bmatrix}=\underbrace{\begin{bmatrix}1&1\\0&1\\\end{bmatrix}}_{E_2}\underbrace{\begin{bmatrix}0&1\\1&0\\\end{bmatrix}}_{E_1}$$ If $M$ is any matrix with $2$ rows, then $E_1M$ is that same matrix with the rows swapped. Now if we (left) multiply this new matrix by $E_2$, row $2$ is added to row $1$. The power just represents how many times we carry out this process. Here's a specific step that should make the process clear. $$\begin{bmatrix}8&5\\5&3\\\end{bmatrix}\xrightarrow[\phantom{..}E_1\phantom{..}]{}\begin{bmatrix}5&3\\8&5\\\end{bmatrix}\xrightarrow[\phantom{..}E_2\phantom{..}]{}\begin{bmatrix}8+5&5+3\\8&5\\\end{bmatrix}=\begin{bmatrix}13&8\\8&5\\\end{bmatrix}$$ And there it is! The recursive definition of the Fibonacci numbers is built right into the matrix $\begin{bmatrix}1&1\\1&0\\\end{bmatrix}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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