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

Note by Fahim Shahriar Shakkhor
5 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

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

- 5 years, 1 month ago

Good observation +1

- 5 years, 1 month 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$

- 5 years, 1 month ago

Thanks dude, I've edited it .

- 5 years, 1 month 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.

- 5 years, 1 month 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.

- 5 years, 1 month ago

Thanks for noticing.

- 5 years, 1 month ago

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

- 5 years, 6 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}$

- 5 years, 1 month 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{aligned} 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{aligned}

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

- 5 years, 1 month ago

Beautiful proof a far better than mine's

- 5 years, 1 month ago

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

- 5 years, 1 month ago

Let me check.

EDIT : Got it.

- 5 years, 1 month 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$.

- 5 years, 1 month ago

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

- 5 years, 1 month 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{aligned} 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{aligned}

- 5 years, 1 month ago

Done!

Thanks.

- 5 years, 1 month ago

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

- 5 years, 1 month ago

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

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

- 5 years, 1 month 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?!

- 5 years, 1 month ago

for infinite summation - $|x| < 1$

- 5 years, 1 month ago

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

- 5 years, 1 month 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

- 5 years, 1 month ago

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

- 5 years, 1 month ago

Excellent work !!! Respect man !!!

- 5 years, 1 month ago