Tag: Strong Induction

Based on the definition, $f_n = f_{n-1} + f_{n-2}$ for every positive integer $n$. This means that $f_k = f_{k+2} -f_{k+1}$ for every positive integer $k$. Therefore, we can write
$$\displaystyle \sum_{k=1}^n f_k = \sum_{k=1}^n (f_{k+2}-f_{k+1}).$$The sum of $f_k$ from $1$ to $n$ is equal to the sum of $(f_{k+2} – f_{k+1})$ from $1$ to $n$. The sum above can be easily evaluated because it is telescopic (its terms cancel each other out). From this, we have
$$\displaystyle \sum_{k=1}^n f_k = f_{n+2}-f_2 = f_{n+2}-1.$$Thus, it is proven that $\displaystyle \sum_{k=1}^n f_k = f_{n+2}-1.$

Let $f_n$ denote the $n$-th term of the Fibonacci sequence. Based on the definition, $f_{n+2} = f_n + f_{n+1}$ for every $n \ge 0.$ Therefore,
$$\begin{aligned} f_{n+3} + f_n & = (f_{n+2} + f_{n+1}) + f_n \\ & = f_{n+2} + (f_{n+1} + f_n) \\ & = f_{n+2} + f_{n+2} \\ & = 2f_{n+2}. \end{aligned}$$Thus, it is proven that $f_{n+3} + f_n = 2f_{n+2}.$

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Based on the definition, $f_{n+2} = f_n + f_{n+1}$ for every $n \ge 0$. Therefore,
$$\begin{aligned} f_{n+3}-f_n & = (f_{n+2} + f_{n+1})- f_n \\ & = ((f_{n+1} + \cancel{f_n}) + f_{n+1})-\cancel{f_n} \\ & = 2f_{n+1}. \end{aligned}$$Thus, it is proven that $f_{n+3}- f_n = 2f_{n+1}.$

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Based on the definition, $f_{n+2} = f_{n} + f_{n+1}$ for every $n \ge 0$. Therefore,
$$\begin{aligned} f_{n-2}+f_{n+2} & = (f_n-f_{n-1}) + (f_n + f_{n+1}) \\ & = (f_n-(f_{n+1}-f_n)) + (f_n + f_{n+1}) \\ & = 3f_n. \end{aligned}$$Thus, it is proven that $f_{n-2}+f_{n+2} = 3f_{n}.$

Let $f_n$ represent the $n$-th term in the Fibonacci sequence and $P(n)$ denote the statement that $f_{2n} = f_n^2 + 2f_{n-1}f_n$ for some positive integer $n.$
Base Step:
$P(1)$ true because
$$\begin{aligned} f_{2(1)} & = f(2) \\ & = 1 \\ & = 1^2 + 2 \cdot 0 \cdot 1 \\ & = f_1^2 + 2f_0f_1. \end{aligned}$$ $P(2)$ is also true because
$$\begin{aligned} f_{2(2)} & = f(4) \\ & = 3 \\ & = 1^2 + 2 \cdot 1 \cdot 1 \\ & = f_2^2 + 2f_1f_2. \end{aligned}$$Inductive Step:
Assume that for any positive integer $k-1,$ $P(1), P(2),$ up to $P(k-1)$ are true We will prove that $P(k)$ is also true.

Consider $P(k-2)$ and $P(k-1)$ which respectively state that $f_{2k-4} = f_{k-2}^2 + 2f_{k-3}f_{k-2}$ dan $f_{2k-2} = f_{k-1}^2 + 2f_{k-2}f_{k-1}.$ Notice that
$$\begin{aligned} f_{2k} & = f_{2k-1} + f_{2k-2} \\ & = (f_{2k-2} + f_{2k-3}) + f_{2k-2} \\ & = (f_{2k-2} + (f_{2k-2}-f_{2k-4})) + f_{2k-2} \\ & = 3f_{2k-2}-f_{2k-4}. \end{aligned}$$Using the induction hypothesis, we obtain
$$\begin{aligned} 3f_{2k-2}-f_{2k-4} & = 3(f_{k-1}^2 + 2f_{k-2}f_{k-1})-(f_{k-2}^2 + 2f_{k-3}f_{k-2}) \\ & = 3f_{k-1}^2+6(f_k-f_{k-1})f_{k-1}-(f_k-f_{k-1})^2-2(f_{k-1}-f_{k-2})(f_{k}-f_{k-1}) \\ & = 3f_{k-1}^2+6(f_k-f_{k-1})f_{k-1}-(f_k-f_{k-1})^2-2(2f_{k-1}-f_{k})(f_{k}-f_{k-1}) \\ & = f_k^2 + 2f_kf_{k-1}. \end{aligned}$$Thus, $P(k)$ is proven to be true.

