Solving linear recursive equation $a_n = a_{n-1} + 2 a_{n-2} + 2^n$.

Question

I wish to solve the linear recursive equation:

$a_n = a_{n-1} + 2a_{n-2} + 2^n$, where $a_0 = 2$, $a_1 = 1$.

I have tried using the Ansatz method and the generating function method in the following way:

Ansatz method

First, for the homogenous part, $a_n = a_{n-1} + 2a_{n-2}$, I guess $a_n = \lambda^n$ as the solution, and substituting and solving for the quadratic, I get $\lambda = -1, 2$. So, $a_n = \alpha (-1)^n + \beta 2^n$. Then, for the inhomogenous part, I guess $a_n = \gamma 2^n$, to get $\gamma 2^n = \gamma 2^{n-1} + 2\gamma 2^{n-2} + 2^n$, whence $2^n=0$, which means, I suppose, that this guess is not valid. These are the kind of guesses that usually work, so I don't know why it fails in this particular case, and what to do otherwise, so I tried the generating function method.

Generating function method

Let $$ A(z) = \sum_{i=0}^{\infty} a_k z^k $$ be the generating function for the sequence $\{ a_n \}_{n \in \mathbb{N} \cup {0}}$. Then, I try to write down the recursive relation in terms of $A(z)$: $$ A(z) = zA(z) + 2z^2 A(z) + \frac{1}{1-2z} + (1 - 2z), $$ where the last term in the brackets arises because of the given initial conditions. Then, solving for $A(z)$, $$ \begin{align} A(z) &= \frac{1}{(1+z)(1-2z)^2} + \frac{1}{1+z}\\ &= \frac{2}{9}\frac{1}{1-2z} + \frac{2}{3}\frac{1}{(1-2z)^2} + \frac{10}{9}\frac{1}{1+z}\\ &=\frac{2}{9} \sum_{k=0}^{\infty} 2^k z^k + \frac{2}{3} \sum_{k=0}^{\infty} (k+1)2^k z^k + \frac{10}{9} \sum_{k=0}^{\infty} (-1)^k z^k\\ &= \sum_{k=0}^\infty \frac{(3k+4)2^{k+1} + (-1)^k 10}{9} z^k. \end{align} $$ So, $$ a_k = \frac{(3k+4)2^{k+1} + (-1)^k 10}{9}. $$ But then, $a_1 = 2$, whereas we started out with $a_1 = 1$.

At first, I thought that maybe the generating function method did not work because some of the series on the right hand side were not converging, but they all look like they're converging for $|z| < 1/2$. I rechecked my calculations several times, so I don't think there is any simple mistake like that. It would be great if someone could explain to me what exactly is going wrong here.

Answer 1

The $1-2z$ in your implicit equation for $A(z)$ is not correct, it should be $1-3z$:

$$\begin{eqnarray*}A(z)&=& a_0 + a_1 z + \sum_{n \geq 2} a_n z^n \\ &=& 2+ z + \sum_{n \geq 2} a_{n-1} z^n + \sum_{n \geq 2} 2 a_{n-2} z^n + \sum_{n \geq 2} 2^n z^n \\ &=&2+ z + \sum_{n \geq 1} a_n z^{z+1} + \sum_{n \geq 0} 2 a_n z^{n+2} + \sum_{n \geq 2} (2z)^n \\ &=&2+ z + \bigl(z A(z)-2 z\bigr) + 2 z^2 A(z) + \left(\frac{1}{1-2z}-1-2z\right)\\ &=&1-\color{red}{3} z + z A(z) + 2z^2 A(z) + \frac{1}{1-2z}\end{eqnarray*}$$ Now you can use your method to compute the coefficients of $A(z)$. This is done in detail in Brian M. Scott's answer.

Answer 2

I’ll use generating functions. I first rewrite the recurrence so that it holds for all $n\ge 0$ on the assumption that $a_n=0$ for $n<0$:

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

where the last two terms use the Iverson bracket. (This is basically just a sneaky way to take care of the initial values right from the start.) Now multiply $(1)$ be $x^n$ and sum over $n\ge 0$, writing $A(x)$ for $\sum_{n\ge 0}a_nx^n$:

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_{n-1}x^n+2\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}2^nx^n+1-3x\\ &=x\sum_{n\ge 0}a_{n-1}x^{n-1}+2x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+\frac1{1-2x}+1-3x\\ &=xA(x)+2x^2A(x)+\frac{2-5x+6x^2}{1-2x}\;, \end{align*}$$

so

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

Break this into partial fractions:

$$\frac{2-5x+6x^2}{(1+x)(1-2x)^2}=\frac{a}{1+x}+\frac{b}{1-2x}+\frac{c}{(1-2x)^2}\;,$$

