recategorized by
9,741 views
36 votes
36 votes
What is the generating function $G(z)$ for the sequence of Fibonacci numbers?
recategorized by

8 Answers

Best answer
59 votes
59 votes

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 :

  1. Here, Irrational Number $\frac{1+ \sqrt{5}}{2} = 1.618\ldots$ represents the golden ratio $\Phi$.
  2. 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.
  3. If "z” is a complex variable then answer still remains the same
  1. #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()
edited by
15 votes
15 votes
The general form is $G(x) = \frac{x}{1-x-x^2}$

and after solving this using partial fraction, we will get

$f_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n- (\frac{1-\sqrt{5}}{2})^n)$
6 votes
6 votes
The recurrence for the Fibonacci series is

$f_n=f_{n-1}+f_{n-2}$

Let $G(x)=\sum_{k=0}^{\infty}a_kx^k$

$xG(x)=\sum_{k=1}^{\infty}a_{k-1}x^k$

$x^2G(x)=\sum_{k=2}^{\infty}a_{k-2}x^k$

Assuming $f_n=a_k,f_{n-1}=a_{k-1},f_{n-2}=a_{n-2}$ I re-write expressions

$G(x)\Biggl(\ 1-x-x^2 \Biggr)=\sum_{k=0}^{\infty}a_kx^k-\sum_{k=1}^{\infty}a_{k-1}x^k-\sum_{k=2}^{\infty}a_{k-2}x^k$

Solving for RHS

$\Bigl( a_0+a_1+\sum_{k=2}^{\infty}a_kx^k \Bigr)- \Bigl( a_1+\sum_{k=2}^{\infty}a_{k-1}x^k \Bigr)-\Bigl( \sum_{k=2}^{\infty}a_{k-2}x^k \Bigr)$

$a_0+\sum_{k=2}^{\infty} \Bigl( a_k-a_{k-1}-a_{k-2} \Bigr)x^k$

Now $a_k-a_{k-1}-a_{k-2}=0$ as evident from the fibonacci series

so $G(x)\Biggl(\ 1-x-x^2 \Biggr)=a_0=1$ (From the initial condition)

$G(x)=\frac{1}{1-x-x^2}$

Related questions

25 votes
25 votes
4 answers
1
makhdoom ghaya asked Nov 7, 2016
4,905 views
The total number of Boolean functions which can be realised with four variables is:$4$$17$$256$$65, 536$
23 votes
23 votes
9 answers
3
makhdoom ghaya asked Nov 14, 2016
5,018 views
Show that the conclusion $(r \to q)$ follows from the premises$:p, (p \to q) \vee (p \wedge (r \to q))$
22 votes
22 votes
6 answers
4
makhdoom ghaya asked Nov 14, 2016
5,343 views
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.