Since $P(1)$ is true dan assuming that for any positive integer $k-1,$ the truth of $P(k-1)$ implies the truth of $P(k),$ by the principle of mathematical induction, we conclude that the statement $P(n)$ is true for every positive integer $n.$ In other words, $f_{2n} = f_n^2 + 2f_{n-1}f_n$ for every positive integer $n.$ $\blacksquare$

Observe that
$$\begin{aligned} f_1 & = 1 = f_2 \\ f_1 + f_3 & = 1 + 2 = 3 = f_4 \\ f_1 + f_3 + f_5 & = 1 + 2 + 5 = 8 = f_6. \end{aligned}$$These observations lead us to conjecture that
$$f_1 + f_3 + \cdots + f_{2n-1} = f_{2n}$$for every positive integer $n.$ We will prove that this conjecture is true by using mathematical induction.

Let $n$ be a positive integer. Define $P(n) : f_1 + f_3 + \cdots + f_{2n-1} = f_{2n}.$ 
Base Step:
For $n = 1$, we have $P(1) : f_1 = 1 = f_2.$ The statement $P(1)$ is obviously true.
Inductive Step:
Assume that for any positive integer $k,$ we have
$$P(k) : f_1 + f_3 + \cdots + f_{2k-1} = f_{2k}.$$Assume that the statement above is true. We will show that $P(k+1)$ is true, i.e.
$$f_1 + f_3 + \cdots + f_{2k-1} + f_{2k+1} = f_{2k+2}.$$Notice that
$$\begin{aligned} \underbrace{f_1 + f_3 + \cdots + f_{2k-1}}_{f_{2k}} + f_{2k+1} & = f_{2k} + f_{2k+1} && (\text{Induction hypothesis}) \\ & = f_{2k+2}. && (\text{Definition of Fibonacci numbers}) \end{aligned}$$So, $P(k+1)$ is proven to be true. Since $P(1)$ is true, and for any positive integer $k,$ the truth of $P(k)$ implies the truth of $P(k+1),$ by the principle of mathematical induction, we conclude that the statement $P(n)$ is true for every positive integer $n.$

Therefore, the simple formula for the sum of the first $n$ odd-indexed Fibonacci numbers, i.e. $f_1 + f_3 + \cdots + f_{2n-1},$ is $f_{2n}.$

Observe that
$$\begin{aligned} f_2 & = 1 = 2-1 = f_3-1 \\ f_2 + f_4 & = 1 + 3 = 5-1 = f_5-1 \\ f_2 + f_4 + f_6 & = 1 + 3 + 8 = 13-1 = f_7-1. \end{aligned}$$These observations lead us to conjecture that
$$f_2 + f_4 + \cdots + f_{2n} = f_{2n+1}-1$$for every positive integer $n.$ We will prove that this conjecture is true by using mathematical induction.

Let $n$ be a positive integer. Define $P(n) : f_2 + f_4 + \cdots + f_{2n} = f_{2n+1}-1.$ 
Basis Step:
For $n = 1$, we have $P(1) : f_2 = 1 = 2-1= f_3-1.$ The statement $P(1)$ is certainly true.
Assume that for any positive integer $k,$ we have: $$P(k) : f_2 + f_4 + \cdots + f_{2k} = f_{2k+1}-1.$$Assume that the statement above is true. We will show that $P(k+1)$ is true, i.e.
$$f_2 + f_4 + \cdots + f_{2k} + f_{2k+2} = f_{2k+3}-1.$$Notice that
$$\begin{aligned} \underbrace{f_2+ f_4 + \cdots + f_{2k}}_{f_{2k+1}-1} + f_{2k+2} & = (f_{2k+1}-1) + f_{2k+2} && (\text{Induction hypothesis}) \\ & = (f_{2k+1} + f_{2k+2})-1 \\ & = f_{2k+3}-1. && (\text{Definition of Fibonacci numbers}) \end{aligned}$$So, $P(k+1)$ is proven to be true.

