Find generating function for linear recurrence

Question

Let $a_0=0, a_1=1,$ and $a_{n+2}=2a_{n+1}+a_n.$ Find the closed form for this sequence using generating functions.

---

I'm not sure what to do, I tried getting some cancellation like when solving for Lucas/Fibonacci numbers but I'm not sure how to.

Answer 1

characteristic equation:

$x^2=2x+1$

$x = 1 \pm \sqrt 2$;

the homogeneous form: will be $$a_n = r(1 + \sqrt 2)^n + s(1 - \sqrt 2)^n$$

the particular solution: since $a_0$ = 0 and $a_1$ = 1 then $r + s = 0$ and $(1 + \sqrt 2)r + (1 - \sqrt 2)s = 1$

$$r=\frac{\sqrt 2}{4}, s=-\frac{\sqrt 2}{4}$$

the general solution:

$$a_n = \frac{\sqrt 2}{4} \left(1 + \sqrt 2\right)^n -\frac{\sqrt 2}{4} \left(1 - \sqrt 2\right)^n$$

Answer 2

$$a_0=0, a_1=1\\a_{n+2}=2a_{n+1}+a_n\tag{1}$$ Let $$f(x)=\sum_{n=0}^{\infty}a_nx^n$$ multiply both sides of $(1)$ by $x^n$ and sum from $n=0$ to $\infty$

$$\sum_{n=0}^{\infty}a_{n+2}x^n=2\sum_{n=0}^{\infty}a_{n+1}x^n+\sum_{n=0}^{\infty}a_nx^n\tag{2}$$ We have $$\sum_{n=0}^{\infty}a_{n+2}x^n=\frac{1}{x^2}\sum_{n=0}^{\infty}a_{n+2}x^{n+2}=\frac{1}{x^2}\left(f(x)-a_0-a_1x\right)=\frac{1}{x^2}\left(f(x)-x\right)$$

$$\sum_{n=0}^{\infty}a_{n+1}x^n=\frac{1}{x}\sum_{n=0}^{\infty}a_{n+1}x^{n+1}=\frac{1}{x}\left(f(x)-a_0\right)=\frac{f(x)}{x}$$

Thus $(2)$ can be written as $$\frac{1}{x^2}\left(f(x)-x\right)=2\frac{f(x)}{x}+f(x)$$ and then $$f(x)=\frac{x}{1-2x-x^2}$$