Recurrence relation using generating function no solution

Question

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?

Answer 1

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

Answer 2

If your aim is to find a closed-form expression for $a_n$ then I know 2 more ways to go about it:

1. Assume $a_n = \alpha^n$ and a simple substitution to the recurrence formula should yield $\alpha^{n+3} - 3\alpha^{n+2} + 3\alpha^{n+1} - \alpha^{n} = 0$ which gives $\alpha^{3} - 3\alpha^{2} + 3\alpha - 1 = 0$ or $({\alpha-1})^3 = 0$. Clearly $\alpha=1$ or $a_n=1$ is a valid solution.

2. Another way could be to see the differences of consecutive terms in the series. If you keep taking differences of consecutive terms in the series and then repeat for the series thus obtained, at the $3^{rd}$ level the series becomes $1,1,1,1$. This leads us to the conclusion that $a_n$ can be written as $an^3 + bn^2 + cn + d$. We can write the first 4 terms and solve equations for a, b, c, and d to get a nice polynomial expression for $a_n$.