# Find generating function for linear recurrence [closed]

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.

$$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}$$

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

• I edited your $\LaTeX$. Check if I changed something wrong and look how to use mathJax more effectively Dec 23, 2020 at 20:32
• yes, I saw thank you it looks more polished now Dec 23, 2020 at 20:36
• I already checked the r was (1 +r \sqrt 2) now it's fine (1 + \sqrt 2)r + (1 - \sqrt 2)s = 1 thanks Dec 23, 2020 at 20:39
• If you like MSE and want to go on contributing, I strongly recommend to learn at least the basics of LaTeX Dec 23, 2020 at 20:47