Continued Matrices

Solution 1:

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n} = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix}$

$\lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n} = \Phi \approx 1.618$

Solution 2:

$\prod_{i=0}^{n} \begin{bmatrix} a_{i} & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} p_{n} & p_{n-1}\\ q_{n} & q_{n-1} \end{bmatrix}\Leftrightarrow \frac{p_{n}}{q_{n}} = [a_{0}, a_{1}, a_{2}, ... , a_{n}]$

Consider the infinite continued fraction

$[1, 1, 1, 1, 1, ...] = 1 + \frac{1}{1 + \frac{1}{1+\frac{1}{1+ \frac{1}{\ddots}}}}$

$x = 1 + \frac{1}{1 + \frac{1}{1+\frac{1}{1+ \frac{1}{\ddots}}}}$

$x = 1 + \frac{1}{x}$

$x^{2} - x - 1 = 0$

$x = \frac{1 \pm \sqrt{5}}{2}$

but because we are adding, our solution is

$x = \frac{1 + \sqrt{5}}{2} = \Phi = 1.1618...$

now because

$\lim_{n\rightarrow \infty} \frac{p_{n}}{q_{n}} = [1, 1, 1, 1, ...] = \Phi$

and

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k} = \begin{bmatrix} a_{k} & b_{k} \\ c_{k} & d_{k} \end{bmatrix}$

then

$\lim_{k \rightarrow \infty} \frac{a_{k}}{c_{k}} = \Phi \approx 1.618$

Relevant wiki: Fast Fibonacci Transform

Let $A_k = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} ^ k$ . With matrix multiplication, we can see that $A_1 = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}, A_2 = \begin{bmatrix} 2 & 1\\ 1 & 0 \end{bmatrix}, A_3 = \begin{bmatrix} 3 & 2\\ 2 & 1 \end{bmatrix}, A_4 = \begin{bmatrix} 5 & 3\\ 3 & 2 \end{bmatrix}, A_5 = \begin{bmatrix} 8 & 5\\ 5 & 3 \end{bmatrix}$ . Looking at the coefficients of each of elements suggests that they follow a Fibonacci sequence .

Claim: $\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix} .$

Proof:

This statement is obviously true for $F_0$ , $F_1$ , and $F_2$ since

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^1 = \begin{bmatrix} F_2 & F_1\\ F_1 & F_0 \end{bmatrix}.$

Assume that it also holds for some $k$ , then we have

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^k = \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \end{bmatrix}.$

Now, multiplying both sides with $\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix},$ we have

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1} = \begin{bmatrix} F_{k} + F_{k+1} &F_{k+1}\\ F_{k+1} & F_{k} \end{bmatrix}.$

This implies

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{k+1} = \begin{bmatrix} F_{k+2} &F_{k+1}\\ F_{k+1} & F_{k} \end{bmatrix} ,$

which follows from the definition.

Hence, the identity holds for any $n$ . QED

---

Our answer is $\displaystyle \lim_{k\to \infty} \frac{a_{k}}{c_{k}} = \lim_{k\to \infty} \dfrac{F_{k+2}}{F_{k+1}} = \phi \approx \boxed{1.618}$ , where $\phi$ denotes the golden ratio .

calculating this was trivial, I saw the solution immediately