linear algebra - Proof of this result related to Fibonacci numbers: $begin{pmatrix}1&1\1&0end{pmatrix}^n=begin{pmatrix}F_{n+1}&F_n\F_n&F_{n-1}end{pmatrix}$?

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

Answer

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