Proof of this result related to Fibonacci numbers: $\begin{pmatrix}1&1\\1&0\end{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!

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

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.