<s>[INST] Find a closed formula for $\sum_{n\geq 0} f(n)x^n.$ Given that $f(n) =f(n-1) + 2f(n-2)$ for $n \geq 2$, with $f(1) = 1$ and $f(2) = 3$ find a closed formula for $$\sum_{n\geq 0} f(n)x^n.$$
Here I try to do the following $ \sum_{n=0}^{\infty}f(n)x^{n} = \sum_{n=1}^{\infty}f(n-1)x^{n} + 2\sum_{n=2}^{\infty}f(n-2)x^{n}$ but when I simplify and re-index I get $$1=x+2x^2,$$ which is not correct. Can someone help me?
 [/INST] Let $F(x)$ denote the generating function for $f(n)$, i.e.
$$F(x)=\sum_{n\ge1}f(n)x^n$$
Multiply both sides of the recurrence by $x^n$ and sum both sides starting from $n=3$:
$$\sum_{n\ge3}f(n)x^n=\sum_{n\ge3}f(n-1)x^n+2\sum_{n\ge3}f(n-2)x^n$$
Now manipulate this as need to get everything in terms of $F(x)$:
$$\begin{align}
\sum_{n\ge3}f(n)x^n&=\sum_{n\ge3}f(n-1)x^n+2\sum_{n\ge3}f(n-2)x^n\\[1ex]
\sum_{n\ge1}f(n)x^n-f(1)x-f(2)x^2&=\left(x\sum_{n\ge2}f(n-1)x^{n-1}-f(1)x^2\right)+2x^2\sum_{n\ge3}f(n-2)x^{n-2}\\[1ex]
F(x)-f(1)x-f(2)x^2&=x\sum_{n\ge1}f(n)x^n-f(1)x^2+2x^2\sum_{n\ge1}f(n)x^n\\[1ex]
F(x)-x-3x^2&=xF(x)-x^2+2x^2F(x)
\end{align}$$
which is easily solved for $F(x)$.
</s>