To prove the matrix-power formula by induction, we need to show that the following holds for all positive integers $n$:

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n = \begin{bmatrix} f_{n-1} & f_n \\ f_n & f_{n+1} \end{bmatrix},$

where $f_n$ is the $n$th Fibonacci number, defined as:

$f_0 = 0, \quad f_1 = 1, \quad \text{and} \quad f_n = f_{n-1} + f_{n-2} \quad \text{for} \, n \geq 2.$

Step 1: Base Case $n = 1$

We first check the base case when $n = 1$.

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^1 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}.$

For $n = 1$, the right-hand side of the equation should be:

$\begin{bmatrix} f_{1-1} & f_1 \\ f_1 & f_{1+1} \end{bmatrix} = \begin{bmatrix} f_0 & f_1 \\ f_1 & f_2 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}.$

Thus, the base case holds.

Step 2: Induction Hypothesis

Assume that the formula holds for some positive integer $k$, i.e., assume that

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^k = \begin{bmatrix} f_{k-1} & f_k \\ f_k & f_{k+1} \end{bmatrix}.$

Step 3: Inductive Step

We need to show that the formula also holds for $n = k+1$. Consider the matrix raised to the $k+1$ power:

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{k+1} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^k \cdot \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}.$

Using the induction hypothesis, this becomes:

$\begin{bmatrix} f_{k-1} & f_k \\ f_k & f_{k+1} \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}.$

Carrying out the matrix multiplication:

$\begin{bmatrix} f_{k-1} & f_k \\ f_k & f_{k+1} \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} f_k & f_{k-1} + f_k \\ f_{k+1} & f_k + f_{k+1} \end{bmatrix}.$

Using the Fibonacci recurrence relation, $f_{k+1} = f_k + f_{k-1}$ and $f_{k+2} = f_{k+1} + f_k$, we have:

$\begin{bmatrix} f_k & f_{k+1} \\ f_{k+1} & f_{k+2} \end{bmatrix}.$

This matches the form:

$\begin{bmatrix} f_{(k+1)-1} & f_{k+1} \\ f_{k+1} & f_{(k+1)+1} \end{bmatrix}.$

Conclusion

By the principle of mathematical induction, the formula holds for all positive integers $n$.

Would you like further details or have any questions?

Here are 5 related questions for further exploration:

1. How does the Fibonacci sequence relate to the eigenvalues of the matrix $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$?
2. Can you prove the matrix power formula using eigenvalues and eigenvectors instead of induction?
3. How does the golden ratio connect to the Fibonacci sequence and this matrix representation?
4. Can you derive the closed-form expression for the Fibonacci numbers (Binet’s formula) using matrices?
5. How does this matrix form extend to solving linear recurrence relations in general?

Tip: Inductive proofs are powerful tools in combinatorics and number theory, especially for problems involving sequences and recurrence relations.