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!
 A: 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.
A: 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.
A: (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.
A: 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}$.
