Solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$ using generating function

Question

I'm preparing to an exam and trying to solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$, where $a_0=0$ and $a_1=1$.

This is my approach:

Let $A(z)=\sum_{n \geq 0} a_{n+2} z^{n+2}$, then:

$$\sum a_{n+2} z^{n+2} = 2 \sum a_{n+1} z^{n+2} - \sum a_n z^{n+2} + \sum (2z)^{n+2}$$

$$A(z)-a_0-a_1 z = 2z(A(z)-a_0)-z^2 A(z) + z^2 \frac{1}{1-2z}$$

$$A(z)(1-2z+z^2)=z+\frac{z^2}{1-2z}$$

$$A(z)=\frac{z(1-z)}{(1-2z)(1-2z+z^2)}=\frac{z}{(1-2z)(1-z)}=\frac{1}{1-2z}-\frac{1}{1-z}=\sum (\underbrace{2^n - 1}_{=a_n}) z^n$$

According to Wolfram, the result is different. Can you tell me where did I make the mistake?

Answer 1

You started off on the wrong foot by defining $A(z)=\sum_{n\ge 0}a_{n+2}z^{n+2}=\sum_{n\ge 2}a_nz^n$ and then, two lines later, calling this same quantity $A(z)-a_0-a_1z$: that implies that $A(z)=\sum_{n\ge 0}a_nz^n$, which is what you really wanted all along. The third line then would have been correct, except that you erred in evaluating the last term:

$$\sum_{n\ge 0}(2z)^{n+2}=\frac{(2z)^2}{1-2z}=\frac{4z^2}{1-2z}\;,$$

not $\frac{z^2}{1-2z}$. As a result,

$$A(z)=\frac{z(1+2z)}{(1-2z)(1-z)^2}=\frac4{1-2z}-\frac1{1-z}-\frac3{(1-z)^2}\;,$$

from which the correct result is easily obtained.

---

An alternative approach that I favor is to rewrite the recurrence so that it’s valid for all $n\ge 0$ on the extra assumption that $a_n=0$ for $n<0$. Here you get

$$a_n=2a_{n-1}-a_{n-2}+2^n-[n=0]-[n=1]\;,\tag{1}$$

where the last two terms are Iverson brackets chosen so that $(1)$ gives the correct values for $a_0$ and $a_1$. Now multiply through by $z^n$ and sum over $n\ge 0$ to get

$$\begin{align*} A(z)&=2zA(z)-z^2A(z)+\sum_{n\ge 0}(2z)^n-1-z\\ &=2zA(z)-z^2A(z)+\frac1{1-2z}-\frac{(1+z)(1-2z)}{1-2z}\\ &=2zA(z)-z^2A(z)+\frac{z(1+2z)}{1-2z} \end{align*}$$

and hence

$$A(z)=\frac{z(1+2z)}{(1-2z)(1-z)^2}\;.$$

From here the solution proceeds as before. I like this approach because once I get $(1)$ set up properly, everything is automatic: I don’t have to think much about the indices at all.

Answer 2

You have to be more careful with your indexing. I prefer to always cast the equation so that it is defined for $n \geq 0$ for greater consistency, but of course it doesn't matter as long as you keep track of your indices.

Anyway, the correct equation would be

$$A(z)(z^2-2z+1) = z + z^2 \frac{4}{1-2z}$$

if you defined $A(z) = \sum_{n=0}a_nz^n$. If you do the algebra you'll get $$A(z) = \frac{4}{1-2z}+\frac{z-4}{(z-1)^2} = \frac{4}{1-2z}-\frac{1}{1-z}-3\frac{d}{dz}\left(\frac{1}{1-z}\right)$$ and hence $$\sum_{n=0}a_nz^n = 4\sum_{n=0}2^nz^n-\sum_{n=0}z^n-3\sum_{n=1}nz^{n-1}$$ or $$\sum_{n=0}a_nz^n = 4\sum_{n=0}2^nz^n-\sum_{n=0}z^n-3\sum_{n=0}(n+1)z^{n}=\sum_{n=0}(-3n+2^{n+2}-4)z^n,$$ as desired.

Answer 3

While the generating function approach works systematically, you can solve this example by hand directly without too much trouble. First I'll define $a_{-1}=1$ (so that the recurrence holds down to $n=1$) and define $b_n=a_n-a_{n-1}$. Then your recurrence becomes $b_n=b_{n-1}+2^n$ for all positive $n$, and from the first few terms ( e.g. -1,1,5,13,...) it's easy to see that the solution is given by $b_n=2^{n+1}-3$. From this we obtain $a_{n\geq 0}$: \begin{align} a_n &=b_n+a_{n-1}\\ &=b_n+b_{n-1}+a_{n-2}\\ &\cdots \\&=b_n+b_{n-1}+\cdots+b_1+a_0\\ &=(2^{n+1}-3)+(2^{n}-3)+\cdots +(2^{2}-3)+0\\ &=\fbox{$4(2^{n}-1)-3n$}.\end{align}