Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do you prove that: $$ \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{pmatrix}$$

share|cite|improve this question

marked as duplicate by Grigory M, mrf, drhab, Joe Johnson 126, graydad Oct 14 '15 at 1:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

12  
What about induction? – Start wearing purple May 7 '14 at 8:17
up vote 18 down vote accepted

Let

$$A=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$

And the Fibonacci numbers, defined by

$$\begin{eqnarray} F_0&=&0\\ F_1&=&1\\ F_{n+1}&=&F_n+F_{n-1} \end{eqnarray}$$

Then, by induction,

$$A^1=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}$$

And if for $n$ the formula is true, then

$$A^{n+1}=A\,A^n=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix}=\begin{pmatrix} F_{n+1}+F_n & F_{n}+F_{n-1} \\ F_{n+1} & F_{n} \end{pmatrix}=\begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{pmatrix}$$

So, the induction step is true, and by induction, the formula is true for all $n>0$.

share|cite|improve this answer

$$\begin{align} F(n+1) &= 1\,F(n) + 1\,F(n-1)\\ F(n) &= 1\,F(n) + 0\,F(n-1)\\ \\ \begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n) \\ F(n - 1) \end{bmatrix} \\ \begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \\ \\ \text{as well as} \\ \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(0) \\ F(-1) \end{bmatrix} \\ \\ \text{from which it follows}\\ \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) & F(0) \\ F(0) & F(-1) \end{bmatrix} \\ \\ \text{and choosing} \\ F(1) &= 1 \\ F(0) &= 0 \\ F(-1) &= 1 \end{align}$$

share|cite|improve this answer
    
Shouldn't that be F(1)=1 , F(0)=1 , F(-1)=0 ? – Raidri May 7 '14 at 15:56
    
@Raidri If F(-1) + F(0) = F(1), what do you get? The negatives of the fibonacci form a pretty recognizable pattern actually ^_^ – DanielV May 7 '14 at 16:30

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