Cassini's Identity/Lemma

From ProofWiki
Jump to navigation Jump to search

Lemma for Cassini's Identity

$\forall n \in \Z_{>1}: \begin{bmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$


Proof

Basis for the Induction

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


Induction Hypothesis

For $k \in \Z_{>1}$, it is assumed that:

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

It remains to be shown that:

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


Induction Step

The induction step follows from conventional matrix multiplication:

\(\displaystyle \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{k+1}\) \(=\) \(\displaystyle \begin{bmatrix} F_{k + 1} & F_k \\ F_k & F_{k - 1} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\) by the induction hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \begin{bmatrix} F_{k + 1} + F_k & F_{k + 1} \\ F_k + F_{k - 1} & F_k \end{bmatrix}\) Definition of Matrix Product
\(\displaystyle \) \(=\) \(\displaystyle \begin{bmatrix} F_{k + 2} & F_{k + 1} \\ F_{k + 1} & F_k \end{bmatrix}\)


So by induction:

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

$\blacksquare$


Sources