Waste less time on Facebook — follow Brilliant.
×

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
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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

Azhaghu Roopesh M - 2 years, 8 months ago

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

Prasun Biswas - 2 years, 8 months ago

Log in to reply

Thanks dude, I've edited it .

Azhaghu Roopesh M - 2 years, 8 months ago

Log in to reply

Good observation +1

U Z - 2 years, 8 months ago

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.

U Z - 2 years, 8 months ago

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.

Prasun Biswas - 2 years, 7 months ago

Log in to reply

Thanks for noticing.

U Z - 2 years, 7 months ago

Log in to reply

Excellent work !!! Respect man !!!

Soutrik Bandyopadhyay - 2 years, 7 months ago

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

Jake Lai - 2 years, 8 months ago

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

Kishlaya Jaiswal - 2 years, 7 months ago

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

Prasun Biswas - 2 years, 7 months ago

Log in to reply

@Prasun Biswas oh, yes! Thanks for pointing out, I'll edit it.

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

@Kishlaya Jaiswal 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}\]

Prasun Biswas - 2 years, 7 months ago

Log in to reply

@Prasun Biswas Done!

Thanks.

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

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

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

@Azhaghu Roopesh M Let me check.

EDIT : Got it.

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

Beautiful proof a far better than mine's

U Z - 2 years, 7 months ago

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

U Z - 2 years, 8 months ago

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

Prasun Biswas - 2 years, 7 months ago

Log in to reply

@Prasun Biswas for infinite summation - \(|x| < 1\)

U Z - 2 years, 7 months ago

Log in to reply

@U Z \(\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).

Prasun Biswas - 2 years, 7 months ago

Log in to reply

@Prasun Biswas 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

U Z - 2 years, 7 months ago

Log in to reply

@U Z 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.

Prasun Biswas - 2 years, 7 months ago

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

U Z - 2 years, 8 months ago

Log in to reply

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...