Any nice way to calculate $A^n$

Question

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

I want to find a formula for $A^n$, is there any other way to do that than eigenvalue decomposition?

I tried: $A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}$

$A^3 = \begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}$ $A^4 = \begin{pmatrix} 2 & 3 \\ 3 & 5 \end{pmatrix}$ $A^5 = \begin{pmatrix} 3 & 5\\ 5 & 8 \end{pmatrix}$

However I do not see any pattern here which I could use for induction :/

Edit: ist it

$A^N= \begin{pmatrix} f_{n-1} & f_n \\ f_n & f_{n+1} \end{pmatrix}$ where $f_n$ is the n-th fibonacci number? But how to do induction here? I would be needing the product of $A^n A$.

Answer 1

The Fibonacci sequence satisfies, for $n > 1$, $f_{n} = f_{n-1}+f_{n-2}$. Now, suppose $$A^{n} = \begin{pmatrix} f_{n-1} & f_{n} \\ f_{n} & f_{n+1}\end{pmatrix} $$ for some $n\ge 1$. We have: $$A^{n+1} = A^{n}A = \begin{pmatrix} f_{n-1} & f_{n} \\ f_{n} & f_{n+1}\end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} f_{n} & f_{n-1}+f_{n} \\ f_{n+1} & f_{n}+f_{n+1}\end{pmatrix}$$ By the recursion formulae $f_{n} = f_{n-1}+f_{n-2}$, we have $f_{n-1}+f_{n} = f_{n+1}$ and also $f_{n}+f_{n+1} = f_{n+2}$. Thus: $$A^{n+1} = \begin{pmatrix} f_{n} & f_{n+1} \\ f_{n+1} & f_{n+2} \end{pmatrix}$$ as desired.

Answer 2

Recall that the Fibonacci sequence is defined recursively as $a_0=0,a_1=1$, and $a_{n}=a_{n-1}+a_{n-2}$. We have $$A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} $$ Show inductively that $$\begin{pmatrix} a_{n-1}\\ a_{n} \end{pmatrix} =A^{n-1} \begin{pmatrix} a_{0}\\ a_1 \end{pmatrix}$$

Then diagonalize $A$ so that $A=SDS^{-1}$ for some diagonal matrix $D$. Then $A^n=SD^nS^{-1}$ and you will arrive at the right answer. From this point, you have actually just derived Binet's Formula for the Fibonacci sequence, since you would have a closed form for $a_n$ by looking at the rows of $$A^n\begin{pmatrix} a_{0}\\ a_1 \end{pmatrix}=SD^nS^{-1}\begin{pmatrix} a_{0}\\ a_1 \end{pmatrix}$$.

Answer 3

You can derive the properties of Fibonacci from $A$ rather than vice versa.

$A^2 = A + I$ by direct computation; multiply by $A^n$ and you get $A^{n+2} = A^{n+1} + A^n$.

Answer 4

You can see that the last row $[1,1]$ will add together whatever lies in the last column of A. So what will lie at position $(1,2)$ and $(2,2)$?

(1,2) will copy the last value of whatever was stored at (2,2) last time, so it will act like a "memory".

These two facts together with the starting condition with values 1,1 invites us to see that we will be getting the Fibonacci sequence.