so

$$2-5x+6x^2=a(1-2x)^2+b(1+x)(1-2x)+c(1+x)\;.$$

Substituting $x=\frac12$, we find that $\frac32c=1$, or $c=\frac23$. Substituting $x=-1$, we find similarly that $9a=13$, or $a=\frac{13}9$. Thus,

$$\begin{align*} 2-5x+6x^2&=\frac{13}9(1-2x)^2+b(1+x)(1-2x)+\frac23(1+x)\\ &=\left(\frac{13}9+b+\frac23\right)+x\left(-\frac{52}9-b+\frac23\right)+x^2\left(\frac{52}9-2b\right)\\ &=\left(b+\frac{19}9\right)+x\left(-b-\frac{46}9\right)+x^2\left(\frac{52}9-2b\right)\;, \end{align*}$$

so $b+\frac{19}9=2$, and $b=-\frac19$. As a safety check it’s easily verified that the other two coefficients yield the same value of $b$, so

$$\begin{align*} A(x)&=\frac19\left(\frac{13}{1+x}-\frac1{1-2x}+\frac6{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac2{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac{d}{dx}\left(\frac1{1-2x}\right)\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\sum_{n\ge 0}n2^nx^{n-1}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+6\sum_{n\ge 0}(n+1)2^nx^n\right)\\ &=\sum_{n\ge 0}\frac{13(-1)^n-2^n+6(n+1)2^n}9x^n\\ &=\sum_{n\ge 0}\frac{(6n+5)2^n+13(-1)^n}9x^n\;, \end{align*}$$

and

$$a_n=\frac{(6n+5)2^n+13(-1)^n}9\;.$$

Answer 3

Suppose $$ a_n=a_{n-1}+2a_{n-2}+2^n\tag{1} $$ Let $a_n=b_n+\frac23n\,2^n$, then $$ b_n+\frac23n\,2^n =b_{n-1}+\frac23(n-1)\,2^{n-1}+2b_{n-2}+2\cdot\frac23(n-2)\,2^{n-2}+2^n\tag{2} $$ and cancelling, we get $$ b_n=b_{n-1}+2b_{n-2}\tag{3} $$ The standard solution to $(3)$ is $b_n=c_1(-1)^n+c_22^n$. Therefore, $$ a_n=c_1(-1)^n+\left(c_2+\frac23n\right)2^n\tag{4} $$ Solving for $a_0=2$ and $a_1=1$, we get $$ a_n=\frac{13}9(-1)^n+\left(\frac59+\frac23n\right)2^n\tag{5} $$

---

Comment on the Ansatz Method

Let $Sa_n=a_{n+1}$. If we apply $S-2$ to $(1)$, we get $$ \begin{align} (S-2)\left(a_n-a_{n-1}-2a_{n-2}\right) &=(S-2)2^n\\ &=0\tag{6} \end{align} $$ This means $$ (S+1)(S-2)^2a_n=0\tag{7} $$ The problem with the Ansatz method, is the exponent of $2$ on $(S-2)$.

The standard solution for $(7)$ is $a_n=c_1(-1)^n+(c_2+c_3n)2^n$.

Answer 4

Using the characteristic equation method, we have the homogeneous part of the given equation, $$g_n = g_{n-1} + 2g_{n-2}$$ As you have done, the roots of the characteristic equation are $2$ and $-1$, so the solution to the homogeneous part is $c_12^n + c_2(-1)^n$ for some constants $c_1$ and $c_2$. For the nonhomogeneous part, according to the comment by @AndreNicolas, we assume the solution is of the form $c_3n2^n$ and we can write: $$c_3n2^n = c_3(n-1)2^{n-1} + 2c_3(n-2)2^{n-2} + 2^n \\ \implies c_3 = \frac{2}{3}$$

Note: We guess $c_3n2^n$ for the nonhomogeneous part, and not $c_32^n$, because $2$ is already a root of the characteristic equation of the homogeneous part. In the same way, when we have repeated roots for the homogeneous part (say the root $a$ appears thrice), we use $c_1a^n + c_2na^n + c_3n^2a^n$, etc.

Now, $$\begin{align} a_n &= h_n + n\frac{2 \cdot 2^n}{3} \\ &= c_12^n + c_2(-1)^n + \frac{2^{n+1}n}{3} \end{align}$$ and by substituting for $a_0$ and $a_1$, we get $c_1 = \frac{5}{9}$, $c_2 = \frac{13}{9}$, and $$a_n = \frac{5\cdot 2^n}{9} + \frac{13 \cdot (-1)^n}{9} + \frac{2^{n+1}n}{3}$$