The recurrence relation is

$$a_n = a_{n-1} + a_{n-2} + n,\quad n\ge 2$$

with initial conditions $a_0 = 0$ and $a_1 = 1$.

I know I need to convert the recurrence into series and I have broken it down, but am struggling with getting it into a proper form to do partial fractions.

I have:

$$f(x) = a_0 + a_1x + x\sum_{n\ge 2} a_{n-1}x^{n-1} + x^2\sum_{n\ge 2} a_{n-2}x^{n-2} + \frac{1}{(1-x)^2}$$

Any insight/help is much appreciated!

  • $\begingroup$ Are you sure about the $n\geq 0$ being the beginning of the summands? You have the first summation beginning with $a_{-1}x^{-1}$ and the second one begins with $a_{-2}x^{-2}. $\endgroup$ Dec 4, 2016 at 4:11
  • $\begingroup$ @DavidSnyder Thanks, you're right, typo on my part. It should be n=2 beginning the summands. $\endgroup$
    – mandib
    Dec 4, 2016 at 4:14

2 Answers 2


Write $F(x)$ as the generating function, then

$$F(x)-x-0= (x+x^2)F(x)+x\left({1\over (1-x)^2}-1\right).$$

Solving gives:

$$F(x) = {x\over (1-x-x^2)(1-x)^2}$$

  • $\begingroup$ Oops. Don't forget the last term, $\frac{1}{(1-x)^2}$. $\endgroup$ Dec 4, 2016 at 4:09
  • $\begingroup$ you forgot the $n$ $\endgroup$
    – Phicar
    Dec 4, 2016 at 4:09
  • 1
    $\begingroup$ @Phicar yeah already caught it, but thanks! $\endgroup$ Dec 4, 2016 at 4:10
  • $\begingroup$ @DavidSnyder yes, and I forgot to take out the constant term from the first one as well @_@ $\endgroup$ Dec 4, 2016 at 4:22
  • 1
    $\begingroup$ @mandib yes, that's the general strategy! :) And sorry for all the edits, keeping track of the little nitty gritty bits is always the devil from the details. $\endgroup$ Dec 4, 2016 at 4:25

Just manipulate the generating function; \begin{align} f(x)=x+\sum_{n=2}^\infty a_nx^n=&x+x\sum_{n=2}^\infty a_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty a_{n-2}x^{n-2}+x\sum_{n=2}^\infty nx^{n-1}\\ =&x+xf(x)+x^2f(x)+x\,\frac{d}{dx}\sum_{n=2}^\infty x^{n}\\ =&x+xf(x)+x^2f(x)+x\,\frac{d}{dx}\underbrace{\left(\frac{1}{1-x}-x-1\right)}_{x^2/(1-x)}\\ =&x+xf(x)+x^2f(x)+x\,\frac{2x-x^2}{(1-x)^2}, \end{align}

and now solve for $f(x)$.


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.