Find a closed formula for $\sum_{n\geq 0} f(n)x^n.$

Question

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?

Answer 1

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)$.