Uppgift 4

Vi bevisar utsagan med induktion. Eftersom vi får att $F_2=F_1+F_0=1$ så stämmer basfallet $n=1$, ty
$$ \begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}. $$
Vi antar nu att
$$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$
för något $n\geq1$. Vi vill visa att formeln då även gäller för nästa heltal, dvs. att
$$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n+1} = \begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix}. \tag{1} $$
Vi får
$$ \begin{aligned} \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n+1} &= \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} \begin{pmatrix}1&1\\1&0\end{pmatrix}\\ &\mathrel{=}_{\text{[ind.ant.]}} \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} \begin{pmatrix}1&1\\1&0\end{pmatrix}\\ &= \begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_n\end{pmatrix}\\ &\mathrel{=}_{\text{[rekursion]}} \begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix}, \end{aligned} $$
så vi har visat (1). Enligt induktionsprincipen gäller därför utsagan för alla $n=1,2,3,\ldots$