×

# 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{eqnarray} 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{eqnarray}$

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{eqnarray} 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{eqnarray}$

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{eqnarray} \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{eqnarray}$

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{eqnarray} \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{eqnarray}$

Notice

$\begin{eqnarray} &\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{eqnarray}$

Substituting again we get

$\begin{eqnarray} \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{eqnarray}$

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

Note by Fahim Shahriar Shakkhor
2 years ago

Sort by:

Problem 3 :

We note that for $$i \in N$$ , $F_i.F_{i+1} - F_{i-1}.F_i$ $= F_i(F_{i+1}-F_{i-1})$ $= F^{2}_i$ .

Also note that $$F_0 = 0$$

Now we have to do some manual labour , we add,

$F^{2}_1 = F_1 . F_2$

$F^{2}_2 = F_2 . F_3 - F_1 . F_2$

$F^{2}_3 = F_3 . F_4 - F_2 . F_3$

$\text{and so on}$

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

Therefore we get $\sum_{i=0}^{n} F^{2}_i = F_n . F_{n+1}$ · 1 year, 8 months ago

There's a typo in the second line of the solution. It should be $$F_i(F_{i+1}-F_{i-1})=F_i^2$$ · 1 year, 8 months ago

Thanks dude, I've edited it . · 1 year, 8 months ago

Good observation +1 · 1 year, 8 months ago

Problem 1 -

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

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

$$\phi_2^2 - 1 = \left(\dfrac{1- \sqrt{5}}{2} \right)^2 - 1 = \dfrac{3 - \sqrt{5}}{2} - 1 = \dfrac{1 - \sqrt{5}}{2} = \phi_2$$

$$\displaystyle \sum_{i=0}^n F_{2 i + 1 } = \sum_{i=0}^n \dfrac{ \phi_1^{2i + 1} - \phi_2^{2i + 1}}{\sqrt{5}}$$

$$= ~ \dfrac{1}{\sqrt{5}} \left( \displaystyle \phi_1 \sum_{i=0}^n \phi_1^{2i} - \phi_2 \sum_{i=0}^n\phi_2^{2i}\right)$$

$$= ~ \dfrac{1}{\sqrt{5}} \left(\phi_1 \times \dfrac{ \phi_1^{2n + 2} - 1}{ \phi_1^{2} - 1} - \phi_2 \times\dfrac{ \phi_2^{2n + 2} - 1}{ \phi_2^{2} - 1} \right)$$

$$= ~ \dfrac{1}{\sqrt{5}} \left( \phi_1^{2i + 2} - 1\right) - \left( \phi_2^{2i + 2} - 1 \right)$$

$$= ~ F_{2n + 2}$$

Problem 2 - $$n > m$$ thus $$m = 2n ~ or ~m = 2n + 1$$

taking the cases , we see that it is divisible. · 1 year, 8 months ago

Regarding the solution you specified for Problem 2:

What happens if we take $$m=3$$ and $$n=9$$? We can see that $$m\mid n$$ and it obeys the assumption you made (without loss of generality) but it doesn't fall in any of the two cases you specified. · 1 year, 7 months ago

Thanks for noticing. · 1 year, 7 months ago

Excellent work !!! Respect man !!! · 1 year, 7 months ago

I would like to suggest a $$\text{problem}$$ of my own: Prove that for all $$|x| < \phi^{-1}$$,

$\frac{x}{1-x-x^{2}} = \sum_{k=0}^{\infty} F_{k}x^{k}$ · 1 year, 8 months ago

That's actually the generating function for Fibonacci series. Here's my solution:

Let $$F(x)$$ be the generating function for the fibonacci series, then

$F(x) = F_0 +F_1 x+ F_2 x^2 + F_3 x^3 +\ldots$

We know that $$F_{n} - F_{n-1} - F_{n-2} = 0$$. Therefore,

$xF(x) = F_0x +F_1 x^2+ F_2 x^3 + F_3 x^4 +\ldots$

$\text{and}\ x^2F(x) = F_0x^2 +F_1 x^3+ F_2 x^4 + F_3 x^5 +\ldots$

Now we observe that,

$\begin{eqnarray} F(x)-xF(x)-x^2F(x) & = & F_0 +F_1 x+ F_2 x^2 + F_3 x^3 +\ldots \\ & & \quad - F_0x - F_1 x^2 - F_2 x^3 - F_3 x^4 -\ldots \\ & & \quad \quad \quad - F_0x^2 - F_1 x^3 - F_2 x^4 - F_3 x^5 - \ldots \\ & & \\ & = & F_0 +(F_1-F_0) x+ (F_2-F_1-F_0) x^2 + (F_3-F_2-F_1) x^3 + (F_4-F_3-F_2) x^4 + \ldots \end{eqnarray}$

