Fibonacci and Fibonacci

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

The Fibonacci Sequence\text{Fibonacci Sequence} is a sequence of integers where the first 2\displaystyle 2 term are 0\displaystyle 0 and 1\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,... 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377, ...

The nn-th Fibonacci number is denoted by FnF_n and the sequence is defined by the recurrence relation

Fn=Fn1+Fn2.F_n = F_{n-1} + F_{n-2}.

Here, F0=0,F1=1,F2=F1+F0=1F_0 = 0,\enspace F_1 = 1,\enspace F_2 = F_1 + F_0 = 1 etc.

Theorem:\text{Theorem:}

Fn=(1+52)n(152)n5F_n = \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{n}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{n} }{\sqrt{5}}

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

Fk=(1+52)k(152)k5.F_k = \dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{k}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{k} }{\sqrt{5}}.

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

(1+52)0(152)05=0=F0.\dfrac{ \left( \dfrac{1+\sqrt{5}}{2} \right)^{0}- \left(\dfrac{1-\sqrt{5}}{2} \right)^{0} }{\sqrt{5}} = 0 = F_0.

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

(1+52)1(152)15=55=1=F1.\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.

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

Fn=Fn2+Fn1=(1+52)n2(152)n25+(1+52)n1(152)n15=(1+52)n2(1+1+52)(152)n2(1+152)5.\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

(1+52)2=1+(1+52),     (152)2=1+(152).\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.

Fn=(1+52)n2(1+52)2(152)n2(152)25=(1+52)n(152)n5\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.

Example 1:\text{Example 1:} Prove that for all nn

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

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

i=0nFi=i=0nϕ1iϕ2i5=15(i=0nϕ1ii=0nϕ2i)=15(ϕ1n+11ϕ11ϕ2n+11ϕ21)\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

ϕ1+ϕ2=1+52+152=1,\phi_1 + \phi_2 = \dfrac{1+\sqrt{5}}{2} + \dfrac{1-\sqrt{5}}{2} = 1,

 ϕ11=ϕ2,     ϕ21=ϕ1.\therefore ~\phi_1 -1 = -\phi_2, ~~~~~\phi_2 -1 = -\phi_1.

Substituting

i=0nFi=15(ϕ1n+11ϕ2ϕ2n+11ϕ1)=15(ϕ2n+11ϕ1ϕ1n+11ϕ2)=15(ϕ2n+2ϕ2ϕ1n+2+ϕ1ϕ1ϕ2)=15(ϕ2n+2ϕ1n+2ϕ1ϕ2+ϕ1ϕ2ϕ1ϕ2).\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

ϕ1ϕ2=(1+52)(152)=154=1ϕ1ϕ2=(1+52)(152)=252=5.\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

i=0nFi=15(ϕ2n+2ϕ1n+21+51)=ϕ1n+2ϕ2n+251=Fn+21.\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.

Problem 1:\text{Problem 1:} Prove that for all nn

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

Problem 2:\text{Problem 2:} Prove that for all integers mm and nn, if mnm\mid n then FmFn.F_m\mid F_n.

Problem 3:\text{Problem 3:} Prove that for all nn

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

Note by Fahim Shahriar Shakkhor
4 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Excellent work !!! Respect man !!!

Soutrik Bandyopadhyay - 4 years, 6 months ago

Log in to reply

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

x1xx2=k=0Fkxk\frac{x}{1-x-x^{2}} = \sum_{k=0}^{\infty} F_{k}x^{k}

Jake Lai - 4 years, 7 months ago

Log in to reply

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

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

F(x)=F0+F1x+F2x2+F3x3+F(x) = F_0 +F_1 x+ F_2 x^2 + F_3 x^3 +\ldots

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

xF(x)=F0x+F1x2+F2x3+F3x4+xF(x) = F_0x +F_1 x^2+ F_2 x^3 + F_3 x^4 +\ldots

and x2F(x)=F0x2+F1x3+F2x4+F3x5+\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,

F(x)xF(x)x2F(x)=F0+F1x+F2x2+F3x3+F0xF1x2F2x3F3x4F0x2F1x3F2x4F3x5=F0+(F1F0)x+(F2F1F0)x2+(F3F2F1)x3+(F4F3F2)x4+\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 xkx^k is 00 k2\forall k \leq 2 and also, we substitute F0=0, F1=1F_0 = 0,\ F_1 =1. Thus,

(1xx2)F(x)=0+x+0x2+0x3+0x4+(1-x-x^2)F(x) = 0 + x + 0x^2 + 0x^3 + 0x^4 + \ldots

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

k=0Fkxk=x1xx2\Rightarrow \sum_{k=0}^\infty F_k x^k = \frac{x}{1-x-x^2}

Kishlaya Jaiswal - 4 years, 6 months ago

Log in to reply

You missed writing the term (F0x)(-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 F0=0F_0=0.

Prasun Biswas - 4 years, 6 months ago

Log in to reply

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

Kishlaya Jaiswal - 4 years, 6 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)x2F(x))(F(x)-xF(x)-x^2F(x)) a little more to the right as follows:

