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

  • 0
    Eigendecompose the matrix being powered, take the $n$-th power of the resulting diagonal matrix, use Binet... something like that.2011-09-05
  • 2
    What, in your opinion, is the difference between a verification and a proof? You might be interested in this post: http://math.stackexchange.com/questions/61541/are-proofs-by-induction-inferior-to-other-proofs.2011-09-05
  • 0
    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.2011-09-05
  • 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?"2011-09-05
  • 0
    @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...2011-09-05
  • 0
    BTW: Robin's answer [here](http://math.stackexchange.com/questions/7266/7268#7268) might be of interest...2011-09-05
  • 0
    @J.M.: You're right, of course. May be I just feel that a proof that doesn't wander outside the domain of integers is more natural in this case?2011-09-05
  • 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.2011-09-05
  • 0
    Related to @Thijs's comment: any recurrence is easily couched as matrix powering.2011-09-05
  • 0
    The Fibonacci sequence is *defined* by a recurrence. The matrix exponentiation is *defined* by a recurrence. A little look shows in this case they are essentially the *same* recurrence. If in doubt calculate the square of the matrix, then multiply suitably to find the cube, then the fourth power. Induction is built into the problem, which isn't really a problem, just a rewording.2011-09-05
  • 0
    See also: http://math.stackexchange.com/questions/693905/proof-by-mathematical-induction-fibonnaci-numbes-and-matrices2015-11-07

3 Answers 3

5

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

  • 1
    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.2011-09-05
  • 0
    @Bill, true enough. I thought it might be helpful for the OP to see it spelled out concretely, though.2011-09-05
  • 0
    Sure, I just prefer to nudge students toward generalizations to help them better understand different ways to view the "essence" of things.2011-09-05
  • 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.2011-09-05
  • 0
    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.2011-09-05
  • 0
    @Ste Indeed, it may prove useful to mention both general and special answers. Furthermore, it is helpful to *explicitly* point out the relationship between the general and special answers, since that may not obvious to the reader.2011-09-05
5

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.

  • 0
    Why you define $F_{-1}$ to be $1$? It's weird.2017-11-28
  • 1
    @RFZ, it makes the recurrence work. It's not uncommon. See https://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers.2017-11-28
5

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.