# find closed form for recurrence relation using generating function

I have this recurrence relation:

$$$$\begin{cases} a_n = 2a_{n-1} + n & (n\geq1)\\ a_0 = 1 \end{cases}$$$$

Set:

$$f(x) = \sum_{n=0}^\infty a_nx^n$$

I solved in this way:

$$\sum_{n=1}^\infty a_nx^n = 2\sum_{n=1}^\infty a_{n-1}x^n + \sum_{n=1}^\infty nx^n$$ $$f(x)-1 = \frac{2}{x}\big(f(x)-1\big) + \frac{1}{1-x}-1$$ $$f(x)-1 = \frac{2}{x}\big(f(x)-1\big) + \frac{1}{(1-x)^2}-1$$ $$f(x)\big(1-\frac{2}{x}\big) = \frac{-2(1-x)^2+x}{x(1-x)^2}$$

$$f(x) = \frac{-2x^2+5x-2}{(1-x)^2(x-2)}$$

and then I get:

$$f(x) = \frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{x-2}$$

but the result I get is:

$$$$\begin{cases} A = 2\\ B=-1\\C=0 \end{cases}$$$$

Don't think that $c=0$ is possible, where is the mistake?

I think that mistake is at $\sum_{n=1}^\infty nx^n$:
• Yeah, that's the mistake. now I get $\frac{x^3-3x^2+x-2}{x^3-4x^2+5x-2}$ how should I procede? – Christian Giupponi Jan 27 '18 at 15:49
• $$\frac{x^3-3x^2+x-2}{x^3-4x^2+5x-2} = 1+\frac{x^2-4x}{x^3-4x^2+5x-2}$$ – Aqua Feb 1 '18 at 13:48
• Now $$\frac{x^2-4x}{x^3-4x^2+5x-2} = {a\over x-1}+ {b\over (x-1)^2}+{c\over x-2}$$ – Aqua Feb 1 '18 at 13:49
• sorry @christian I have noticed an error in my excercise. the second sum should be $2x$ instead of $\frac{2}{x}$? – Christian Giupponi Feb 5 '18 at 10:20