I need to solve the following recurrence relation:
$a_n=3a_{n-1}-2a_{n-2}+2^n$
For the homonogenous part, it's quite simple and I get:
$a_n^h=\lambda_1+\lambda_22^n$
The nonhomonogenous part is where I get lost. Since one of the solutions from the equation (that I got from Euler's substutution) turns out to be $2$, I need to use the following substitution for $a_n$ :
$a_n=A2^nn^m$
Which means I get:
$An^m2^n-3A(n-1)^m2^{n-1}+2A(n-2)^m2^{n-2}=2^n$
I can easily reduce this to:
$An^m-3A(n-1)^m2^{-1}+A(n-2)^m2^{-1}=1$
But I'm not sure how to continue here. I'd be grateful if anyone could help me point me to the right direction. I'm not sure how to factor $n^m$.
EDIT:
The solution (thank you for helping!):
$a_n=\lambda_1+\lambda_2*2^n+2*n*2^n$
Alternate solution as a reference. Since the non-homogeneous is kind of special, we can proceed as follows.
Solution. $\blacktriangleleft$ Divide the equation by $2^n$ we have $$ \frac {a_n}{2^n} = \frac 32 \cdot \frac {a_{n-1}} {2^{n-1}} - \frac 12 \cdot \frac {a_{n-2}} {2^{n-2}} + 1. $$ Let $b_n = a_n \cdot 2^{-n}$, then replace $n$ by $n+1$ we have two equations: \begin{alignat*}{5} &b_{n+1} & - \frac 32 &b_n& + &\frac 12 b_{n-1}& &&= &1&\\ & & &b_n& - & \frac 32 b_{n-1}& + &\frac 12 b_{n-2}& = &1& \end{alignat*} Subtract them we get a homogeneous recurrence $$ b_{n+1} - \frac 52 b_n + 2 b_{n-1} - \frac 12 b_{n-2} = 0, $$ whose characteristic polynomial is $$ 2x^3 - 5x^2 + 4 x -1 = (x-1)(2x^2-3x + 1) = (x-1)^2 (2x-1), $$ hence the general solution is $$ b_n = (c_1 + c_2 n) + c_3 2^{-n}, $$ and the solution to the original equation is $$ a_n = c_3 + (c_1 + c_2 n)\cdot 2^n. \blacktriangleright $$
Now that I think about it, this seems like an indirect application to the Euler substitution. Maybe my post is redundant here...