Solving the recurrence $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$ using generating functions

Question

Solve the following recurrence using generating functions: $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$.

My partial solution:

We can rewrite $a_{n+2} = 3a_{n+1} - 2a_n$, as $a_{n+2} - 3a_{n+1} + 2a_n = 0$, and we let $A(z) = \sum a_n z^n$. The goal is to compute $A(z)$ as this can be done as follows: $$A(z) - a_0 - a_1z - 3z(A(z) - a_0) + 2z^2A(z) = 0$$ $$(1-3z+2z^2)A(z) = a_0 + a_1z -3a_0z$$ $$A(z) = \frac{a_0 + (a_1 - 3a_0)z}{1-3z+2z^2}$$ $$\quad \quad = \frac{a_0 + (a_1 - 3a_0)z}{(1-z)(1-2z)}$$ $$\quad \quad = \frac{C}{(1-z)}+\frac{D}{(1-2z)}$$

And, I don't know how to continue, I cannot figure out the remaining. I'm pretty sure it is obvious, but I just cannot see it. If someone can help me I would be glad.

Answer 1

Some hints.

To find $C$ and $D$, use that $a_0 = A(0)$ and $a_1 = A'(0)$. Two equations in two unknowns..

Once the above is done, use the following identity to get the formula for each $a_n$. $${1 \over 1 - x} = 1 + x + x^2 + x^3 + ....$$

Answer 2

\begin{align} \frac{C}{1-z}+\frac{D}{1-2z} &= \frac{C(1-2z)}{(1-z)(1-2z)} + \frac{(1-z)D}{(1-z)(1-2z)} \\\\ &= \frac{(C+D)+(-2C-D)z}{(1-z)(1-2z)} \\\\ &= \frac{(a_0)+(a_1-3a_0)z}{(1-z)(1-2z)} \end{align}

You now have 2 linear equations and easily solve for $C$ and $D$ in terms of $a_0$ and $a_1$.

What is the power series for $\dfrac{1}{1-z}$? It's a simple one, try long hand division, and you'll see the coefficient pattern after a few terms. Note that $\dfrac{1}{1-2z}$ is just $\dfrac{1}{1-y}$ with $y=2z$.

Let $\displaystyle F(z) = \dfrac{1}{1-z} = \sum_{n=0}^{\infty}f_n z^n$ be that power series.

Then $\displaystyle A(z) = CF(z)+DF(2z) = \sum_{n=0}^{\infty} (C+D2^n)f_n z^n$. $\square$