Non-homogenous recurrences using generating functions

Question

I'd like to practice solving non-homogenous recurrences using ordinary generating functions. Consider an example $$ a_n = a_{n-2} + 2 a_{n-1} -3 + 2^n \quad (n>2) $$ with $a_0 = 1, a_2 = 2$. In particular, $a_1 = -1$. Let $F(x) = \sum_{n=0}^\infty a_n x^n$ be the associated generating function. Solving this for the homogenous part is routine, if I am not mistaken, the sequence $(a_n)$ is like this: $$ 1,4,4,-8,16,-32, \ldots $$ so the pattern is clear. Can one tell me how to write it concisely to incorporate the non-homogenous part? More generally, how to approach such problems?

Answer 1

Hint.

After multiplying by $x^n$ we have

$$ a_nx^n - a_{n-2}x^n - 2 a_{n-1}x^n + 3x^n - 2^nx^n=0 $$

and summing up

$$ S(x) -x^2S(x)-2xS(x)+\frac{3}{1-x}-\frac{1}{1-2x}=\phi_0(x) $$

or

$$ S(x) = \frac{1}{1-x^2-2x}\left(\frac{1}{1-2x}-\frac{3}{1-x}+\phi_0(x)\right) $$

here $\phi_0(x)$ contains the initial conditions. Also

$$ x^2+2x-1 = (x+1)^2-2 = (x+1-\sqrt{2})(x+1+\sqrt{2}) $$

$$ \phi_0(x) = -(a_0+a_1x)+2(a_1x)=a_1 x-a_0 $$

NOTE

This recurrence needs only two initial conditions.