Solutions for Generating Functions

Page  A-15
12:  Use a generating function to solve: the recurrence relation:  
       a_k = 3a_(k-1) + 2 and the initial condition  a_0 = 1.

Solution:
Multiply the given recurrence relation by  x^k and add for  k=1 to \inf:
* \Sum_[k=1 to inf]  a_k x^k   
            =  \Sum_[k=1 to inf] 3 a_(k-1) x^k   + \Sum_[k=1 to inf] 2 x^k.

Replacing \Sum_[k=0 to inf]  a_k x^k  by the generating function
      G(x), we have:
        \Sum_[k=1 to inf]  a_k x^k   =  G(x) - a_0;
        \Sum_[k=1 to inf] 3 a_(k-1) x^k  = 3x G(x);
        \Sum_[k=1 to inf] 2 x^k = 2x [1/(1- x)].
Substituting in *, with a_o = 1, we have:
         G(x) - 1  =   3x G(x)   +  2x [1/(1- x)];  
         (1-3x) G(x) =  1  +  2x [1/(1- x)]             (using algebra)
        G(x)  =  1 /(1-3x)   +2x /(1-x)(1-3x)           (using more algebra)
        G(x)  =   1/1-3x)  -  1/(1-x)  +1/(1-3x)        (partial fractions)
                =  2/(1-3x)  - 1/(1-x) 
                =  2[  1 + (3)x + (3)^2x^2 + (3)^3x^3 ...  + (3)^kx^k + ... ]
                    -[  1 +  x  + x^2 + x^3 +...   +  x^k + ...  ]
Therefore:
     a_k = 2(3^k)  -  1   is the solution.

Check:    1 = a_ 0 =  2 - 1  
   LHS:  a_k =  2(3^k)  -  1   =  6J(3^(k-1)) - 1
   RHS:  3a_(k-1) + 2  =  3[2(3^(k-1))  -  1 ]  + 2 = 6(3^(k-1)) - 3 +2  = LHS.
We have the correct solution.


13:  Use a generating function to solve: the recurrence relation:  
       a_k = 3a_(k-1) + 4^(k-1) and the initial condition  a_0 = 1.

Solution:
Multiply the given recurrence relation by  x^k and add for  k=1 to \inf:
* \Sum_[k=1 to inf]  a_k x^k   
            = \Sum_[k=1 to inf] 3 a_(k-1) x^k  + \Sum_[k=1 to inf] 4^(k-1) x^k.

Replacing \Sum_[k=0 to inf]  a_k x^k  by the generating function
      G(x), we have:
        \Sum_[k=1 to inf]  a_k x^k   =  G(x) - a_0;
        \Sum_[k=1 to inf] 3 a_(k-1) x^k  = 3x G(x);
        \Sum_[k=1 to inf] 4^(k-1)  x^k = x [1/(1- 4x)].
Substituting in *, with a_o = 1, we have:
         G(x) - 1  =   3x G(x)   +  x [1/(1- 4x)];  
         (1-3x) G(x) =  1  +  x [1/(1- 4x)]             (using algebra)
        G(x)  =  1 /(1-3x)   +x /(1-4x)(1-3x)           (using more algebra)
        G(x)  =   1/1-3x)  + 1/(1-4x)  -1/(1-3x)        (partial fractions)
                =  1/(1-4x) 
                =  [1 + 4x  +(4)^2 x^2 +(4)^3 x^3 +... +4^(k-1) x^k + ... ]
Therefore:
     a_k = 4^k   is the solution.

Check:    1 = a_ 0 =  1  
   LHS:   a_k =  4^k   =  4 (4^(k-1))
   RHS:   3a_(k-1) + 4^(k-1)   =  3(4^(k-1))  +  4^(k-1) = 4(4^(k-1))
We have the correct solution.


Extra Problem:  
  Use a generating function to solve: the recurrence relation:  
       a_k = 3a_(k-1) + 2^(k) and the initial condition  a_0 = 1.

Solution:
Multiply the given recurrence relation by  x^k and add for  k=1 to \inf:
* \Sum_[k=1 to inf]  a_k x^k   
            =  \Sum_[k=1 to inf] 3 a_(k-1) x^k   + \Sum_[k=1 to inf] 2^(k) x^k.

Replacing \Sum_[k=0 to inf]  a_k x^k  by the generating function
      G(x), we have:
        \Sum_[k=1 to inf]  a_k x^k   =  G(x) - a_0;
        \Sum_[k=1 to inf] 3 a_(k-1) x^k  = 3x G(x);
        \Sum_[k=1 to inf] 4^(k-1)  x^k = 2x [1/(1- 2x)].
Substituting in *, with a_o = 1, we have:
         G(x) - 1  =   3x G(x)   +  2x [1/(1- 24x)];  
         (1-3x) G(x) =  1  +  2x [1/(1- 2x)]            (using algebra)
        G(x)  =  1 /(1-3x)   + 2x /(1-2x)(1-2x)         (using more algebra)
        G(x)  =   1/1-3x)  - 2/(1-2x)  +2/(1-3x)        (partial fractions)
                =  3/(1-3x) - 2/(1-2x)  +
                =  3[1 +3x +(3)^2 x^2 + (3)^3 x^3 +... + 3^(k-1) x^k + ...  ]
                   -2[1 +2x +(2)^2 x^2 +(2)^3 x^3 +... + 2^(k-1) x^k + ...  ]

Therefore:
     a_k = 3^(k+1)  - 2^(k+1)  is the solution.

Check:    1 = a_ 0 =  1  
   LHS:   a_k =  3^(k+1)  - 2^(k+1)   =  3(3^(k))  -2 (2^(k))
   RHS:   3a_(k-1) + 2^(k)   =  3[(3^(k))  -  2^(k)) ] + 2^(k)  
          = 3(3^(k))  - 2(2^(k)). 
We have the correct solution.


Back to 2320 Home Page