Now, first we observe that the coefficient of $$x^k$$ is $$0$$ $$\forall k \leq 2$$ and also, we substitute $$F_0 = 0,\ F_1 =1$$. Thus,

$(1-x-x^2)F(x) = 0 + x + 0x^2 + 0x^3 + 0x^4 + \ldots$

$\Rightarrow F(x) = \frac{x}{1-x-x^2}$

$\Rightarrow \sum_{k=0}^\infty F_k x^k = \frac{x}{1-x-x^2}$ · 1 year, 7 months ago

You missed writing the term $$(-F_0 x)$$ in the line where you grouped the coefficients of the terms before substitution of values took place. It doesn't matter much though since $$F_0=0$$. · 1 year, 7 months ago

oh, yes! Thanks for pointing out, I'll edit it. · 1 year, 7 months ago

Another suggestion that I'd like to make is to shift the third line of the sum $$(F(x)-xF(x)-x^2F(x))$$ a little more to the right as follows:

$\begin{eqnarray} F(x)-xF(x)-x^2F(x) & = & F_0 +F_1 x+ F_2 x^2 + F_3 x^3 +\ldots \\ & & \quad - F_0x - F_1 x^2 - F_2 x^3 - F_3 x^4 -\ldots \\& & \quad\quad\quad~~ - F_0x^2 - F_1 x^3 - F_2 x^4 - F_3 x^5 - \ldots \\ & & \\ & = & F_0 +(F_1-F_0) x+ (F_2-F_1-F_0) x^2 + (F_3-F_2-F_1) x^3 + (F_4-F_3-F_2) x^4 + \ldots \end{eqnarray}$ · 1 year, 7 months ago

Done!

Thanks. · 1 year, 7 months ago

Hi Kishlaya , I had sent you an e-mail to your outlook account , did you receive it ? · 1 year, 7 months ago

Let me check.

EDIT : Got it. · 1 year, 7 months ago

Beautiful proof a far better than mine's · 1 year, 7 months ago

\begin{align} \frac x{1-x-x^2}&=\sum^\infty_{k=1}F_kx^k\\ x&=(1-x-x^2)\sum^\infty_{k=1}F_kx^k\\ x&=\sum^\infty_{k=1}F_kx^k-\sum^\infty_{k=1}F_kx^{k+1}-\sum^\infty_{k=1}F_kx^{k+2}\\ x&=F_1x+F_2x^2-F_1x^2+\sum^\infty_{k=3}(F_k-F_{k-1}-F_{k-2})x^k\\ x&=F_1x+(F_2-F_1)x^2+\sum^\infty_{k=3}(F_k-F_{k-1}-F_{k-2})x^k\\ \end{align}

$$F_1 = 1 , F_2 - F_1 = 0 , F_k-F_{k-1}-F_{k-2} = 0 ~by~definition$$

$$x = x$$

$$L.H.S=R.H.S$$

$$H.P$$ · 1 year, 8 months ago

What happens when $$|x|\geq \phi^{-1}$$ ? Does the given equation still hold true? Your solution seems incomplete to me since it doesn't make any conclusion regarding the constraint and doesn't specify whether it fails for $$|x|\geq \phi^{-1}$$ or not?! · 1 year, 7 months ago

for infinite summation - $$|x| < 1$$ · 1 year, 7 months ago

$$\phi^{-1}\approx 0.618$$

So, what happens for $$|x|\in [\phi^{-1},1)$$ ? Does the series converge for that part? That's what I'm referring to. The $$|x|\lt 1$$ part is trivial and needs not to be mentioned since the sum is a weighted infinte GP with Fibonacci numbers as coefficients (weights). · 1 year, 7 months ago

Yes it would - $$|\dfrac{a_{n+1}}{a_n}|$$. I did'nt understand your last line that $$|x|<1$$ is trivial and please can you elaborate the weighted part · 1 year, 7 months ago

The fact that you mentioned in the previous comment. I was referring to that. And I used the term "weighted" to say that all the $$x_k$$'s do not equally contribute to the sum. The contribution depends upon the $$F_k$$ coefficients. You must have heard of the Weighted Arithmetic Mean. The "weighted" here means the same as it does there. · 1 year, 7 months ago

The note which I have created I wrote the problems which I created myself , I am adding your's too . Thanks · 1 year, 8 months ago