Fibonacci Series and Its Properties

• What are Fibonacci(Fee-bo-na-chi) Series?
• C++ Code Implementation to find Fibonacci Numbers
• Time Complexity Analysis
• Practice Problem for you to Strengthen this Concept.

Prerequisite:

• Recursion.
• Dynamic Programming.

Fibonacci Series:

Fibonacci Series is a naturally occurring series of numbers that leads us to various forms of design patterns accepted by nature.  Fibonacci Series looks something like:
$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$
and hence, defined as:

and are the reason for the shapes of tornados, galaxies, sunflower seeds pattern, even your beauty(through golden ratio), and

Recursive implementation to compute Fibonacci Number:

#include<bits/stdc++.h>
using namespace std;

//function to return fibonacci number
int fib(int n){
if (n <= 1)
return n;
//recursive call
return fib(n-1) + fib(n-2);
}

int main(){

int n ;
cout<<"Enter n ";
cin>>n;
cout<<endl<<"Fibonacci number is "<<fib(n)<<endl;
return 0;
}

DP implementation to compute Fibonacci Numbers:

Why use DP?

• Dynamic Programming is used with recursive methods to speed the successive computation by saving the results from subproblem computation.
• Secondly, we don't go through the recursive tree all over again with all the computation, we can just search and use the saved results.

How we implemented DP here?

• We implemented a 'lookup' array to store the computed values of subproblems to be used in the successive computation.
• We used negative one(-1) as initialization value for the lookup array, one must choose that value in DP as initialization value that can never be reached in the computation process being performed.
• We search and update our lookup array with each process of subproblem.

#include <bits/stdc++.h>
using namespace std;
#define NIL -1
#define MAX 100

int lookup[MAX];

//initialising lookup array
void _init(){
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}

//function to find and store fibonacci numbers
int fib(int n){
if (lookup[n] == NIL){
if (n <= 1)
//storing unsaved value
lookup[n] = n;
else
//recursicve call and storing unsaved value
lookup[n] = fib(n - 1) + fib(n - 2);
}

return lookup[n];
}
int main(){
int n;
_init();
cout<<"Enter n ";
cin>>n;
cout <<endl<< "Fibonacci number is " << fib(n)<<endl;
return 0;
}

Properties of Fibonacci Numbers:

Zeckendorf's Theorem:
Every positive integer can be represented in a unique combination of non-consecutive Fibonacci Numbers.
For any integer n >0, we have:

 $\forall&space;i&space;\in&space;\mathbb{N},&space;k_i\geq&space;\2$
$k_{i&space;+&space;1}&space;>&space;k_i&space;+&space;1$
$\displaystyle&space;n&space;=&space;\sum_{i&space;\mathop&space;=&space;0}^j&space;F_{k_i}&space;\&space;\&space;,\&space;where\&space;F_{k}\&space;is\&space;Fibonacci\&space;Number$
$\forall&space;\&space;n\&space;\left&space;\langle&space;k_i&space;\right&space;\rangle\&space;is\&space;different.$

Note:  Zeckendorf's Theorem is the most asked Fibonacci Number's property in competitive programming. Zeckendorf representations have applications in coding; they have been proposed for use in self-delimiting codes and for run-length-limited binary codes.

Algorithm for finding Zeckendorf's Pattern(using Greedy Algorithm):

1. Let n be the number for which we want to find Zeckendorf's Pattern.
2. Find the largest Fibonacci number k less than or equal to n.
3. Replace n = n-k
4. Repeat until we find the whole pattern i.e. until n becomes 0

Code implementation for Zeckendorf's Pattern:

#include <bits/stdc++.h>
using namespace std;

//function to find largest fibonacci number smaller than n
int fib_search(int n){

if (n == 0 || n == 1)
return n;

int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}

//function to display the found fibonacci number
void display_fib(int n){

while (n > 0) {
int f = fib_search(n);
cout << f << " ";
//updating n
n = n - f;
}
}

int main(){
int n;
cout <<"Enter the number n ";
cin >>n;
cout <<endl<< "Zeckendorf's Representation of "
<< n << " is \n";
display_fib(n);
return 0;
}

Vajda's Identity:
It states that:
$F_{n&space;+&space;i}&space;F_{n&space;+&space;j}&space;-&space;F_n&space;F_{n&space;+&space;i&space;+&space;j}&space;=&space;\left&space;({-1}&space;\right&space;)&space;^n&space;F_i&space;F_j$

Catalan's Identity:
Catalan's Identity is a special case of Vajda's Identity.
${F_n}^2&space;-&space;F_{n&space;-&space;r}&space;F_{n&space;+&space;r}&space;=&space;\left({-1}\right)^{n&space;-&space;r}&space;{F_r}^2$

Cassini's Identity:
Cassini's Identity is a special case of Catalan's Identity and henceforth child of Vajda's Identity too.
$F_{n&space;+&space;1}&space;F_{n&space;-&space;1}&space;-&space;F_n^2&space;=&space;\left&space;({-1}&space;\right&space;)&space;^n$

GCD of Fibonacci Numbers:
GCD of any two Fibonacci Numbers is equal to the Fibonacci number at the index of gcd of their indices:
$\forall&space;{m,&space;n}&space;\in&space;\mathbb{Z}_{>&space;2}:&space;\gcd&space;\left&space;\{{F_m,&space;F_n}&space;\right&space;\}&space;=&space;F_{\gcd&space;\left&space;\{&space;{m,&space;n}&space;\right&space;\}&space;}$
gcd: Greatest Common Divisor

