Solve $2a_{n-2} = a_n + a_{n-1}$ using generating function Need to solve:
$$2a_{n-2} = a_n + a_{n-1}$$
with: $a_0 = 0$ and $a_1=1$
I get:
$$f(x) = \frac{2x^3-x^2-x}{2x^2-x-1}$$ so I tried to scompose the denominator and I get:
$$f(x) = \frac{2x^3-x^2-x}{(x-1)(x+\frac{1}{2})}$$ now I think I have to use partial fraction but in this case I do not see any $x^3$ coming out so how should I procede?
$$\frac{A}{x-1}+\frac{B}{x+\frac{1}{2}}$$
 A: I think you committed a typo in calculations. From:
$$a_n=2a_{n-2}-a_{n-1}$$
we should have:
$$f(x)=\sum\limits_{n=0}\color{blue}{a_{n}}x^{n}=
x+\sum\limits_{n=2}a_nx^n=
x+\sum\limits_{n=2}\left(2a_{n-2}-a_{n-1}\right)x^n=\\
x+2x^2\left(\sum\limits_{n=2}a_{n-2}x^{n-2}\right)-x\left(\sum\limits_{n=2}a_{n-1}x^{n-1}\right)=\\
x+2x^2\left(\sum\limits_{n=0}a_{n}x^{n}\right)-x\left(\sum\limits_{n=1}a_{n}x^{n}\right)=x+2x^2f(x)-xf(x)$$
and
$$\color{red}{f(x)=\frac{x}{1+x-2x^2}}=\frac{1}{3(1-x)}-\frac{1}{3(1+2x)}=\\
\sum\limits_{n=0}\frac{1}{3}x^n-\sum\limits_{n=0}\frac{1}{3}(-2)^nx^n=
\sum\limits_{n=0}\color{blue}{\frac{1-(-2)^n}{3}}x^n$$
and (also agrees with wolfram)
$$a_n=\frac{1-(-2)^n}{3}$$
A: There's an error in the factorisation of the denominator. You should get
$$f(x) = \frac{2x^3-x^2-x}{(x-1)(2x+1)}.$$
Now this isn't a proper rational function (i.e. the degree of the numerator is not $<$ degree of the denominator). So (in theory) you have to perform the Euclidean division of the numerator by the denominator first.
However, observe that
$2x^3-x^2-x=x(2x^2-x-1)$,
so the ‘fraction’ simplifies to $\color{red}x$.
