# Table of Contents

The Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones.

10, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

## History

- Leonardo Bonacci, Italian Mathemetician from the Republic of Pisa studied with Muslim schoolmaster who introduced him to the Hindu-Arabic system of Enumeration along with computation. later he investigated various arithmetic sytems in Egypt, France, Greece, Rome and Syria.
- In 1202, he published his Liber Abaci (Book of Abacus), Practice of Geometry (1220), Book of Square Numbers (1225) and others etc.
- This sequence of numbers (0,1,1,2,3,5,8,13,21,34...) called Fibonacci Sequence which is contraction of Filius Bonacci (son of Bonacci).

### Problem of Rabbits

Problem is about a person who has a pair of newborn rabbits (different gender). here problem to determine the numbers of pairs after a year. at the end of each month, a newborn pair grows to maturity.

### Rabbits Population per year.

Newborn | Matured | Total | |
---|---|---|---|

Jan 1 | 1 | 0 | 1 |

Feb 1 | 0 | 1 | 1 |

Mar 1 | 1 | 1 | 2 |

Apr 1 | 1 | 2 | 3 |

May 1 | 2 | 3 | 5 |

Jun 1 | 3 | 5 | 8 |

Jul 1 | 5 | 8 | 13 |

Aug 1 | 8 | 13 | 21 |

Sep 1 | 13 | 21 | 34 |

Oct 1 | 21 | 34 | 55 |

Nov 1 | 34 | 55 | 89 |

Dec 1 | 55 | 89 | 144 |

Jan 1 | 89 | 144 | 233 |

## Properties

Finding the great common divisor of F5 = 5 and F6 = 8 is 1. This is due to the fact that only positive integer that divide F5 = 5 are 1 and 5 (denoted as gcd(F5, F6) = 1 likewise, F6 = 8 are 1,2,4 and 8 (denoted as gcd(F9, F10) = 1) there are common properties available. lets look at them.

- For n>=0, GCD(F
_{n}, F_{n+1}) = 1 - For n>=0, GCD(F
_{n}, F_{n+2}) = 1 - Sum of any six consecutive fibonacci numbers is divisible by 4
- Sum of 10 consecutive fibonacci numbers is divisible by 11
- and there is five more properties until 9.

## Solutions

Let's take a problem to find a N-th value of the Fibonacci sequence? There is various kinds of approaches in order to get this sequence and there is many solutions available. lets see each of them with solutions written in javascript. Before, lets look at the formulae.

- F
_{0}= 0, F_{1}= 1 (initial conditions) - Fn = F
_{n-1}+ F_{n-2}, n>=2 (Recurrence Relation)

### 1. Recursive Approach

Basically, this approach call itself creating more and more branches of the tree until it hits the base case. Below is the recursive solution in Javascript.

**Time Complexity:**O(2

^{n}) - Exponential

**Space Complexity:**O(n) - Linear (considering function call stack size, otherwise O(1) Constant.)

1function fib_1(n) {2 if (n < 2) {3 return n4 }5 return fib_1(n - 1) + fib_1(n - 2)6}

### 2. Dynamic Programming

- Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
- The idea is to simply store the results of sub problems to prevent re-computations of same inputs.
- This helps to reduces time complexities from exponential to polynomial.

**Time Complexity:** O(n).

**Space Complexity:** O(1).

1function fib_2(n) {2 let a = 0, b = 1, c, i;3 if (n == 0)4 return a;5 for (i = 2; i <= n; i++) {6 c = a + b;7 a = b;8 b = c;9 }10 return b;11}

### 3. Power of Matrix Approach

**Time Complexity:** O(Logn).

**Space Complexity:** O(1) or O(Logn) on function call stack size consideration.

1function fib_3(n) {2 const F = [[1, 1], [1, 0]];3 if (n == 0)4 return 0;5 power(F, n - 1);6 return F[0][0];7}8// Helper function that multiplies 29// matrices F and M of size 2*2, and10// puts the multiplication result11// back to F[][]12function multiply(F, M) {13 const x = F[0][0] * M[0][0] + F[0][1] * M[1][0];14 const y = F[0][0] * M[0][1] + F[0][1] * M[1][1];15 const z = F[1][0] * M[0][0] + F[1][1] * M[1][0];16 const w = F[1][0] * M[0][1] + F[1][1] * M[1][1];17 F[0][0] = x;18 F[0][1] = y;19 F[1][0] = z;20 F[1][1] = w;21}22// Helper function that calculates F[][]23// raise to the power n and puts the24// result in F[][]25function power(F, n) {26 const M = [[1, 1], [1, 0]];27 // n - 1 times multiply the28 // matrix to {{1,0},{0,1}}29 for (let i = 2; i <= n; i++)30 multiply(F, M);31}32// Optimized version of power() in method 4 */33function power(F, n) {34 if (n == 0 || n == 1)35 return;36 const M = [[1, 1], [1, 0]];37 power(F, n / 2);38 multiply(F, F);39 if (n % 2 != 0)40 multiply(F, M);41}

### 4 Using Binet's Formula

Binet formula, sums, combinatorial representations and generating function of the generalized Fibonacci -numbers.

**Time Complexity:** O(logn), this is because calculating phi^n takes logn time.

**Space Complexity:** O(1)

1function fib_4(n) {2 let phi = (1 + Math.sqrt(5)) / 2;3 return Math.round(Math.pow(phi, n) / Math.sqrt(5));4}

## Other Facts

Let's look at the other facts where we used in real life.

### Planets Activity

Even our planet activities like Rotations period, Precession Period, Orbital Period are in fibonacci. Refer to Journal of Astronomy on Modeling Celestial Mechanics Using the Fibonacci Numbers

### Golden Ratio (Phi)

In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities where F_{(n+1)} / F_{n} is most of the time is 1.618

Golden ratio everywhere like example below.

- Flower petals
- Spiral of Pine Cone, Pineapple
- Storms spin in golden sequence
- Wave can be measured in this ratio.
- Planet alignment and spirals of our Milky way galaxy
- Shoulder to elbow and elbow to fingertips will be 1:1.6
- Finger tips to wrist and wrist to elbow
- bottom of fingertips to wrist
- Even your ears, brains, lungs system even helix of our DNA that forms rhythm of our hearbeat.
- Musical scales like piano.

### Fibonacci Extension

Fibonacci extensions are a tool that traders can use to establish profit targets or estimate how far a price may travel after a retracement/pullback is finished. Extension levels are also possible areas where the price may reverse.

### Fibonacci Retracement

In finance, Fibonacci retracement is a method of technical analysis for determining support and resistance levels.[1] They are named after their use of the Fibonacci sequence.