Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

As the title states, I need a solution of this recurrence but I'll provide my own solution and ask if there is an easier, simpler solution using some deeper knowledge about recurrence relations.

$$D_{n} = nD_{n-1} + (n-1)!$$ $$D_{n} = n[(n-1)D_{n-2} + (n-2)!] + n!\frac{1}{n}$$ $$D_{n} = n(n-1)[(n-2)D_{n-3} + (n-3)!] + n!\left(\frac{1}{n} + \frac{1}{n-1}\right)$$ $$\vdots$$ $$D_{n} = n!D_{1} + n!\left(\frac{1}{1} + \ldots + \frac{1}{n}\right)$$ $$D_{n} = n!\left( D_{1} + 1 + \frac{1}{2} + \ldots + \frac{1}{n}\right)$$

Now, my question is, how can one avoid the inductive solution and solve the recurrence with some other tools?

Any books on the subject or areas of mathematics which would make things simpler?

Currently, I only have the knowledge of solving them using Euler's substitution and some other smart tricks which assume the solution has polynomial or exponential form when recurrence is non-homogeneous etc. But!, when factorials are there only thing I can assume is that the solution is of factorial form but that isn't the case here.

share|cite|improve this question
The subject's name of this kind of problems is "(finite) difference equations". A good book about it: "An introduction to difference equations", by Saber Elaydi, Springer UTM. – a.r. Jan 10 '13 at 7:24
up vote 8 down vote accepted

Starting with $D_{n} = nD_{n-1} + (n-1)!$, divide through by $n!$ and let $a_n=\frac{D_n}{n!}$ to get


Clearly $a_n=H_n+a_0$, where $H_n$ is the $n$-th harmonic number, and $D_n=n!H_n+a_0n!$.

I strongly recommend the book Concrete Mathematics, by R.L. Graham, D.E. Knuth, and O. Patashnik; it contains a great many techniques for dealing with such problems.

share|cite|improve this answer
Thanks! The book has been on my to read list for a year now. Went through first two chapters but never finished it. – user48724 Jan 9 '13 at 18:18
@Leolinus: You’re welcome! (And it really is a very good book.) – Brian M. Scott Jan 9 '13 at 18:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.