0
$\begingroup$

How do I prove by induction that the Fibonacci sequence correlates to the below expression of matrices?

$$\begin{pmatrix} f(n) \\ f(n+1) \end{pmatrix} = \begin{pmatrix} 0 && 1 \\ 1 && 1 \end{pmatrix}^n \begin{pmatrix}0 \\ 1\end{pmatrix}, \text{ for any } n\geq0$$

$\endgroup$
  • $\begingroup$ It is very clearly true directly already, you just represent the recursive formula in a matrix, for the $n $-th number, you apply the formula $n$ times. $\endgroup$ – DWe1 Oct 25 '17 at 7:20
1
$\begingroup$

Take $n = 0$ and see that $$\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$ is clearly true: We just see the first two terms.

Suppose for a particular $n \in \mathbb{N}$, $$\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$ then, $$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} f(n) \\ f(n+1) \end{bmatrix} = \begin{bmatrix} f(n+1) \\ f(n) + f(n+1) \end{bmatrix} = \begin{bmatrix} f(n+1) \\ f(n+2) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n+1}\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.