Introduction
The fibonacci series is the number sequence in which the given number results from adding the two previous numbers. The terms in the Fibonacci sequence are as follows:
The individual numbers in this sequence are called Fibonacci numbers. The Fibonacci sequence is a fantastic mathematical concept found in various places, including seashell patterns and the Parthenon.
Properties of Fibonacci Numbers
- The ADDITION Rule
F_{N + K} = F_{K} . F_{N + 1} + F_{K - 1} . F_{N}
- Applying Addition Rule to the case, K = N
F_{N + N} = F_{N} . F_{N + 1} + F_{N - 1} . F_{N}
F_{2N} = F_{N} ( F_{N + 1} + F_{N - 1})
- From the above property, we can prove that for any positive integer K, F_{NK} is the multiple of F_{N }(By the Induction Hypothesis).
- The inverse of the above property is true since, if F_{M} is multiple of F_{N}, then M is also the multiple of N.
- Cassiniâ€™s Identity
F_{N - 1} . F_{N + 1} - F_{N}^{2} = (-1)^{N}
This identity was given by Giovanni Domenico Cassini, an Italian mathematician. In the mathematical expression, N is the variable and it can have values from 1â€¦..N.
For eg., if â€˜Nâ€™ is an odd number, i.e. 1, 3, 5,... then (-1)^{N+1} = +1 in every case. But if we take even value here, we will get the result as -1.
- GCD Identity
For M, N >= 1
GCD(F_{M} , F_{N}) = F_{GCD (M, N) }, where M, N are integers
Recommended topic, kth largest element in an array and Euclid GCD Algorithm
The Golden Ratio Approach
The golden ratio is defined as the limit of the ratio of successive terms in the Fibonacci sequence.
Now, if we divide F_{2 }with F_{1}, we get, F_{2} / F_{1} = 1 / 1 = 1 F_{3} / F_{2} = 2 / 1 = 2 F_{4} / F_{3} = 3 / 2 = 1.5 F_{5} / F_{4} = 5 / 3 = 1.667 F_{6} / F_{5} = 8 / 5 = 1.6 F_{7} / F_{6} = 13 / 8 = 1.625 F_{8} / F_{7} = 21 / 13 = 1.61538 F_{9} / F_{8} = 34 / 21 = 1.619047 F_{10} / F_{9} = 55 / 34 = 1.61765 F_{11} / F_{10} = 89 / 55 = 1.61818 F_{12} / F_{11} = 144 / 89 = 1.617975 F_{13} / F_{12} = 233 / 144 = 1.61805 . . . and so on. |
The golden ratio is coming about 1.618, as it means that as â€˜Nâ€™ becomes sufficiently large, the fibonacci sequence approaches or approximates a geometric sequence. So, starting at number 144, and if we multiply 144 by 1.618, we get 233 (Approx.), the next element in the sequence. If we now multiply 233 with 1.618, we get approximately 377. Hence this golden ratio helps to approximate the next number in the series easily.
The formula for golden ratio is,
(1 + âˆš5)^{N } - (1 - âˆš5)^{N} F_{N} = ------------------------------ 2^{N} . âˆš5 |
For example, let us find out the 8^{th} element in the sequence using the formula,
(1 + âˆš5)^{8 } - (1 - âˆš5)^{8}
F_{8} = ------------------------------ = 21
2^{8} . âˆš5