Fibonacci Numbers
In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n > 1. Sequence = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Negative : The Fibonacci sequence also works below 0. It has alternating + and - accordingly. Ex - …, −8, 5, −3, 2, −1, 1, 0. Which is basically, F−n = (−1)n+1 * Fn for n > 1.
They also appear in biological settings, such as branching in trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke, an uncurling fern, and the arrangement of a pine cone’s bracts.
Finding nth Fibonacci Number
Recursive
Time = O(2^n)
Space = O(n)
int fib(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
Dynamic Programming
Time = O(n)
Space = O(n)
int fib(int n)
{
int arr[n + 1];
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i <= n; i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
Space Optimized (Best)
Time = O(n)
Space = O(1)
int fib(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
int a = 0, b = 1, c;
for(int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
Using Power of Matrix
Link: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
Using Binet’s Formula - O(1)
Time = O(1)
Space = O(1)
Formula: Fn is the nearest integer to ϕn / √5.
int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}
Some Interesting Facts.
- Sum of Fibonacci numbers (Si) till nth Fibonacci number (Fn) => Sn = Fn+2 - 1.
- To check if a number (n) is fibonacci or not - If either or both of 5n2+4 and 5n2-4 are perfect squares, then n is a fibonacci number.
- The series of last digits of numbers in Fibonacci sequence repeats with a cycle length of 60. Infact, Fibonacci sequence is periodic wrt Modulo. Application
- Cassini’s Identity -F(n-1) * F(n+1) – F(n) * F(n) = (-1)n.
- gcd(Fa, Fb) = Fgcd(a, b)
- Fibonorial - In mathematics, the Fibonorial n!F, also called the Fibonacci factorial, where n is a non-negative integer, is defined as the product of the first n positive Fibonacci numbers.
- Hosoya’s Triangle - Follows four seed relations -
H(0, 0) = H(1, 0) = H(1, 1) = H(2, 1) = 1and two recurrnce relations -H(n, j) = H(n - 1, j) + H(n - 2, j)and for the last element in current rowH(n, j) = H(n - 1, j - 1) + H(n - 2, j - 2).
Zeckendorf’s Theorem & Fibonacci Coding
Zeckendorf’s Theorem states that every positive integer can be written uniquely as a sum of distinct non-neighbouring Fibonacci numbers. Ex = 30 = 21 8 1, and 41 = 34 5 2.
Fibonacci coding is used in place of binary representation to represent positive numbers in data processing and communications. One important observation about this representation is, number of 1s in the Fibonacci representation tends to be much less than the number of 1s in the binary representation. Hence if in any application where it is more costly to store a 1 than to store a 0, it would make sense to use the fibonacci representation.
//Greedy Algorithm to print Fibonacci representation of a number
1) Let n be input number
2) While n > 0
a) Find the greatest Fibonacci Number smaller than n.
Let this number be 'f'. Print 'f'.
b) n = n - f
int smallestFib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1, c = 1;
while (c <= n) //change
{
c = a + b;
a = b;
b = c;
}
return a;
}
int main() {
int n = 30;
int i = 0;
while (n > 0) //change
{
i = smallestFib(n);
cout << i << " ";
n = n - i;
}
}
Modular Nature of Fibonacci
Fibonacci series is always periodic under modular representation i.e. F (mod m) will repeat after a certain period and the cycle will repeat too. This means we can find numbers diisible by a given number (m) at regular intervals in the Fibonacci sequence. Examples
Even Fibonacci Numbers
Using modular nature of the sequence, we can find period for numbers divisible by 2 (even numbers). That comes out to be 3 i.e. every third number in the Fibonacci sequence is divisible by 2. We can then come up with the recurrence relation to calculate nth even Fibonacci number as:
Recurrence for Even Fibonacci sequence is:
EFn = 4(EFn-1) + (EFn-2)
with seed values,
EF0 = 0 and EF1 = 2.
EFn represents n'th term in Even Fibonacci sequence.
The period is calle the Pisano period.
Leonardo Number
Sequence of numbers given by the recurrence:
The first few Leonardo Numbers are 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, …
The Leonardo numbers are related to the Fibonacci numbers by below relation:
