Tag: simplified

The Math behind Fibonacci Numbers

In this blog we will see how to find index of a particular number in fibonacci series and find the number at a particular index in fibonacci series

1. Find the number at a particular index in fibonacci series

The Fibonacci numbers are defined recursively by the following difference equation:

\left\{\begin{matrix} F_{n} = F_{n-1} + F_{n-2} & & & & \\ F_{1} = 1 & & & & \\ F_{0} = 0 & & & & \end{matrix}\right.

It is easy to compute the first few elements in the sequence:

0,1,1,2,3,5,8,13,21,34⋯

Derivation of the general formula

It is possible to derive a general formula for F_{n} without computing all the previous numbers in the sequence. If a gemetric series (i.e. a series with a constant ratio between consecutive terms r^n ) is to solve the difference equation, we must have

r^n = r^{n-1} + r^{n-2}

which is equivalent to

r^2 = r + 1

This equation has two unique solutions

\varphi = \frac {1 + \sqrt{5}}{2} \approx 1.61803

\frac {1 - \sqrt{5}}{2} = 1 - \varphi = - \frac {1}{\varphi } \approx -0.61803

In particular the larger root is known as the golden ratio
\varphi = \frac {1 + \sqrt{5}}{2} \approx 1.61803

Now, since both roots solve the difference equation for Fibonacci numbers, any linear combination of the two sequences also solves it

a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^n + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^n

It’s not hard to see that all Fibonacci numbers must be of this general form because we can uniquely solve for a and b such that the initial conditions of F_{1}=1 and F_{0}=0 are met

\left\{\begin{matrix} F_{0} = a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^0 + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^0 & \\ F_{1} = a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^1 + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^1 & \end{matrix}\right.

yielding

\left\{\begin{matrix} a= \frac {1}{\sqrt{5}}\\ b= \frac {-1}{\sqrt{5}} \end{matrix}\right.

We have therefore derived the general formula for the n-th Fibonacci number

F_{n}= \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 + \sqrt{5}}{2} \end{smallmatrix}\bigr)^n + \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 - \sqrt{5}}{2} \end{smallmatrix}\bigr)^n

Since the second term has an absolute value smaller than 1, we can see that the ratios of Fibonacci numbers converge to the golden ratio
\lim_{n -> \infty } \frac {F_{n}}{F_{n-1}} = \frac {1 + \sqrt{5}}{2}

Python code:

def findFibIndexValue(index):
    golden_ratio = (1 + math.sqrt(5)) / 2
    return round(((golden_ratio ** index) - ((1 - golden_ratio) ** index)) / math.sqrt(5))

2. Find index of a particular number in fibonacci series

We know that
F_{n} = \frac {1}{\sqrt{5}}\left ( \varphi ^n - \hat \varphi^n \right )
where
\varphi = \frac {1}{2}\left ( 1 + \sqrt{5} \right ) and \hat \varphi = \frac {1}{2}\left ( 1 - \sqrt{5} \right )

n = round \begin{Bmatrix} \frac {logF_{n}+log\sqrt{5}}{log \varphi} \end{Bmatrix}

where “round” means round to the nearest integer. For speed of computation we should simplify this to:
n = round \begin{Bmatrix} \alpha \cdot log F_{n} + \beta \end{Bmatrix}

where the 𝛼 and 𝛽 constants are precomputed as:
\alpha = \frac {1}{log \varphi } \approx 2.078087
\beta = \frac {log \sqrt{5}}{log \varphi} \approx 1.672276

Python code:

def findFibIndex(val):
    return round(2.078087 * math.log(val) + 1.672276)

3. Count number of digits in the nth Fibonacci number

F_{n}= \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 + \sqrt{5}}{2} \end{smallmatrix}\bigr)^n + \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 - \sqrt{5}}{2} \end{smallmatrix}\bigr)^n

The above formula can be simplified,
F_{n} = round\left ( \frac {\varphi ^n}{\sqrt {5}} \right )
Count of digits in Fib(n)
= log_{10}F_{n}
= log_{10}\left ( \frac {\varphi ^n}{\sqrt{5}} \right )
= n \cdot log_{10}\varphi - log_{10}\sqrt{5}
= n \cdot log_{10}\varphi - \frac {log_{10}5}{2}

 

Python code:

phi = (1 + 5**.5) / 2
def numberOfDig (n) : 
    if n == 1 : 
        return 1
    return math.ceil((n * math.log10(phi) - 
                      .5 * math.log10(5)))