Fibonacci and Fibonacci

Today I am writing about a well known and interesting sequence, that is $\text{Fibonacci Sequence}$. Let us have a short introduction to it.

The $\text{Fibonacci Sequence}$ is a sequence of integers where the first $\displaystyle 2$ term are $\displaystyle 0$ and $\displaystyle 1$, and each subsequent term is the sum of the previous two numbers.

$0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377, ...$

The $n$-th Fibonacci number is denoted by $F_n$ and the sequence is defined by the recurrence relation

$F_n = F_{n-1} + F_{n-2}.$

Here, $F_0 = 0,\enspace F_1 = 1,\enspace F_2 = F_1 + F_0 = 1$ etc. $$

$\text{Theorem:}$

$F_n = \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{n} }{\sqrt{5}}$

$\text{Proof:}$ We will use strong induction to prove it. Let $n$ be an arbitrary natural number and suppose that for all $k < n$

$F_k = \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{k}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{k} }{\sqrt{5}}.$

$\text{Case 1.}\enspace n=0.$ Then

$\dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{0}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{0} }{\sqrt{5}} = 0 = F_0.$

$\text{Case 2.}\enspace n=1.$ Then

$\dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{1}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{1} }{\sqrt{5}} = \frac{\sqrt5}{\sqrt5} = 1 = F_1.$

$\text{Case 3.}\enspace n\geq 2.$ Now applying the inductive hypothesis to $n-2$ and $n-1$, we get

$\begin{aligned} F_n &=& F_{n-2} + F_{n-1} \\ \\ &=&\dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n-2}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{n-2} }{\sqrt{5}} + \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n-1}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{n-1} }{\sqrt{5}} \\ \\ &=& \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n-2} \left(1+\frac{1+\sqrt{5}}{2}\right) - \left( \dfrac{1-\sqrt{5}}{2} \right)^{n-2} \left(1+\frac{1-\sqrt{5}}{2}\right)}{\sqrt{5}}. \end{aligned}$

Note that

$\left( \dfrac{1+\sqrt{5}}{2} \right)^{2} = 1 +\left( \dfrac{1+\sqrt{5}}{2} \right), ~~~~~\left( \dfrac{1-\sqrt{5}}{2} \right)^{2} = 1 +\left( \dfrac{1-\sqrt{5}}{2} \right).$

Hence.

$\begin{aligned} F_n &=& \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n-2} \left(\dfrac{1+\sqrt{5}}{2}\right)^2 - \left( \dfrac{1-\sqrt{5}}{2} \right)^{n-2} \left(\dfrac{1-\sqrt{5}}{2}\right)^2}{\sqrt{5}} \\ \\ &=&\dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{n} }{\sqrt{5}} \end{aligned}$

Now we are going to deal with some problems. Before that here is an example for you.

$\text{Example 1:}$ Prove that for all $n$

$\displaystyle \sum_{i=0}^{n}F_i = F_{n+2} - 1.$

$\text{Solution:}$ Let $\phi_1 = \dfrac{1+\sqrt{5}}{2}$ and $\phi_2 = \dfrac{1-\sqrt{5}}{2}$.

$\begin{aligned} \sum_{i=0}^{n} F_i &=&\sum_{i=0}^{n} \dfrac{\phi_1^i-\phi_2^i}{\sqrt{5}} \\ \\ &=& \dfrac{1}{\sqrt{5}} \left(\sum_{i=0}^{n} \phi_1^i - \sum_{i=0}^{n} \phi_2^i \right) \\ \\ &=&\displaystyle \dfrac{1}{\sqrt{5}} \left( \dfrac{\phi_1^{n+1} -1 }{\phi_1-1} - \dfrac{\phi_2^{n+1} -1 }{\phi_2-1} \right) \end{aligned}$

Note that

$\phi_1 + \phi_2 = \dfrac{1+\sqrt{5}}{2} + \dfrac{1-\sqrt{5}}{2} = 1,$

$\therefore ~\phi_1 -1 = -\phi_2, ~~~~~\phi_2 -1 = -\phi_1.$

Substituting

$\begin{aligned} \sum_{i=0}^{n} F_i &=& \dfrac{1}{\sqrt{5}} \left( \dfrac{\phi_1^{n+1} -1 }{-\phi_2} - \dfrac{\phi_2^{n+1} -1 }{-\phi_1} \right) \\ \\ &=& \dfrac{1}{\sqrt{5}} \left(\dfrac{\phi_2^{n+1} -1 }{\phi_1}-\dfrac{\phi_1^{n+1} -1 }{\phi_2}\right) \\ \\ &=& \dfrac{1}{\sqrt{5}} \left( \dfrac{\phi_2^{n+2}-\phi_2-\phi_1^{n+2}+\phi_1}{\phi_1\phi_2} \right) \\ \\ &=& \dfrac{1}{\sqrt{5}} \left( \dfrac{\phi_2^{n+2}-\phi_1^{n+2}}{\phi_1\phi_2}+\dfrac{\phi_1-\phi_2}{\phi_1\phi_2} \right). \end{aligned}$

Notice

$\begin{aligned} &\phi_1\phi_2 &=& \left(\dfrac{1+\sqrt{5}} {2}\right)\left(\dfrac{1-\sqrt{5}}{2}\right) = \dfrac{1-5}{4} = -1 \\ \\ &\phi_1-\phi_2 &=& \left(\dfrac{1+\sqrt{5}} {2}\right)-\left(\dfrac{1-\sqrt{5}}{2}\right) = \dfrac{2\sqrt5}{2} = \sqrt5. \end{aligned}$

Substituting again we get

$\begin{aligned} \sum_{i=0}^{n}F_i &=&\dfrac{1}{\sqrt{5}} \left( \dfrac{\phi_2^{n+2}-\phi_1^{n+2}}{-1}+\dfrac{\sqrt{5}}{-1} \right) \\ \\ &=& \dfrac{\phi_1^{n+2} -\phi_2^{n+2}}{\sqrt{5}}-1 \\ \\ &=& F_{n+2} - 1. \end{aligned}$

Here I'm giving some problems for exercise. I hope you will try them.

$\text{Problem 1:}$ Prove that for all $n$

$\sum_{i=0}^{n}F_{2i+1} = F_{2n+2}.$

$\text{Problem 2:}$ Prove that for all integers $m$ and $n$, if $m\mid n$ then $F_m\mid F_n.$

$\text{Problem 3:}$ Prove that for all $n$

$\sum_{i=0}^{n}F_{i}^2 = F_nF_{n+1}.$