Consider the non-homogeneous linear recurrence relations $a_n = 2a_{n−1} + 2^n$ find all solutions. 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$
 A: 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}.$$
A: 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.
