Assuming Fibonacci Sequence as: $1, 1, 2, 3, 5, 8, 13, \ldots $
So, sequence $a_{n} = 1,1,2,3,5,8,13,\ldots $ where, $n=0,1,2,3,\ldots$
Now, The Generating Function for the sequence $a_{n}$ of real numbers is defined as: $$G(z) = \sum_{n=0}^{\infty }a_{n}z^{n}$$
So, For the given Fibonacci Sequence :
$\implies \;G(z) = 1+z+2z^{2}+3z^{3}+5z^{4}+8z^{5}+13z^{6}+\ldots+f_{n}z^{n}+\ldots \quad (1)$
Now , Shift one position right and multiply by $'z'$ :-
$\implies \;zG(z)=\;\;\;\; z+\;z^{2} \;\;+2z^{3}+3z^{4}+5z^{5}+8z^{6}+\ldots \quad \qquad (2)$
Now, Shift one more position right and multiply by $’z'$ :-
$\implies \;z^{2}G(z)=\;\;\;\; \;\;\;\;\;z^{2}\;\;+\;z^{3} \;\;+2z^{4}+3z^{5}+5z^{6}+8z^{7}+\ldots \quad \qquad (3)$
Now, Add Equation $(2)$ and Equation $(3)$:-
$\implies \;zG(z)+ z^{2}G(z)=z+2z^{2}+3z^{3}+5z^{4}+8z^{5}+13z^{6}+\ldots$
$\implies \;zG(z)+ z^{2}G(z) = G(z) - 1 \quad[\because \text{From equation}\; (1)]$
$\implies \;G(z)-zG(z)- z^{2}G(z) = 1$
$\implies \;G(z)= \frac{1}{1-z-z^{2}}$
So, Generating Function for the given Fibonacci Sequence is :-
$G(z)= \frac{1}{1-z-z^{2}}=1+z+2z^{2}+3z^{3}+5z^{4}+8z^{5}+13z^{6}+\ldots+f_{n}z^{n}$
Now , To get the Closed-Form Expression, We have to find the coefficient of $z^{n}$ i.e. $f_{n}$ in the given Generating Function for the given Fibonacci Sequence.
Let, $\frac{1}{1-z-z^{2}} = \frac{-1}{z^{2}+z-1}= \frac{-1}{(z-\alpha )(z-\beta )}$
$\implies \;z^{2}+z-1= (z-\alpha )(z-\beta )$
$\implies \;z^{2}+z-1= z^{2}-(\alpha + \beta)z +\alpha\;\beta$
On Comparing Coefficients $:- \alpha + \beta = -1 \; and\; \alpha\;\beta= -1$
Since , $(\alpha -\beta )^{2} = (\alpha +\beta )^{2}-4\alpha \beta = (-1)^{2} + 4 = 5$
So, $\alpha + \beta = -1$ and $\alpha -\beta = \pm \sqrt{5}$
On Solving these $2$ equations , We get :-
$\alpha = \frac{-1\pm \sqrt{5}}{2}$ and $\beta = \frac{-1\mp \sqrt{5}}{2}$
Let's take only one solution for the further calculations :-
So, Consider , $\alpha = \frac{-1 + \sqrt{5}}{2}$ and $\beta = \frac{-1 - \sqrt{5}}{2}$
Now, By Using Partial Fractions,
$ \frac{-1}{(z-\alpha )(z-\beta )}= \frac{A}{(z-\alpha )} +\frac{B}{(z-\beta) }$
$\implies\; -1 = A(z-\beta)+B(z-\alpha)$
$\implies \;-1 = (A+B)z-(A\beta\; + B\alpha)$
So, $A=-B$ and $A\beta = 1-B\alpha$
On solving these $2$ equations , We get ,
$A= \frac{1}{\beta -\alpha }$ and $B= \frac{-1}{\beta -\alpha }$
Now , after putting the values of $\alpha$ and $\beta$ , We get
$A= \frac{-1}{\sqrt{5}}$ and $B= \frac{+1}{\sqrt{5}}$
Now, on putting all these values in the original equation, we get ,
$\frac{1}{1-z-z^{2}} = \frac{-1}{z^{2}+z-1}= \frac{-1}{(z-\alpha )(z-\beta )}= \frac{A}{(z-\alpha )} +\frac{B}{(z-\beta)} =\frac{-1}{\sqrt{5}}\frac{1}{(z-\alpha )} + \frac{1}{\sqrt{5}}\frac{1}{(z-\beta) } $
$\implies\;\frac{1}{1-z-z^{2}} = \frac{-1}{\sqrt{5}}\frac{1}{(z-\alpha )} + \frac{1}{\sqrt{5}}\frac{1}{(z-\beta) }=\frac{1}{\sqrt{5}}\frac{1}{(\alpha-z )} - \frac{1}{\sqrt{5}}\frac{1}{(\beta-z) } $
So, $G(z)=\frac{1}{1-z-z^{2}} = \frac{1}{\sqrt{5}\alpha}\frac{1}{\left(1-\left(\frac{1}{\alpha}\right)z \right)} - \frac{1}{\sqrt{5}\beta}\frac{1}{\left(1- \left(\frac{1}{\beta}\right)z\right) } $
Now,
If $G(z)= \frac{1}{1-az}$ ,Then Coefficient of $z^{n}=a^{n}$
So, here , Coefficient of $z^{n} = f_{n} \; is :-$
$f_{n} = \frac{1}{\sqrt{5}}\frac{1}{\alpha }\left(\frac{1}{\alpha }\right)^{n} - \frac{1}{\sqrt{5}}\frac{1}{\beta }\left(\frac{1}{\beta }\right)^{n}$
$ f_{n} = \frac{1}{\sqrt{5}}\left(\frac{1}{\alpha }\right)^{n+1} - \frac{1}{\sqrt{5}}\left(\frac{1}{\beta }\right)^{n+1}$
Since , $\alpha = \frac{-1+ \sqrt{5}}{2}$ and $ \beta = \frac{-1- \sqrt{5}}{2}$
So, $\frac{1}{\alpha } = \frac{2}{\sqrt{5}-1}= \frac{2}{\left(\sqrt{5}-1\right)}\frac{(\sqrt{5}+1)}{(\sqrt{5}+1)}= \frac{(1+\sqrt{5})}{2}$
Similarly , $\frac{1}{\beta } = \frac{\left(1-\sqrt{5}\right)}{2}$
Now, On putting these values in $f_{n}$ , We get,
$f_{n} = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2 }\right)^{n+1} - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2 }\right)^{n+1}$
So, Closed-Form Expression for the given Fibonacci Sequence is :-
$f_{n} = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2 }\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2 }\right)^{n+1}\right]$
Note :
- Here, Irrational Number $\frac{1+ \sqrt{5}}{2} = 1.618\ldots$ represents the golden ratio $\Phi$.
- If we take Fibonacci Sequence as $0,1,1,2,3,5,8,\ldots,$ then the Generating Function $G(z)$ will be $\frac{z}{1-z-z^{2}}$ and Closed-Form expression will be different . $G(z)$ and Closed-Form expression for this Fibonacci Sequence can be obtained by the above procedure.
- If "z” is a complex variable then answer still remains the same
-
#Visualization:
import matplotlib.pyplot as plt
import numpy as np
known = {0:0, 1:1}
def fibonacci(n):
'''
It is a “memoized” version of fibonacci:
'''
if n in known:
return known[n]
res = fibonacci(n-1) + fibonacci(n-2)
known[n] = res
return res
if __name__=='__main__':
n=10
res=fibonacci(n)
f=np.array(list(known.values()))
plt.title("Fibonacci Sequence")
plt.xlabel("n")
plt.ylabel("fibonacci (n)")
x=np.arange(0,n+1,1)
print("Value of n:\t \t\t",x)
print("Value of fibonacci sequence: ",f)
plt.plot(x, f, linestyle = 'solid',marker ='o',color='green')
plt.tight_layout()
plt.show()