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.