Since $P(1)$ is true, and for any positive integer $k,$ the truth of $P(k)$ implies the truth of $P(k+1),$ by the principle of mathematical induction, we conclude that the statement $P(n)$ is true for every positive integer $n.$ Therefore, the simple formula for the sum of the first $n$ even-indexed Fibonacci numbers, i.e., $f_2 + f_4 + \cdots + f_{2n},$ is $f_{2n+1}-1.$ 

Let $n$ be a positive integer. Consider two cases as follows.
Case 1:
Suppose that $n = 2k$ is a positive even integer. Therefore,
$$\begin{aligned} f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 & = (f_{2k} + f_{2k-1} + \cdots + f_1)-2(f_{2k-1} + f_{2k-3} + \cdots + f_1) \\ & = (f_{2k+2}-1)-2(f_{2k}) \\ & = (f_{2k+2}-f_{2k})-f_{2k}-1 \\ & = f_{2k+1}-f_{2k}-1 \\ & = f_{2k-1}-1 \\ & = f_{n-1}-1. \end{aligned}$$This is done by using the fact that $\displaystyle \sum_{m=1}^{2k} f_{m} = f_{2k+2}-1$ and $\displaystyle \sum_{m=1}^{k} f_{2m-1} = f_{2k}.$
Case 2:
Suppose that $n = 2k+1$ is a positive odd integer. Therefore,
$$\begin{aligned} f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 & = f_{2k+1}-(f_{2k}-f_{2k-1}+\cdots-(-1)^{n+1}f_1) \\ & = f_{2k+1}-(f_{2k-1}-1). \end{aligned}$$This is done by using the formula proven in Case 1. Then,
$$\begin{aligned} f_{2k+1}-(f_{2k-1}-1) & = f_{2k}+1 \\ & = f_{n-1}+1. \end{aligned}$$By combining the formulas for Case 1 and Case 2, we have $$f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1 = f_{n-1}-(-1)^n.$$

The statement will be proven using mathematical induction.
Let $n$ be a positive integer. Let $P(n)$ state that the sum of the squares of the first $n$ Fibonacci numbers, i.e. $f_1^2 + f_2^2 + \cdots + f_n^2$, is equal to $f_nf_{n+1}.$
Base Step:
For $n = 1$, we have $$f_1^2 = 1^2 = 1 = 1 \cdot 1 = f_1 \cdot f_2.$$Thus, $P(1)$ is true.
Inductive Step:
Assume that for any positive integer $k$, $P(k)$ is true, stating that the sum of the squares of the first k Fibonacci numbers, i.e. $f_1^2 + f_2^2 + \cdots + f_k^2,$ is equal to $f_kf_{k+1}.$ We’ll show that $P(k+1)$ is also true, meaning that the sum of the squares of the first $k+1$ Fibonacci numbers, i.e. $f_1^2 + f_2^2 + \cdots + f_k^2 + f_{k+1}^2,$ is equal to $f_{k+1}f_{k+2}.$
Notice that
$$\begin{aligned} \underbrace{f_1^2 + f_2^2 + \cdots + f_k^2}_{f_{k}f_{k+1}} + f_{k+1}^2 & = f_kf_{k+1} + f_{k+1}^2 && (\text{Induction hypothesis}) \\ & = f_{k+1}(f_k + f_{k+1}) \\ & = f_{k+1}f_{k+2}. && (\text{Definition of Fibonacci numbers}) \end{aligned}$$So, $P(k+1)$ is proven to be true.

Since $P(1)$ is true, and for any positive integer $k$, the truth of $P(k)$ implies the truth of $P(k+1)$, by the principle of mathematical induction, it follows that the statement $P(n)$ is true for every positive integer $n$. In other words, the sum of the squares of the first $n$ Fibonacci numbers, $f_1^2 + f_2^2 + \cdots + f_n^2,$ is equal to $f_nf_{n+1}$ for every positive integer $n.$ $\blacksquare$

