## Example Problems and Solutions – Fibonacci Number and Fibonacci Sequence

Fibonacci, also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano, was an Italian mathematician renowned as the “greatest mathematician of the Middle Ages.” He was born around 1170 and is believed to have passed away around 1250. Fibonacci is famous for his work in introducing a sequence of numbers now known as the Fibonacci numbers. Some even claim that this sequence is the “fingerprint of God.”

Read: Materi, Soal, dan Pembahasan – Bilangan Fibonacci

In his book titled “Liber Abaci,” written in 1202, Fibonacci posed a problem related to the breeding of rabbits in a specific area. The problem can be narrated as follows: A pair of young rabbits (one male and one female) are placed on a remote island. It is assumed that these rabbits do not reproduce until they are $2$ months old, and once they reach $2$ months of age, they reproduce one pair of young rabbits each month. It is also assumed that the rabbits on the island do not die. How many pairs of rabbits will be on the island after $n$ months? Let’s denote $f_n$ as the number of pairs of rabbits after $n$ months. In this case, $f_1 = 1$ because there is only one pair of rabbits on the island after the first month. Since this pair of rabbits does not reproduce in the second month, we have $f_2 = 1.$ Next, this pair of rabbits reproduces one more pair of young rabbits. So, at the end of the third month, there are now $2$ pairs of rabbits. Therefore, $f(3) = 2.$

To determine the number of pairs of rabbits after $n$ months, you can add the number of pairs of rabbits in the previous month, which is $f_{n-1},$ to the number of pairs of rabbits that were just born, which is $f_{n-2},$ because they are born from pairs of rabbits that are two months old. This idea leads to the formal definition of the “Fibonacci sequence.”

### Definition: Fibonacci Sequence and Number

The Fibonacci sequence is defined recursively as follows: $f_1 = 1, f_2 = 1,$ and $f_n = f_{n-1} + f_{n-2}$ for every positive integer $n \ge 3.$ The terms of the Fibonacci sequence are referred to as Fibonacci numbers.

According to historical records, Édouard Lucas (1842–1891), a French mathematician, was the first person to give the name “Fibonacci” to this sequence of numbers. Lucas was a mathematician who extensively studied the Fibonacci sequence and discovered many of its properties. Furthermore, the definition mentioned above indicates that starting from the third term, the value of each term is determined by adding the two preceding terms, which is a key characteristic of the Fibonacci sequence.

We will evaluate the $10$ first Fibonacci numbers manually as follows.
\begin{aligned} f_1 & = 1 \\ f_2 & = 1 \\ f_3 & = f_2 + f_1 = 1 + 1 = 2 \\ f_4 & = f_3 + f_2 = 1 + 2 = 3 \\ f_5 & = f_4 + f_3 = 3 + 2 = 5 \\ f_6 & = f_5 + f_4 = 5 + 3 = 8 \\ f_7 & = f_6 + f_5 = 8 + 5 = 13 \\ f_8 & = f_7 + f_6 = 13 + 8 = 21 \\ f_9 & = f_8 + f_7 = 21 + 13 = 34 \\ f_{10} & = f_9 + f_8 = 34 + 21 = 55. \end{aligned}The Fibonacci sequence is defined recursively, where the values of its terms depend on the previous terms. However, the $n$-th term of the Fibonacci sequence can also be determined using an explicit formula that has been discovered, which is
$$f(n) = \frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n- \left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$This formula can be proven to be true using strong induction (which will be discussed further in the problems section below).

The Fibonacci sequence possesses several interesting properties. One of them is that the ratio between two consecutive Fibonacci numbers approaches the golden ratio, denoted by $\phi$ (pronounced as “phi”), which has an approximate value of $1.61803$. The golden ratio is frequently encountered in nature and art, making the Fibonacci sequence an intriguing mathematical structure.

