Homework - Resolve the recurrence relation What's the closed formula of this recurrence relation?
$$a_n = a_{n-1}+2a_{n-2}+2^n \text{ with } a_0=1, a_1=2 $$
 A: A generating function approach would make this straightforward:
$$G(x) = \sum_{n=0}^\infty a_n x^n = 1+2x+\sum_{n=2}^\infty a_n x^n$$
$$=1+2x+\sum_{n=2}^\infty (a_{n-1} + 2a_{n-2} + 2^n)x^n$$
$$=1+2x+\sum_{n=1}^\infty a_n x^{n+1} + 2 \sum_{n=0}^\infty a_n x^{n+2} + \sum_{n=2}^\infty 2^n x^n$$
$$=1+2x+x(G(x)-1)+2x^2G(x)+\frac{2^2x^2}{1-2x}$$
Thus $$G(x)(1-x-2x^2) = 1+x+\frac{2^2x^2}{1-2x}$$ and $$G(x) = \frac{1+x}{1-x-2x^2} + \frac{2^2x^2}{(1-2x)(1-x-2x^2)} = \frac{1+x}{(1+x)(1-2x)} + \frac{2^2x^2}{(1-2x)(1+x)(1-2x)}$$
$$= \frac{1}{(1-2x)} + \frac{2^2x^2}{(1-2x)^2(1+x)}$$
Now you can use partial fractions, and then expand in terms of geometric series to find the taylor coefficients of $G(x)$ which are the terms $a_n$.
A: This is nonhomogeneneous difference equations. First solve the homogeneous equation
$$
a_n - a_{n-1} - 2a_{n-2} = 0 \quad (1)
$$
Let $a_n = r^n$, so that $a_{n-1} = r^{n-1}$ and $r_{n-2} = r^{n-2} = 0$. Replacing in (1), we have
$$
r^n - r^{n-1} - 2r^{n-2} = 0 \quad r^2 - r - 2 = 0 \quad \Rightarrow \ r_1 = -1, \ r_2 = 2
$$ 
$$
a_{nh} = C_1(-1)^n + C_22^n
$$
Particular solution: Let $a_{np} = a_n = An2^n$. The presence of n is due to the fact that $2$ is a root of the equation (1). So, $a_{n-1} = A(n-1)2^{n-1}$ and $a_{n-2} = A(n-2)2^{n-2}$. Substituting in the given equation, we have
$$
An2^n + (An - A)2^{n-1} - 2A(n-2)2^{n-2} = 2^n \quad \Rightarrow \quad A = \frac{2}{3}
$$
Thus, $a_n = a_{nh} + a_{np} = C_1(-1)^n + C_22^n + \frac{2n2^n}{3}$. But, $a_0 = a(0) = 1$ and $a_1 = a(1) = 2$. We have the system
$$
\begin{cases}
1 = a_0 = C_1 + C_2\\
2 = a_1 = -C_1 + C_2  + \frac{8}{3}
\end{cases}
\quad \Rightarrow \quad C_1 = 8/9, \quad C_2 = 1/9
$$
Thus,
$$
a_n = \frac{8(-1)^n}{9} + \frac{1}{9}2^n + \frac{2n2^n}{3}
$$
A: The best course of action for simple inhomogeneous recurrences is to make use of a smart "change of variables" (read: substitute with another recurrence relation) to turn it into a homogeneous recurrence. A nice observation here is to notice that $2^n$ is itself a recurrence relation, namely: 
$$y_n=2y_{n-1},\,\,(y_0=1)$$ 
Let's use this to our advantage:
$$\begin{align}
a_n=a_{n-1}+2a_{n-2}+2^n &\Leftrightarrow 2^n=a_n-a_{n-1}-2a_{n-2} \\
&\Leftrightarrow 2\cdot2^{n-1}=a_n-a_{n-1}-2a_{n-2} \\
&\Leftrightarrow 2\cdot (a_{n-1}-a_{n-2}-2a_{n-3})=a_n-a_{n-1}-2a_{n-2} \\
&\Leftrightarrow a_n-3a_{n-1}+4a_{n-3}=0
\end{align}$$
Bam, homogeneous recurrence. Can apply the characteristic equation and finish it by yourself?
Edit: The characteristic equation for the last recurrence is $x^3-3x+4=0$, whose roots are $2,2$ and $-1$. It is well-known then, that given these roots, the solution is of the form:
$$a_n=(An+B)2^n+C(-1)^n$$
For some constants $A,B,C$. To find out what the constants are, we plug in values of $n$ for which the value of $a_n$ is known. The values of $a_0,a_1$ were given, but we need three to solve a linear system with three variables. We can easily calculate $a_2$: $$a_2=a_1+2a_0+2^2=8$$
Now we solve the system:
$$\begin{cases}
(A\cdot0+B)2^0+C(-1)^0=1 \\
(A\cdot1+B)2^1+C(-1)^1=2 \Rightarrow \\
(A\cdot2+B)2^2+C(-1)^2=8
\end{cases}$$
$$\Rightarrow \begin{cases}
B+C=1 \\
2(A+B)-C=2 \\
4(2A+B)+C=8
\end{cases}$$
Solving this will yield $A=\frac{2}{3}$,$B=\frac{5}{9}$ and $C=\frac{4}{9}$. Therefore, the closed form is:
$$a_n=\frac{(6n+5)2^n+4(-1)^n}{9}$$