The statement will be proven using mathematical induction.
Let $n$ be a positive integer. Define $$P(n) : f_{n+1}f_{n-1}-f_n^2 = (-1)^n.$$Base Step:
For $n = 1$, we have $$f_2f_0-f_1^2 = 1 \cdot 0-1^2 = -1 = (-1)^1.$$So, $P(1)$ is true.
Inductive Step:
Assume that for any positive integer $k,$ $$P(k) : f_{k+1}f_{k-1}-f_k^2 = (-1)^k.$$is true. We will show that $P(k+1)$ is true, i.e.
$$f_{k+2}f_{k}-f_{k+1}^2 = (-1)^{k+1}.$$Notice that
$$\begin{aligned} f_{k+2}f_{k}-f_{k+1}^2 & = (f_k + f_{k+1})f_k-f_{k+1}(f_{k-1} + f_k) \\ & = f_k^2 + \cancel{f_{k+1}f_k}-f_{k+1}f_{k-1}-\cancel{f_{k+1}f_k} \\ & = f_k^2-f_{k+1}f_{k-1} \\ & = -(-1)^k \\ & = (-1)^{k+1}. \end{aligned}$$So, $P(k+1)$ is true.

Since $P(1)$ is true, and for any positive integer $k$, the truth of $P(k)$ implies the truth of $P(k+1)$, by the principle of mathematical induction, it follows that the statement $P(n)$ is true for every positive integer $n$. In other words, $$f_{n+1}f_{n-1}-f_n^2 = (-1)^n$$for every positive integer $n.$ $\blacksquare$

The statement will be proven using mathematical induction.
Let $n$ be a positive integer. Define $$P(n) : f_1f_2 + f_2f_3 + \cdots + f_{2n-2}f_{2n-1} + f_{2n-1}f_{2n} = f_{2n}^2.$$Base Step:
For $n = 1$, we have
$$f_1f_2 = (1)(1) = 1 = 1^2 = f_2^2.$$So, $P(1)$ is true.
Inductive Step:
Assume that for any positive integer $k,$ $$P(k) : f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k} = f_{2k}^2$$is true. We will show that $P(k+1)$ is true, i.e.
$$f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k} + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} = f_{2k+2}^2.$$You should see that
$$\begin{aligned} \underbrace{f_1f_2 + f_2f_3 + \cdots + f_{2k-2}f_{2k-1} + f_{2k-1}f_{2k}}_{f_{2k}^2} + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} & = f_{2k}^2 + f_{2k}f_{2k+1} + f_{2k+1}f_{2k+2} \\ & = f_{2k}(f_{2k} + f_{2k+1}) + f_{2k+1}f_{2k+2} \\ & = f_{2k}f_{2k+2} + f_{2k+1}f_{2k+2} \\ & = f_{2k+2}(f_{2k} + f_{2k+1}) \\ & = f_{2k+2}f_{2k+2} \\ & = f_{2k+2}^2. \end{aligned}$$So, $P(k+1)$ is true.

Since $P(1)$ is true, and for any positive integer $k$, the truth of $P(k)$ implies the truth of $P(k+1)$, by the principle of mathematical induction, it follows that the statement $P(n)$ is true for every positive integer $n$. In other words, $$f_1f_2 + f_2f_3 + \cdots + f_{2n-2}f_{2n-1} + f_{2n-1}f_{2n} = f_{2n}^2$$for every positive integer $n.$ $\blacksquare$

