# Recitation 9A

Problem 1: Define the Fibonacci sequence by $F_0=0$, $F_1=1$ and $F_{n+2}=F_{n+1}+F_n$. Denote $\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$ as $M$. Prove that $M \begin{bmatrix}F_{n+1} \\ F_{n}\end{bmatrix} = \begin{bmatrix}F_{n+2} \\ F_{n+1}\end{bmatrix}$ and $M^n \begin{bmatrix}1 \\ 0\end{bmatrix}=\begin{bmatrix}F_{n+1} \\ F_n\end{bmatrix}$. Use these results to find a closed formula for $F_n$.

Proof: Check that $M \begin{bmatrix}F_{n+1} \\ F_{n}\end{bmatrix}= \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} \begin{bmatrix}F_{n+1} \\ F_{n}\end{bmatrix} = \begin{bmatrix}F_{n+1} + F_n \\ F_{n+1}\end{bmatrix} = \begin{bmatrix}F_{n+2} \\ F_{n+1}\end{bmatrix}$. In other words, if we multiply $\begin{bmatrix}F_{n+1} \\ F_n\end{bmatrix}$ with matrix $M$, both indices increase by 1. Therefore if we multiply $\begin{bmatrix}F_1 \\ F_0\end{bmatrix}$ with matrix $M$ for $n$ times, both indices increase by $n$. That is $M^n \begin{bmatrix}1 \\ 0\end{bmatrix} = M^n \begin{bmatrix}F_1 \\ F_0\end{bmatrix} = \begin{bmatrix}F_{n+1} \\ F_n\end{bmatrix}$. In order to find a closed formula for $F_n$, we have to compute $M^n$ using diagonalization. Set $\lambda_1 = \frac{1+\sqrt{5}}{2}, \lambda_2 = \frac{1-\sqrt{5}}{2}$. The diagonalization of $M$ is $PDP^{-1}$, where $P= \begin{bmatrix}\lambda_1 & \lambda_2 \\ 1 & 1\end{bmatrix}$ and $D= \begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2\end{bmatrix}$. Hence $\begin{bmatrix}F_{n+1} \\ F_n\end{bmatrix}= M^n \begin{bmatrix}1 \\ 0\end{bmatrix}=PD^nP^{-1}\begin{bmatrix}1 \\ 0\end{bmatrix}=\begin{bmatrix}\lambda_1 & \lambda_2 \\ 1 & 1\end{bmatrix}\begin{bmatrix}\lambda_1^n & 0 \\ 0 & \lambda_2^n\end{bmatrix}\frac{1}{\sqrt{5}}\begin{bmatrix}1 & -\lambda_2 \\ -1 & \lambda_1\end{bmatrix}\begin{bmatrix}1 \\ 0\end{bmatrix}$. Expand the equation and obtain $F_n = \frac{1}{\sqrt{5}}(\lambda_1^n-\lambda_2^n)$.

Problem 2: Let $u=\begin{bmatrix}2\\-5\\-1\end{bmatrix}$ and $v= \begin{bmatrix}-7\\-4\\6\end{bmatrix}$. Compute $u\cdot v$, $||u||^2$, $||v||^2$, $||u+v||^2$ and $||u-v||^2$. Check the Pythagorean theorem and the parallelogram law hold true.

Solution: Plug in $u$ and $v$ and obtain $u\cdot v=0$, $||u||^2=30$, $||v||^2=101$, $||u+v||^2=||u-v||^2=131$. The Pythagorean theorem holds because $u\cdot v=0$ and $||u||^2+||v||^2=||u+v||^2$. The parallelogram law holds as well because $||u+v||^2+||u-v||^2=2||u||^2+2||v||^2$.