Fibonacci Series

History
- Problem of Rabbits
Properties
Solutions
Other Facts

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 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, F₁ = 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ⁿ) - 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 n
4  }
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 2
9// matrices F and M of size 2*2, and
10// puts the multiplication result
11// 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 the
24// result in F[][]
25function power(F, n) {
26  const M = [[1, 1], [1, 0]];
27  // n - 1 times multiply the
28  // 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