The statement will be proven using strong induction.
Let $n$ be a positive integer. Fix the value of $m.$ Then, define
$$P(n) : f_{m+n} = f_mf_{n+1} + f_nf_{m-1}.$$Base Step:
For $n = 1,$ we have
$$\begin{aligned} f_{m+1} & = f_mf_2 + f_1f_{m-1} \\ & = f_m(1) + 1f_{m-1} \\ & = f_m + f_{m-1}. \end{aligned}$$So, $P(1)$ is true by using the definition of Fibonacci number. 
For $n = 2,$ we have
$$\begin{aligned} f_mf_3 + f_2f_{m-1} & = f_m(2) + 1f_{m-1} \\ & = 2f_m + f_{m-1} \\ & = f_m + (f_m + f_{m-1}) \\ & = f_m + f_{m+1} \\ & = f_{m+2}. \end{aligned}$$So, $P(2)$ is true.
Inductive Step:
Assume that for any positive integer $k,$ it holds
$$P(k) : f_{m+k} = f_mf_{k+1} + f_kf_{m-1}.$$We will show that $P(k+1)$ is true, i.e.
$$f_{m+k+1} = f_{m}f_{k+2} + f_{k+1}f_{m-1}.$$Consider $P(k-1)$ and $P(k)$ which respectively stated that
$$f_{m+k-1} = f_{m}f_k + f_{k-1}f_{m-1}$$and $$f_{m+k} = f_{m}f_{k+1} + f_{k}f_{m-1}.$$Notice that
$$\begin{aligned} f_{m}f_{k+2} + f_{k+1}f_{m-1} & = f_m(f_{k+1} + f_k) +(f_k + f_{k-1})f_{m-1} \\ & = f_mf_{k+1} + f_mf_k + f_kf_{m-1} + f_{k-1}f_{m-1} \\ & = (f_mf_k + f_{k-1}f_{m-1}) + (f_mf_{k+1} + f_kf_{m-1}) \\ & = f_{m+k-1} + f_{m+k} \\ & = f_{m+k+1}. \end{aligned}$$So, $P(k+1)$ is true.

By using the principle of mathematical induction, we conclude that $P(n)$ is true for every positive integer $n.$ In other words, it is proven that $$f_{m+n} = f_mf_{n+1} + f_nf_{m-1}$$for every positive integer $m$ and $n.$ $\blacksquare$

The statement will be proven using strong induction.
Let $n$ be a positive integer. Then, define
$$P(n) : f_n > \alpha^{n-2}.$$Base Step:
For $n = 3,$ we have $$f_3 = 2 > \dfrac{1+\sqrt5}{2} = \alpha.$$Furthermore, for $n = 4,$ we have $$f_4 = 3 > \dfrac{3+\sqrt5}{2} = \left(\dfrac{1+\sqrt5}{2}\right)^2 = \alpha^2.$$Thus, $P(3)$ and $P(4)$ both are true.
Inductive Step:
Assume that for any positive integer $k \ge 3,$ it holds
$$P(k) : f_k > \alpha^{k-2}.$$Assume that this statement is true. We will prove that $P(k+1)$ is also true, i.e.
$$f_{k+1} > \alpha^{k-1}.$$Because $\alpha = \dfrac{1+\sqrt5}{2}$ is a root of quadratic equation $x^2-x-1=0,$ we have $\alpha^2 = \alpha + 1.$ Hence,
$$\begin{aligned} \alpha^{k-1} & = \alpha^2 \cdot \alpha^{k-3} \\ & = (\alpha + 1) \cdot \alpha^{k-3} \\ & = \alpha^{k-2} + \alpha^{k-3}. \end{aligned}$$By the inductive hypothesis, we have the inequalities
$$\alpha^{n-2} < f_n~\text{dan}~\alpha^{n-3} < f_{n-1}.$$By adding these two inequalities, we have
$$\alpha^{n-1} = \alpha^{n-2} + \alpha^{n-3} < f_{n} + f_{n-1} = f_{n+1}.$$Thus $P(k+1)$ is proven to be true.