Furthermore, the Fibonacci sequence has practical applications in various fields. For instance, in financial mathematics, the Fibonacci sequence is used in calculations related to interest and investments. In computer science, the Fibonacci sequence is employed in algorithms and data structures, such as binary search algorithms and constant-time division. Even in biology, Fibonacci sequences often appear in the distribution of leaves on a plant or the arrangement of petals in flowers. For example, the number of spirals in plants with leaf arrangements forms a pattern known as phyllotaxis, and it often follows Fibonacci numbers. These practical and aesthetic aspects of the Fibonacci sequence make it a fascinating and versatile concept in mathematics with connections to many areas of science and art.

From this, we can say that the works of Fibonacci have contributed to enriching the world of mathematics and science in general, providing insights into how mathematical patterns and structures emerge in nature and our daily lives.

### Quote by Linda Hogan

There is a way that nature speaks, that land speaks. Most of the time we are simply not patient enough, quiet enough, to pay attention to the story.

Question Type: Essay

## Problem Number 1

Let $n$ be a positive integer. Prove that $\displaystyle \sum_{k=1}^n f_k = f_{n+2}-1.$

Solution

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.$

[collapse]

Read: Materi, Soal, dan Pembahasan – Deret Teleskopik

## Problem Number 2

Let $f_n$ denote the $n$-th term of the Fibonacci sequence. Prove that $f_{n+3} + f_n = 2f_{n+2}$ for every positive integer $n.$

Solution

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}.$

[collapse]

## Problem Number 3

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that $f_{n+3}- f_n = 2f_{n+1}$ for every positive integer $n.$

Solution

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}.$

[collapse]

## Problem Number 4

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that $f_{n-2}+f_{n+2} = 3f_{n}$ for every positive integer $n$.

Solution

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}.$

[collapse]

## Problem Number 5

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that $f_{2n} = f_n^2 + 2f_{n-1}f_n$ for every positive integer $n.$

Solution

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$

[collapse]

Read: Soal dan Pembahasan – Barisan dan Deret Aritmetika

## Problem Number 6

Let $n$ be a positive integer. Determine and prove a simple formula for the sum of the first $n$ odd-indexed Fibonacci numbers, i.e. $f_1 + f_3 + \cdots + f_{2n-1}.$

Solution

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}.$

[collapse]

## Problem Number 7

Let $n$ be a positive integer. Determine and prove a simple formula for the sum of the first $n$ even-indexed Fibonacci numbers, i.e. $f_2 + f_4 + \cdots + f_{2n}.$

Solution

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.$

[collapse]

## Problem Number 8

Let $n$ be a positive integer. Determine and prove a simple formula for expression $$f_n-f_{n-1} +f_{n-2}-\cdots+(-1)^{n+1}f_1.$$

Solution

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.$$

[collapse]

## Problem Number 9

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that
$$\displaystyle \sum_{j=1}^n f_j^2 = f_1^2 + f_2^2 + \cdots + f_n^2 = f_nf_{n+1}$$for every positive integer $n.$

Solution

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$

[collapse]

## Problem Number 10

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that
$$f_{n+1}f_{n-1}-f_n^2 = (-1)^n$$for every positive integer $n.$

Solution

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$

[collapse]

## Problem Number 11

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that
$$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.$

Solution

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$

[collapse]

## Problem Number 12

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that $$f_{m+n} = f_mf_{n+1} + f_nf_{m-1}$$for every positive integer $m$ and $n.$

Solution

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$

[collapse]

## Problem Number 13

Let $f_n$ represent the $n$-th term in the Fibonacci sequence. Prove that $f_n > \alpha^{n-2}$ for every positive integer $n \ge 3$ where $\alpha = \dfrac{1+\sqrt5}{2}.$

Pembahasan

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$

[collapse]

## Problem Number 14

Let $n$ be a positive integer, $\alpha = \dfrac{1 + \sqrt5}{2},$ and $\beta = \dfrac{1-\sqrt5}{2}.$ Show that $f_n = \dfrac{1}{\sqrt5}(\alpha^n-\beta^n)$ where $f_n$ represents $n$-th term of Fibonacci sequence.

Solution

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$

[collapse]

## Problem Number 15

Let $F = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.$ Show that $F^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix}$ for every positive integer $n$ where $f_n$ represents the $n$-th term in the Fibonacci sequence.

Solution

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$

[collapse] 