how can we solve this recurrence relation having part $2^n * n$

Question

how can we solve recurrence relation like this? $a_n - 3 a_{n-1} + 2 a_{n-2} = 2^n (n+1)$

I know $a_n = a_n(h) + a_n(p)$. What's $a_n(p)$ for $2^n * n$?

Answer 1

Like for differential equations: as $2^n$ is a simple solution of the characteristic equation, you can find a particular solution of the form: $$a_p(n)=n(\alpha n+\beta)2^n.$$ You should find $\;\alpha_p(n)=-n(n+1)2^{n-1}.$