Divisibility of Fibonacci Numbers:
$\forall&space;{m,&space;n}&space;\in&space;\mathbb{Z}_{>&space;2}&space;:&space;m&space;\mid&space;n&space;\iff&space;F_m&space;\mid&space;F_n$
a | b is read as 'a divides b' (i.e. without leaving any remainder).

Sum of squares of Fibonacci Numbers:
It is naturally the most intriguing property of Fibonacci Numbers. As it is this property that shows us the spiral behavior of the Fibonacci Numbers.
$F_1^2&space;+&space;F_2^2&space;+&space;F_3^2&space;+&space;\cdots&space;+&space;F_n^2&space;=&space;F_nF_{n+1}$
Sequential relations for Fibonacci Numbers:

Sum of the sequence of Fibonacci Numbers:

$\displaystyle&space;\forall&space;n&space;\in&space;\mathbb{Z}_{\ge&space;0}:&space;\sum_{j&space;\mathop&space;=&space;0}^n&space;F_j&space;=&space;F_{n&space;+&space;2}&space;-&space;1$

Sum of even indexed Fibonacci Numbers:

$\displaystyle\&space;\forall&space;n&space;\ge&space;1:&space;\,\sum_{j&space;\mathop&space;=&space;1}^n&space;F_{2&space;j}&space;=&space;F_2&space;+&space;F_4&space;+&space;F_6&space;+&space;\cdots&space;+&space;F_{2&space;n}&space;=&space;F_{2&space;n&space;+&space;1}&space;-&space;1$

Sum of odd indexed Fibonacci Numbers:

$\displaystyle\&space;\forall&space;n&space;\ge&space;1:&space;\,\sum_{j&space;\mathop&space;=&space;1}^n&space;F_{2&space;j-1}&space;=&space;F_1&space;+&space;F_3&space;+&space;F_&space;+&space;\cdots&space;+&space;F_{2&space;n-1}&space;=&space;F_{2&space;n}$

Sum of even sequence of products of Fibonacci Numbers:

$\displaystyle&space;\sum_{j&space;\mathop&space;=&space;1}^{2&space;n}&space;F_j&space;F_{j&space;+&space;1}&space;=&space;{F_{2&space;n&space;+&space;1}&space;}^2&space;-&space;1$

Sum of the odd sequence of products of Fibonacci Numbers:

$\displaystyle&space;\sum_{j&space;\mathop&space;=&space;1}^{2&space;n-1}&space;F_j&space;F_{j&space;+&space;1}&space;=&space;{F_{2&space;n}&space;}^2$

Methods to compute Fibonacci Number:

Euler-Binet Formula:

$F_n&space;=&space;\frac&space;{\Phi^n&space;-&space;\left&space;(&space;{1&space;-&space;\Phi}^n&space;\right&space;)}&space;{\sqrt&space;5}&space;=&space;\frac&space;{\Phi^n&space;-&space;\left&space;({-1&space;/&space;\Phi}^n&space;\right&space;)&space;}&space;{\sqrt&space;5}&space;=&space;\frac&space;{\Phi^n&space;-&space;\left&space;(&space;{-1}^n&space;\Phi^{-n}&space;\right&space;)&space;}&space;{\sqrt&space;5}$
$\Phi&space;\&space;is\&space;the\&space;golden\&space;ratio(\Phi&space;=&space;\dfrac&space;{1&space;+&space;\sqrt&space;5}&space;2&space;=&space;1.618)$
$F_n&space;=&space;\frac{\left(\frac{1&space;+&space;\sqrt{5}}{2}\right)^n&space;-&space;\left(\frac{1&space;-&space;\sqrt{5}}{2}\right)^n}{\sqrt{5}}$

As the second term in the above expression is always less than 1, so we can drop that term and henceforth the expressions reduces to:

$F_n&space;=&space;\left[\frac{\left(\frac{1&space;+&space;\sqrt{5}}{2}\right)^n}{\sqrt{5}}\right]$

and hence the Fibonacci number will the closest integer to the obtained value.

Time Complexity: O(n)

Note: Binet's relation can easily be proved using induction.

Fibonacci Number as the sum of Binomial Coefficients:

$\,&space;\displaystyle&space;\forall&space;n&space;\in&space;\mathbb{Z}_{>0}:F_n&space;=&space;\,&space;\sum_{k&space;\mathop&space;=&space;0}^{\left&space;\lfloor{\frac&space;{n&space;-&space;1}&space;2}&space;\right&space;\rfloor&space;}&space;\dbinom&space;{n&space;-&space;k&space;-&space;1}&space;k=&space;\binom&space;{n&space;-&space;1}&space;0&space;+&space;\binom&space;{n&space;-&space;2}&space;1&space;+&space;\binom&space;{n&space;-&space;3}&space;2&space;+&space;\dotsb&space;+&space;\binom&space;{n&space;-&space;j}&space;{j&space;-&space;1}&space;+&space;\binom&space;{n&space;-&space;j&space;-&space;1}&space;j\&space;where\&space;j&space;=&space;\left&space;\lfloor&space;{\frac&space;{n&space;-&space;1}&space;2}&space;\right&space;\rfloor$

Fibonacci Number as sum of previous series:
$\forall&space;\&space;n\geq&space;2,\&space;F_n&space;=1+&space;\sum_{i=0}^{n-2}&space;{F_i}$

Note:  This relation can be proved by induction.

Conclusion:

In this article, we learned about Fibonacci Numbers and Series and some of their most basic properties. And, we also learned how to find Fibonacci Numbers and Zeckendorf's Pattern using Recursion and Dynamic Programming and Greedy Algorithm respectively.

This is all for this article, if you have any doubt or there is an error in the content then do comment for which we will be thankful to you.