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}.\]

## Comments

Sort by:

TopNewestProblem 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} \]

Log in to reply

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\)

Log in to reply

Thanks dude, I've edited it .

Log in to reply

Good observation +1

Log in to reply

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.

Log in to reply

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.

Log in to reply

Thanks for noticing.

Log in to reply

Excellent work !!! Respect man !!!

Log in to reply

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}\]

Log in to reply

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}\]

Log in to reply

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\).

Log in to reply

Log in to reply

\[\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}\]

Log in to reply

Thanks.

Log in to reply

Hi Kishlaya , I had sent you an e-mail to your outlook account , did you receive it ?

Log in to reply

EDIT : Got it.

Log in to reply

Beautiful proof a far better than mine's

Log in to reply

\[ \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\)

Log in to reply

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?!

Log in to reply

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

The note which I have created I wrote the problems which I created myself , I am adding your's too . Thanks

Log in to reply

Brilli members, you can add solution to the given problems here.

Log in to reply