An Explanation of the Fibonacci Sequence

Abstract

In this paper, I will examine the properties of Fibonacci Sequence and some identities related to Fibonacci sequence. I will also touch the applications of Fibonacci numbers, recurrence and closed forms of Fibonacci sequence.

Contents

1 Introduction

2 Fibonacci Numbers in Pascal's Triangle

3 Cassini's Identity

4 Difference of Square of Fibonacci Numbers

5 Sum of Odd Fibonacci Numbers

6 Golden Ratio

7 Golden Spiral

8 Fibonacci Recurrence Relation

9 Fibonacci Closed Form

10 Conclusion

1 Introduction

Fibonacci numbers were discovered by Leonardo Pisano. His nickname is Fibonacci. The Fibonacci Sequence is the series of numbers:

0,1,1,2,3,5,8,13,21,34,...

Each number in the sequence is sum of the previous two terms.

u₁ = 1 u₂ = 1 u_n = u_n−1+u_n−2,n > 2

Fibonacci numbers first used in 'rabbit problem'. At the beginning, Fibonacci had one male and one female rabbits. He supposed that, every month. Next month more babies (male and female) were born. The next month these babies were grown and the first pair had two more babies (again male and female) . The next month the two adult pairs each have a pair of baby rabbits and the babies from last month mature. Fibonacci asked how many rabbits a single can produce after a year with this breeding process (rabbits never die, every month each adult pair produces a mixed pair of baby rabbits who mature the next month). Fibonacci asked how many would be formed in a year. Following the Fibonacci sequence perfectly the rabbits reproduction was determined 144 rabbits (Sinha,2017).

Fig.1 rabbit problem diagram

2 Fibonacci Numbers in Pascal's Triangle

The Fibonacci Numbers are also applied in Pascal's Triangle. Entry is sum of the two numbers either side of it, but in the row above. Diagonal sums in Pascal's Triangle are the Fibonacci numbers.

An interesting property of Pascal's Triangle is that its diagonals sum to the Fibonacci sequence, as shown in the picture below:

Fig.2 diagonal sums in Pascal's triangle

The sum of the entries in the nth diagonal of Pascal's triangle is equal to the nth Fibonacci numbers for all positive integers n. Suppose ∑d_n sum of the numbers at nth diagonal and f_n = nth Fibonacci number, n ≥ 0.

Principle of Mathematical Induction will be used for proof.

For n = 0, ∑d₀ = 0, f₀ = 0 (The result is true for n = 0) Assume that ∑d_k = f_k f_k+1 = f_k+ f_k−₁, Property of Fibonacci Sequence f(k) = ∑d_k and f(k−1) = ∑d_k−₁, inductive hypothesis

Therefore, ∑d_k+1 = ∑d_k+∑d_k−1

F₁2+F₂2 = 12

3 Cassini's Identity

Cassini(1625-1712) is the astronomer who found Cassini Identity. Cassini's identity is a mathematical identity for Fibonacci sequence.

The history of science is silent as to why Cassini took such a great interest in Fibonacci numbers. Most likely it was simply a hobby of the Great astronomer. At that time many serious scientist took a great interest in Fibonacci numbers and the golden mean. These mathematical objects were also a hobby of Cassini's contemporary, Kepler(Stahbov,2012).

Fn+1Fn

Proof by induction

Let's check that if the identity works for n=1.

For n = 1,2×1−1² = 1 = 1¹⁺¹

Assume that the identity works for some n=k,

Fk+1Fkk+1

We want to show that also

Fk+2Fkk+2

To prove this we will establish

F_k

Here is how:

F_k²F_kF_k−1−F_kF_k−1−F_k+1F_k−1

= F_k+1F_k−F_k−F_kF_k−1−F_k+1F_k−1

= F_k+1F_k−2F_kF_k

(F_k+1+F_k)F_k−(F_k+F_k−1)²

4 Difference of Square of Fibonacci Numbers

The difference of the square of two consecutive Fibonacci numbers is equal to the product of two Fibonacci numbers.

F FnFn−1

Proof

Use the following identities.

F FnFn−1

F_n+1 = Fn+F_n−1

an = F2n−1 b_n = 2F_nF_n−1

cn

a2_n = b2_n+c2_n

FFnFn

FF_nF_n−1)²

Consider separately

FF_nF_n−1)².

FF_nF_n−1)²

F_nF_n−1)²−(2F_nF_n−1)²

FnFnFnFn−1)2

FFnFn−1

= (F_n+F_n−1)⁴−4(F_n+F_n−1)F_nF_n−1

FnFFnFn2−1

FnFFnFn2−1

After simplifying this by using identities

We can show that FF_nF_n−₁)² = (F_nF_n−₁)²

Hence F(F_nF_n−1)² So, F F_nF_n−1.

5 Sum of Odd Fibonacci Numbers

The sum of odd Fibonacci numbers is also a Fibonacci number.

F₁+F₃+F₅+...+F_2n−1 = F_2n,F₀ = 0,F₁ = 1

Proof by induction. base case: for n=1 F₁ = 1 = F₂ This proves that the base case is true.

inductive step: Lets assume that it is true for some n ≥ 1.

F₁+F₃+F₅+...+F_2n−1 = F_2n

We need to prove that it is also true for n+1.

F₁+F₃+F₅+...+F₂(_n+1)−1 = (F₁+F₃+F₅+...+F_2n−1)+F₂(_n+1)−1

= F2n+^F2(n+1)−1

= F2n+F2n+1

= F2n+2

= ^F2(n+1)

This proves that it is true for n+1. Hence it is true for all n ≥ 1.

6 Golden Ratio

Any Fibonacci number divided by the previous Fibonacci number has a quotient of approximately 1.618034...

