# Recurrence relation using generating function no solution

I have a problem with the solution of this recurrence relation:$$a_{n+2}=2a_{n+1}-a_n+1\qquad(n≥1),\ a_0=0,\ a_1=1$$

I found the generating function, then I used partial fraction decomposition to find the solution, but I have no solution for the system of equations. This is what I did:$$\frac 1{x^2} \sum_{n=0}^\infty a_{n+2}x^{n+2}=\frac 1x\sum_{n=0}^\infty 2a_{n+1}x^{n+1}-\sum_{n=0}^\infty a_{n}x^n+\sum_{n=0}^\infty x^n$$$$\frac1{x^2}(f(x)-x)=\frac2xf(x)-f(x)+\frac1{1-x}$$$$f(x)(\frac1{x^2}-\frac2x+1)=\frac 1x+\frac 1{1-x}$$$$f(x)(\frac{1-2x+x^2}{x^2})=\frac1{(1-x)x}$$$$f(x)=\frac x{(x-1)^2(1-x)}$$ Then I did partial fraction decomposition: $$\frac A{(x-1)}+\frac B{(x-1)^2}+\frac C{(1-x)}$$$$Ax-Ax^2-A+Ax+B-Bx+Cx^2-2Cx+C$$Finally I have the system of equations $$\left\{ \begin{array}{c} -A+C=0 \\ 2A-B-2C=1\\ -A+B+C=0 \end{array} \right.$$ which has no solutions. Where am I wrong?

• Note: $(x-1)^2=(1-x)^2,$ so $(x-1)^2(1-x)=(1-x)^3,$ so you should have $\dfrac C {(1-x)^3}$ – J. W. Tanner Jun 16 '19 at 15:29

One place you went wrong: $$f(x)=\dfrac x{(x-1)^2(1-x)}=\color{red}{\dfrac x {(1-x)^3}}$$ has partial fraction decomposition $$\frac A{(1-x)}+\frac B{(1-x)^2}+\frac C{(1-x)^3}.$$