### 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.

```