How to solve non homogeneous recurrence relation for a given one like in the photo
$a_n = a_{n-1} + 2a_{n-2} + 2^n$
and
$a_0 = 1; a_1 = 1$ ; n >= 2
If someone could help me with a kind of formula or something similar , cause I am new are really stucked here
$$a_n = a_{n-1} + 2a_{n-2} + 2^n \tag{1}$$ $$a_{n-1} = a_{n-2} + 2a_{n-3} + 2^{n-1} \tag{2}$$ $$a_{n-2} = a_{n-3} + 2a_{n-4} + 2^{n-2} \tag{3}$$ $$a_{n-3} = a_{n-4} + 2a_{n-5} + 2^{n-3} \tag{4}$$ $$...$$ $$a_4 = a_3 + 2a_2+2^4$$ $$a_3 = a_2 + 2a_1+2^3$$ $$a_2 = a_1 + 2a_0+2^2$$
Substituting in $(1)$ with (2): $$a_n = a_{n-2}+2a_{n-2}+2a_{n-3}+2^n+2^{n-1}$$ $$a_n = (1+2)a_{n-2}+2a_{n-3}+2^n+2^{n-1} \tag{5}$$
Substituting in $(5)$ with (3): $$a_n = 3a_{n-3}+2a_{n-3} + 3·2a_{n-4} +2^n+2^{n-1} + 3·2^{n-2}$$ $$a_n = (1+2+2)a_{n-3} + (1+2)2a_{n-4} +2^n+2^{n-1} + (1+2)·2^{n-2} \tag{6}$$
Substituting in $(6)$ with (4): $$a_n = 5a_{n-4} + 6a_{n-4} + 5·2a_{n-5}+ 2^n+2^{n-1} + 3·2^{n-2} + 5·2^{n-3}$$ $$a_n = (1+2+2 + (1+2)2)a_{n-4} + (1+2+2)2a_{n-5}+ 2^n+2^{n-1} + (1+2)·2^{n-2} + (1+2+2)·2^{n-3} \tag{7}$$
Let's write $(7)$ this way: $$a_n = S_1a_{n-4} + S_2a_{n-5}+ 2^n+2^{n-1} + S_3·2^{n-2} + S_4·2^{n-3}$$
Where the coefficients $S_1, S_2, S_3, S_4$ are sumatories of series I have sketched above.
I leave to you the job of finding out those series. Hint: what happens at each serie each time I make a substitution? How many substitutions I need?
