Consider the non-homogeneous linear recurrence relations $a_n = 2a_{n−1} + 2^n$ find all solutions.

Question

I can show that $a_n^{(h)}$characteristic equation $r-2=0 \to a_n^{(h)}=\alpha2^n$

But I'm stuck on $a_n^{(p)}$ characteristic equation $A2^n = 2A2^{n-1} + 2^n$

Simplifies to $-A = 2$

$A = 2A + 2$

Answer 1

Let $A(z)=\sum_{n=0}^\infty a_n z^n$ be the ordinary generating function. Then \begin{align} A(z) &= a_0 + \sum_{n=1}^\infty (a_{n-1} + 2^n)z^n \\ &= a_0 + z \sum_{n=1}^\infty a_{n-1} z^{n-1} + \sum_{n=1}^\infty (2z)^n \\ &= a_0 + z A(z) + \frac{2z}{1-2z}, \end{align} so \begin{align} A(z) &= \frac{a_0}{1-z} + \frac{2z}{(1-z)(1-2z)} \\ &= \frac{a_0}{1-z} - \frac{2}{1-z} + \frac{2}{1-2z} \\ &= \frac{a_0-2}{1-z} + \frac{2}{1-2z} \\ &= (a_0-2) \sum_{n=0}^\infty z^n + 2\sum_{n=0}^\infty (2z)^n \\ &= \sum_{n=0}^\infty (a_0-2 + 2^{n+1}) z^n, \end{align} which immediately implies that $$a_n = a_0-2 + 2^{n+1}.$$

Answer 2

Here is an alternative method of solution. I consider a more general form of the problem as follows:

$$\begin{align} & {{f}_{n}}-A{{f}_{n-1}}=B{{C}^{n}} \\ & {{f}_{n-1}}-A{{f}_{n-2}}=\frac{B{{C}^{n}}}{C} \\ \end{align}$$

where ${{f}_{0}}$ is given and ${{f}_{1}}=A{{f}_{0}}+BC$. Now, multiply the 2nd equation by $C$ and add to eliminate the $C^n$ terms to get $${{f}_{n}}=\left( A+C \right){{f}_{n-1}}-CA{{f}_{n-2}}$$

This is now in the form of a generalized Fibonacci sequence, say

$$\begin{align} & f_{n}=af_{n-1}+bf_{n-2} \\ & a=A+C \\ & b=CA \\ \end{align}$$

which can solved by standard means.