0
$\begingroup$

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.

$\endgroup$
3

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

This site is temporarily in read-only mode and not accepting new answers.