F^Fn−ⁿ1 ≈ 1.618034(φ)

Fig.3 ratio of consecutive Fibonacci numbers

The Golden Ratio is also found all throughout the physical universe. Weather patterns, Whirlpool have almost the same form like the golden spiral. Even the Sea Wave sometimes shows almost the same spiral pattern. The three rings of Saturn are designed naturally based on the Golden Ratio. The Galaxy, Milky Way, also has the spiral pattern almost like golden spiral. Relative planetary distances of the Solar System also have the golden ratio properties. (2011)

There is a good change of variable analysis in textbook 'An Introduction to the Analysis of Algorithms' (2013).

a_n = 1/(1+a_n−₁) (2013)

Let's write some terms.

a₀ = 1

a₁ = =

a2 = 1+1+1 = 1+2 =

When we continue, we will see the pattern to continued fractions continues.

a3 = 1+1+1 1 = 1+3 =

1+1

a4 = 1+1 = 1+5 =

1+ 1

1+1

The form a_n ^{= b}_bⁿ⁻n¹ is certainly suggested:

substituting this equation into the recurrences gives

bbn−1 = 1/(1+ bbnn−−21) for n > 1 with b0 = b1 = 1.

n

Dividing both sides by b_n−₁gives

bn−1+¹bn−2 for n > 1 with b₀ = b₁ = 1,

which implies that b_n = F_n+1, the Fibonacci sequence. This argument generalizes to give a way to express general classes of "continues fraction" representations as solutions to recurrences (2013).

7 Golden Spiral

Golden spiral is derived from golden ratio.The growth factor of golden spiral is φ , the golden ratio.

Fig.4 golden spiral

To draw Golden Spiral, draw squares by using Fibonacci sequence. This works by drawing squares which have the side lengths of Fibonacci numbers and combining them.

Golden spiral is used in real life in many areas like art, beauty, clothing, architecture,logos etc.

The Golden ratio is prevalent in Da Vinci's The Annunciation, Madonna with Child and Saints, The Mona Lisa and St. Jerome. He was famous for using the Golden ratio in his works. The Mona Lisa, a well known portrait of a woman with a coy smile, is embedded with Golden rectangles (2018).

Fig.5 The Mona Lisa

8 Fibonacci Recurrence Relation

We can find recurrence formula of Fibonacci sequence by using its definition.

Fn = F_n−1+F_n−2 xn = xn−1+xn−2

We will divide each term by xⁿ⁻²

x² = x+1 x²−x−1 = 0

We will solve the quadratic equation by using quadratic formula

x x

F_n n

F₀ = 0,F₁ = 1

c c

F_n

Fibonacci Recurrence Relation

9 Fibonacci Closed Form

Let G(z) be closed form of Fibonacci sequence.

G(z) = F₀+F₁z+F₂z²+F₃z³+F₄z⁴+...

Now let's find zG(z) and z²G(z) by multiplying G(z) by z and z².

zG(z) = F₀z+F₁z²+F₂z³+F₃z⁴+F₄z⁵+... z²G(z) = F₀z²+F₁z³+F₂z⁴+F₃z⁵+F₄z⁶+...

Now we will find the difference of G(z)−zG(z)−z²G(z)

(1−z−z²)G(z) = F₀+(F₁−F₀)z+(F₂−F₁−F₀)z²+(F₃−F₂−F₁)z³+...

We know that F₁ = F₂ = 1

so

F₂−F₁ = 0.

Also since for n > 2 we have that

F_n = F_n−1+F_n−2 then

F₃−F₂−F₁ = 0,F₄−F₃−F₂ = 0,...,

F_n+1−F_n−F_n−1 = 0.

Therefore:

(1−z−z²)G(z) = z

This will give us the closed form of Fibonacci sequence as:

G(z) = 1−z^z−z₂

10 Conclusion

In conclusion, studying Fibonacci numbers was great experience. It was interesting and joyful to see the harmony of numbers and the beauty they made. I searched the history of Fibonacci numbers, some identities related to Fibonacci numbers and the applications of Fibonacci numbers. Seeing the applications of Fibonacci numbers was eye opening.

References

1. Sinha, Sudipta, 2017, The Fibonacci Numbers and Its Amazing Applications, International Journal of Engineering Science Invention, Volume 6, Issue6

2. Stakhov, Alexey, 2012, A generalization of the Cassini Formula, The International Clubof the Golden Section

3. Akhtaruzzaman, Md , Shafie, Amir A. ,2011, Geometrical Substantiation of Phi, theGolden Ratio and the Baroque of Nature, Architecture, Design and Engineering International Journal of Arts

4. Thapa ,Gyan Bahadur , Thapa , Rena, 2018, Journal of the Institute of Engineering, TheRelation of Golden Ratio, Mathematics and Aesthetics

5. Sedgewick, R., & Flajolet, P. (2013). An introduction to the analysis of Algorithms, (Second Edition). Addision-Wesley Professional.

6. Wiki page Golden Ratio. https://en.wikipedia.org/wiki/Goldenspiral

7. Fig.1 Knott, Ron, 2016, Fibonacci Numbers and Nature. http://www.maths.surrey.ac.uk/hostedsites/R.Knott/Fibonacci/fibnat.html

8. Fig.2 https://www.maplesoft.com/applications/view.aspx?SID=3617view=html

9. Fig.3 Ancient Architecture(ratio of consecutive Fibonacci numbers). https://nzmaths.co.nz/resource/anciarchitecture

10. Fig.4. Wikimedia commons. https://commons.wikimedia.org/wiki/File:FibonacciSpiral.svg

11. Fig.5. The Mona Lisa https://thefibonaccisequence.weebly.com/mona-lisa.html