Question

8. a) Find the generating function of the recurrence an = 6an−1 −5an−2 +1 with initial

conditions a0 = 2,a1 = 5.

Answer 1

We will look for a generating function in the form

$G(z) = \sum\limits_{n = 0}^\infty {{a_n}} {z^n}$

$1 \cdot {a_0} = 1 \cdot 2 = 2$

$z \cdot {a_1} = 5z$

.........

${z^n}{a_n} = \left( {6{a_{n - 1}} - 5{a_{n - 2}} + 1} \right){z^n}$

Then

$G(z) = \sum\limits_{n = 0}^\infty {{a_n}} {z^n}={a_0} + {a_1}z + \sum\limits_{n = 2}^\infty {{a_n}} {z^n} = 2 + 5z + \sum\limits_{n = 2}^\infty {\left( {6{a_{n - 1}} - 5{a_{n - 2}} + 1} \right){z^n}} = 2 + 5z + 6\sum\limits_{n = 2}^\infty {{a_{n - 1}}{z^n}} - 5\sum\limits_{n = 2}^\infty {{a_{n - 2}}{z^n}} + \sum\limits_{n = 2}^\infty {{z^n}}$

Since

$\sum\limits_{n = 2}^\infty {{a_{n - 1}}{z^n}} = z\sum\limits_{n = 2}^\infty {{a_{n - 1}}{z^{n - 1}}} = z\sum\limits_{n = 1}^\infty {{a_n}{z^n}} = z\left( {\sum\limits_{n = 1}^\infty {{a_n}{z^n}} + {a_0} - {a_0}} \right) = z\left( {\sum\limits_{n = 0}^\infty {{a_n}{z^n}} - {a_0}} \right) = z\left( {G(z) - 2} \right)$

$\sum\limits_{n = 2}^\infty {{a_{n - 2}}{z^n}} = {z^2}\sum\limits_{n = 2}^\infty {{a_{n - 2}}{z^{n - 2}}} = {z^2}\sum\limits_{n = 0}^\infty {{a_n}{z^n}} = {z^2}G(z)$

$\sum\limits_{n = 2}^\infty {{z^n}} = \sum\limits_{n = 2}^\infty {{z^n}} + z + 1 - z - 1 = \sum\limits_{n = 0}^\infty {{z^n}} - z - 1 = \frac{1}{{1 - z}} - z - 1 = \frac{{1 - (z + 1)(1 - z)}}{{1 - z}} = \frac{{1 - 1 + {z^2}}}{{1 - z}} = \frac{{{z^2}}}{{1 - z}}$

then

$G(z) = 2 + 5z + 6z(G(z) - 2) - 5{z^2}G(z) + \frac{{{z^2}}}{{1 - z}}$

$G(z) - 6zG(z) + 5{z^2}G(z) = 2 + 5z - 12z + \frac{{{z^2}}}{{1 - z}}$

$G(z)\left( {1 - 6z + 5{z^2}} \right) = \frac{{(2 - 7z)(1 - z) + {z^2}}}{{1 - z}}$

$G(z) = \frac{{2 - 9z + 8{z^2}}}{{(1 - z)\left( {1 - 6z + 5{z^2}} \right)}}$

Answer: $G(z) = \frac{{2 - 9z + 8{z^2}}}{{(1 - z)\left( {1 - 6z + 5{z^2}} \right)}}$