<s>[INST] 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 $$
 [/INST] 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}
$$
</s>