2.7 FIBONACCI NUMBERS

2.7 FIBONACCI NUMBERS

The Fibonacci numbers $F_n$ for ($n \geq 0$) are defined recursively as follows: $F_0 = 0, F_1 = 1$, and for $n \geq 2, F_n = F_{n-1} + F_{n-2}$

52 Prove by induction on n that $\sum_{i=0}^{n}F_i = F_{n+2} -1$

52-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
F_{2} &= F_1 + F_0
\\
&= 1 + 0 = 1
\\
\end{aligned}
$$

$$
\begin{aligned}
\sum_{i=0}^{n}F_i &= F_{n+2} -1
\\
\sum_{i=0}^{0}F_i &= F_{0+2} -1
\\
0 &= F_{2} -1
\\
F_{2} = 1
\end{aligned}
$$

따라서 n = 0 일 때 성립한다.

52-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=0}^{k}F_i &= F_{k+2} -1
\end{aligned}
$$

52-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$
\begin{aligned}
\sum_{i=0}^{k+1}F_i &= F_{k+3} -1
\\
\sum_{i=0}^{k+1}F_i &= F_{k+2} + F_{k+1} -1
\\
\sum_{i=0}^{k}F_i + F_{k+1} &= F_{k+2} + F_{k+1} -1
\\
\sum_{i=0}^{k}F_i &= F_{k+2}-1
\\
&\text{k 일 때 활용}
\\
F_{K+2} - 1 &= F_{k+2}-1
\end{aligned}
$$

따라서 k+1일 때 성립한다.

53 Prove by induction that $F_{n+k} = F_kF_{n+1} + F_{k-1}F_n$

53-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
F_{n+k} &= F_kF_{n+1} + F_{k-1}F_n
\\
F_{k} &= F_kF_{1} + F_{k-1}F_0
\\
F_{k} &= F_{k}
\end{aligned}
$$

따라서 n = 0 일 때 성립한다.

53-2. Induction (귀납 가정)

---

n <= t일 때 성립한다고 가정하자.

$$
\begin{aligned}
F_{t+k} &= F_kF_{t+1} + F_{k-1}F_t
\\
F_{t+k-1} &= F_kF_{t} + F_{k-1}F_{t-1}
\\
\end{aligned}
$$

53-3. Induction Proof (가정을 이용한 증명)

---

n = t + 1일 때를 증명해보자

$$
\begin{aligned}
F_{t+k+1} &= F_{k}F_{t+2} + F_{k-1}F_{t+1}
\\
F_{t+k+1} &= F_{k}(F_{t+1} + F_{t}) + F_{k-1}(F_{t}+F_{t-1})
\\
F_{t+k+1} &= F_{k}F_{t+1} + F_{k}F_{t} + F_{k-1}F_{t} + F_{k-1}F_{t-1}
\\
F_{t+k+1} &= F_{t+k} + F_{t+k-1}
\\
\end{aligned}
$$

따라서 k+1일 때 성립한다.

54 Prove by induction on $n \geq 1$ that $\sum_{i=1}^nF_i^2=F_nF_{n+1}$

54-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^nF_i^2 &= F_nF_{n+1}
\\
\sum_{i=1}^1F_i^2 &= F_1F_{2}
\\
F_1^2 &= F_1F_{2}
\\
1^2 &= 1*1
\\
1 &= 1
\end{aligned}
$$

따라서 n = 1 일 때 성립한다.

54-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
\sum_{i=1}^kF_i^2 &= F_kF_{k+1}
\\
\end{aligned}
$$

54-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$
\begin{aligned}
\sum_{i=1}^{k+1}F_i^2 &= F_{k+1}F_{k+2}
\\
\sum_{i=1}^{k}F_i^2 + F_{k+1}^2 &= F_{k+1}(F_{k+1}+F_{k})
\\
F_kF_{k+1} + F_{k+1}^2 &= F_{k+1}(F_{k+1}+F_{k})
\\
F_kF_{k+1} + F_{k+1}^2 &= F_{k+1}^2 + F_{k+1}F_{k}
\\
F_{k+1}^2 &= F_{k+1}^2
\\
\end{aligned}
$$

따라서 k+1일 때 성립한다.

55 Prove by induction on $n \geq 1$ that $F_{n+1}F_{n+2} = F_{n}F_{n+3}+(-1)^n$

55-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
F_{n+1}F_{n+2} &= F_{n}F_{n+3}+(-1)^n
\\
F_{1}F_{2} &= F_{0}F_{3}+(-1)^0
\\
1 * 1 &= 0 * 3 + 1
\\
\end{aligned}
$$

따라서 n = 1 일 때 성립한다.

55-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
F_{k+1}F_{k+2} &= F_{k}F_{k+3}+(-1)^k
\end{aligned}
$$

55-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$
\begin{aligned}
F_{k+2}F_{k+3} &= F_{k+1}F_{k+4}+(-1)^{k+1}
\\
F_{k+2}F_{k+3} &= F_{k+1}(F_{k+3}+F_{k+2})+(-1)^{k+1}
\\
F_{k+2}F_{k+3} &= F_{k+1}F_{k+3} + F_{k+1}F_{k+2}+(-1)^{k+1}
\\
F_{k+3}(F_{k+2}-F_{k+1}) &= F_{k}F_{k+3}+(-1)^k+(-1)^{k+1}
\\
F_{k+3}(F_{k+2}-F_{k+1}) &= F_{k}F_{k+3}
\\
F_{k+3}F_{k} &= F_{k}F_{k+3}
\\
\end{aligned}
$$

따라서 k+1일 때 성립한다.

56 Prove by induction on $n \geq 2$ that $F_{n-1}F_{n+1} = F_n^2+(-1)^n$

56-1. Basis Condition

---

n = 2일 때 성립하는가?

$$
\begin{aligned}
F_{n-1}F_{n+1} &= F_n^2+(-1)^n
\\
F_{1}F_{3} &= F_2^2+(-1)^2
\\
2 &= 1^2+1
\\
2 &= 2
\end{aligned}
$$

따라서 n = 1 일 때 성립한다.

56-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
F_{k-1}F_{k+1} &= F_k^2+(-1)^k
\end{aligned}
$$

56-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$
\begin{aligned}
F_{k}F_{k+2} &= F_{k+1}^2+(-1)^{k+1}
\\
F_{k}F_{k+2} &= F_{k+1}^2+(-1)^{k+1}
\\
(F_{k+1}-F_{k-1})(F_{k+1}+F_{k}) &= F_{k+1}^2+(-1)^{k+1}
\\
F_{k+1}^2 + F_{k+1}F_k -F_{k-1}F_{k+1} -F_{k-1}F_{k} &= F_{k+1}^2+(-1)^{k+1}
\\
F_{k+1}F_k -F_{k-1}F_{k+1} -F_{k-1}F_{k} &= (-1)^{k+1}
\\
F_{k+1}F_k -(F_k^2+(-1)^k) -F_{k-1}F_{k} &= (-1)^{k+1}
\\
F_{k+1}F_k -F_k^2 -F_{k-1}F_{k} &= 0
\\
F_{k+1}-F_k -F_{k-1} &= 0
\\
F_{k+1} &= F_k +F_{k-1}
\\
\end{aligned}
$$

따라서 k+1일 때 성립한다.