F(x)xF(x)x2F(x)=F0+F1x+F2x2+F3x3+F0xF1x2F2x3F3x4  F0x2F1x3F2x4F3x5=F0+(F1F0)x+(F2F1F0)x2+(F3F2F1)x3+(F4F3F2)x4+\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}

Prasun Biswas - 4 years, 6 months ago

Log in to reply

@Prasun Biswas Done!

Thanks.

Kishlaya Jaiswal - 4 years, 6 months ago

Log in to reply

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

A Brilliant Member - 4 years, 6 months ago

Log in to reply

@A Brilliant Member Let me check.

EDIT : Got it.

Kishlaya Jaiswal - 4 years, 6 months ago

Log in to reply

Beautiful proof a far better than mine's

U Z - 4 years, 6 months ago

Log in to reply

x1xx2=k=1Fkxkx=(1xx2)k=1Fkxkx=k=1Fkxkk=1Fkxk+1k=1Fkxk+2x=F1x+F2x2F1x2+k=3(FkFk1Fk2)xkx=F1x+(F2F1)x2+k=3(FkFk1Fk2)xk \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}

F1=1,F2F1=0,FkFk1Fk2=0 by definitionF_1 = 1 , F_2 - F_1 = 0 , F_k-F_{k-1}-F_{k-2} = 0 ~by~definition

x=x x = x

L.H.S=R.H.SL.H.S=R.H.S

H.PH.P

U Z - 4 years, 7 months ago

Log in to reply

What happens when xϕ1|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ϕ1|x|\geq \phi^{-1} or not?!

Prasun Biswas - 4 years, 6 months ago

Log in to reply

@Prasun Biswas for infinite summation - x<1|x| < 1

U Z - 4 years, 6 months ago

Log in to reply

@U Z ϕ10.618\phi^{-1}\approx 0.618

So, what happens for x[ϕ1,1)|x|\in [\phi^{-1},1) ? Does the series converge for that part? That's what I'm referring to. The x<1|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 - 4 years, 6 months ago

Log in to reply

@Prasun Biswas Yes it would - an+1an |\dfrac{a_{n+1}}{a_n}|. I did'nt understand your last line that x<1|x|<1 is trivial and please can you elaborate the weighted part

U Z - 4 years, 6 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 xkx_k's do not equally contribute to the sum. The contribution depends upon the FkF_k coefficients. You must have heard of the Weighted Arithmetic Mean. The "weighted" here means the same as it does there.

Prasun Biswas - 4 years, 6 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 - 4 years, 7 months ago

Log in to reply

Problem 3 :

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

Also note that F0=0F_0 = 0

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

F12=F1.F2 F^{2}_1 = F_1 . F_2

F22=F2.F3F1.F2 F^{2}_2 = F_2 . F_3 - F_1 . F_2

F32=F3.F4F2.F3 F^{2}_3 = F_3 . F_4 - F_2 . F_3

and so on \text{and so on}

Fn2=Fn.Fn+1Fn1.Fn F^{2}_n = F_n . F_{n+1} - F_{n-1} . F_{n}


Therefore we get i=0nFi2=Fn.Fn+1 \sum_{i=0}^{n} F^{2}_i = F_n . F_{n+1}

A Brilliant Member - 4 years, 7 months ago

Log in to reply

There's a typo in the second line of the solution. It should be Fi(Fi+1Fi1)=Fi2F_i(F_{i+1}-F_{i-1})=F_i^2

Prasun Biswas - 4 years, 7 months ago

Log in to reply

Thanks dude, I've edited it .

A Brilliant Member - 4 years, 7 months ago

Log in to reply

Good observation +1

U Z - 4 years, 7 months ago

Log in to reply

Problem 1 -

ϕ1=1+52,ϕ2=152\phi_1 = \dfrac{1+\sqrt{5}}{2} , \phi_2 = \dfrac{1-\sqrt{5}}{2}

ϕ121=(1+52)21=3+521=1+52=ϕ1 \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

ϕ221=(152)21=3521=152=ϕ2 \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

i=0nF2i+1=i=0nϕ12i+1ϕ22i+15 \displaystyle \sum_{i=0}^n F_{2 i + 1 } = \sum_{i=0}^n \dfrac{ \phi_1^{2i + 1} - \phi_2^{2i + 1}}{\sqrt{5}}

= 15(ϕ1i=0nϕ12iϕ2i=0nϕ22i) = ~ \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)

= 15(ϕ1×ϕ12n+21ϕ121ϕ2×ϕ22n+21ϕ221) = ~ \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)

= 15(ϕ12i+21)(ϕ22i+21) = ~ \dfrac{1}{\sqrt{5}} \left( \phi_1^{2i + 2} - 1\right) - \left( \phi_2^{2i + 2} - 1 \right)

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

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

taking the cases , we see that it is divisible.

U Z - 4 years, 7 months ago

Log in to reply

Regarding the solution you specified for Problem 2:

What happens if we take m=3m=3 and n=9n=9? We can see that mnm\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 - 4 years, 6 months ago

Log in to reply

Thanks for noticing.

U Z - 4 years, 6 months ago

Log in to reply

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

Fahim Shahriar Shakkhor - 4 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...