Things we will discuss in this Article:
 What are Fibonacci(Feebonachi) Series?
 C++ Code Implementation to find Fibonacci Numbers
 Time Complexity Analysis
 Practice Problem for you to Strengthen this Concept.
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
many more.
Recursive implementation to compute Fibonacci Number:
#include<bits/stdc++.h>
using namespace std;
int fib(int n){
if (n <= 1)
return n;
//recursive call
return fib(n1) + fib(n2);
}
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];
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
nonconsecutive Fibonacci Numbers.
For any integer n >0, we have:
For any integer n >0, we have:

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 selfdelimiting codes and for runlengthlimited 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 = nk
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:
Catalan's Identity:
Catalan's Identity is a special case of Vajda's Identity.
Cassini's Identity:
Cassini's Identity is a special case of Catalan's Identity and henceforth
child of Vajda's Identity too.
GCD of Fibonacci Numbers:
GCD of any two Fibonacci Numbers is equal to the Fibonacci number at the
index of gcd of their indices:
gcd: Greatest Common Divisor
Divisibility of Fibonacci Numbers:
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.
Sequential relations for Fibonacci Numbers:
 Sum of the sequence of Fibonacci Numbers:
 Sum of even indexed Fibonacci Numbers:
 Sum of odd indexed Fibonacci Numbers:
 Sum of even sequence of products of Fibonacci Numbers:
 Sum of the odd sequence of products of Fibonacci Numbers:
Methods to compute Fibonacci Number:
EulerBinet Formula:
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:
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:
Fibonacci Number as sum of previous series:
Note: This relation can be
proved by induction.
Related Practice Problems:
Related Articles:
 Dynamic Programming.
 Matrix Form and Golden Ratio.
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.
Thank You for Reading