Solving a non-homogeneous linear recurrence relation

Question

So i have this non-homogeneous linear recurrence relation to solve:

$$a_{n}=2a_{n-1}-a_{n-2}+2^n+2$$

$a_{1}=7$ and $a_{2}=19$

I know that the non-homogeneous part is $2^n$ and i know how to solve homogeneous linear recurrence relations, but when i get a non-homogeneous one i have no idea how to approach it.

I have this as well: $b_{n}=Aq^n$ when the non-homogeneous part is an exponential function look-alike. So yeah i know it should be of help, but i don't know how to apply it in solution. I need to make a characteristic polynomial as well(if that's what it is called) but i am really stuck at using all that in practical example.

So i am not sure how to solve it, any hints or help would really be appreciated.

Answer 1

If we set $a_n=b_n+2^{n+2}$ we have $$ b_n+2^{n+2}=2 b_{n-1} + 2^{n+2}-b_{n-2}-2^{n}+2^n + 2 $$ or just: $$ b_n = 2b_{n-1}-b_{n-2}+2 $$ In a similar way, if we set $b_n=c_n+ n^2$ we have $$ c_n=2c_{n-1}-c_{n-2}. $$ $a_1=7, a_2=19$ lead to $b_1=-1,b_2=3$ and to $c_1=-2, c_2=-1$.
By the previous homogeneous recurrence relation, it follows that $c_n=n-3$, hence $b_n=n^2+n-3$ and $$\boxed{\phantom{\sum}a_n = \color{red}{2^{n+2}+n^2+n-3}\phantom{\sum}}$$

Answer 2

Define: $g_n := a_{n}-a_{n-1}$

Then $a_{n}=2a_{n-1}-a_{n-2}+2^n+2 \implies a_{n}-a_{n-1}=a_{n-1}-a_{n-2}+2^n+2 \\\ \implies g_n = g_{n-1} + 2^n +2 \implies g_n- g_{n-1} = 2^n +2$

$$g_n- g_{n-1} = 2^n +2 $$ $$g_{n-1}- g_{n-2} = 2^{n-1} +2 $$ $$.$$ $$.$$ $$.$$ $$g_3- g_{2} = 2^3 +2 $$

Since $g_2 = 19-7=12$, then $g_n = \sum_{i=3}^n g_i-g_{i-1} +g_2 = 2^3\times \frac{1-2^{n-3+1}}{1-2} + 2\times (n-3+1) + 12= 2^{n+1}+2n$ Therefore $a_n-a_{n-1} = 2^{n+1}+2n$.For all $n \geq 3$.

$$a_n-a_{n-1} = 2^{n+1}+2n$$ $$a_{n-1}-a_{n-2} = 2^{n}+2(n-1)$$ $$.$$ $$.$$ $$.$$ $$a_3-a_{2} = 2^4+2 \times 3$$

$a_n = \sum_{i = 3}^{n} a_i - a_{i-1} + a_{2} = 2^4 \times \frac{1-2^{n-3+1}}{1-2}+ (3+n) \times (n-3+1) + 19 = n^2+n +2^{n+2}-3$. For all $n \geq 3$.

EDIT: For generalization:

$$a_n = Aa_{n-1}+Ba_{n-2} + P(n)$$ Assert: $$a_n - C a_{n-1} = D (a_{n-1} - Ca_{n-2}) + P(n) \implies $$ Where $C,D \in \mathbb C$ \begin{cases}C+D = A \\ CD = -B\end{cases}

so $C,D$ is roots of $x^2-Ax-B=0$