By using the principle of mathematical induction, we conclude that $P(n)$ is true for every positive integer $n \ge 3.$ In other words, it is proven that $f_{n} > \alpha^{n-2}$ for every positive integer $n \ge 3$ where $\alpha = \dfrac{1+\sqrt5}{2}.$ $\blacksquare$

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Denote $P(n)$ as representing $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ for a positive integer $n.$ Note that $\alpha = \dfrac{1 + \sqrt5}{2}$ and $\beta = \dfrac{1-\sqrt5}{2}$ are the roots of the quadratic equation $x^2-x-1 = 0,$ so it holds that $\alpha^2 = \alpha + 1$ and $\beta^2 = \beta + 1.$
Base Step:
$P(1)$ is true because
$$\begin{aligned} f_{1} & = 1 \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{2\sqrt5}{2}\right) \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{1 + \sqrt5}{2}-\dfrac{1-\sqrt5}{2}\right) \\ & = \dfrac{1}{\sqrt5}(\alpha-\beta). \end{aligned}$$ $P(2)$ is also true because
$$\begin{aligned} f_{2} & = 1 \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{4\sqrt5}{4}\right) \\ & = \dfrac{1}{\sqrt5}\left(\dfrac{6 + 2\sqrt5}{4}-\dfrac{6-2\sqrt5}{4}\right) \\ & = \dfrac{1}{\sqrt5}(\alpha^2-\beta^2). \end{aligned}$$Inductive Step:
Assume that for any positive integer $k,$ $P(1), P(2),$ up to $P(k)$ are true.  We will show that $P(k+1)$ is also true.

Consider $P(k-1)$ and $P(k)$ that respectively state $f_{k-1} = \dfrac{1}{\sqrt5}(\alpha^{k-1}-\beta^{k-1})$ and $f_{k} = \dfrac{1}{\sqrt5}(\alpha^{k}-\beta^{k}).$ Notice that
$$\begin{aligned} f_{k+1} & = f_{k-1} + f_k \\ & = \dfrac{1}{\sqrt5}(\alpha^{k-1}-\beta^{k-1}) + \dfrac{1}{\sqrt5}(\alpha^{k}-\beta^{k}) \\ & = \dfrac{1}{\sqrt5}\left((\alpha^{k-1}-\beta^{k-1} + (\alpha^{k}-\beta^{k})\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k-1}(\alpha+1)-\beta^{k-1}(\beta+1)\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k-1} \cdot \alpha^2-\beta^{k-1} \cdot \beta^2\right) \\ & = \dfrac{1}{\sqrt5}\left(\alpha^{k+1}-\beta^{k+1}\right). \end{aligned}$$So, $P(k+1)$ is proven to be true.

By using the principle of mathematical induction, we can conclude that the statement $P(n)$ is true for every positive integer $n.$ In other words, for every positive integer $n,$ it holds $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ where $\alpha = \dfrac{1 + \sqrt5}{2}$ and $\beta = \dfrac{1-\sqrt5}{2}.$ $\blacksquare$

The statement will be proven using mathematical induction.
Let $n$ be a positive integer. Define $$P(n) : F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$$where $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ and $f_n$ represents the $n$-th term in the Fibonacci sequence.
Base Step:
For $n = 1$, we have
$$F^1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} f_2 & f_1 \\ f_1 & f_0 \end{pmatrix}.$$Thus, $P(1)$ is true.
Inductive Step:
Assume that for any positive integer$k,$ it holds
$$P(k) : F^k = \begin{pmatrix} f_{k+1} & f_k \\ f_k & f_{k-1} \end{pmatrix}.$$We’ll show that $P(k+1)$ is also true, meaning that
$$F^{k+1} = \begin{pmatrix} f_{k+2} & f_{k+1} \\ f_{k+1} & f_{k} \end{pmatrix}.$$You should see that
$$\begin{aligned} F^{k+1} & = F^k \cdot F \\ & = \begin{pmatrix} f_{k+1} & f_k \\ f_k & f_{k-1} \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\ & = \begin{pmatrix} f_{k+1} + f_k & f_{k+1}+0 \\ f_k+f_{k-1} & f_k + 0 \end{pmatrix} \\ & = \begin{pmatrix} f_{k+2} & f_{k+1} \\ f_{k+1} & f_k \end{pmatrix}. && (\text{Definition of Fibonacci sequence}) \end{aligned}$$So, $P(k+1)$ is proven to be true.

Since $P(1)$ is true, and for any positive integer $n$, the truth of $P(k)$ implies the truth of $P(k+1),$ by the principle of mathematical induction, it follows that the statement $P(n)$ is true for every positive integer $n.$ In other words, $F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$ for every positive integer $n$ where $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ and $f_n$ represents the $n$-th term in the Fibonacci sequence. $\blacksquare$