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?

  • 2
    $\begingroup$ 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}$ $\endgroup$ – 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}.$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.