Take the 2-minute tour ×

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|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

1 Answer 1

up vote 10 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|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. –  Looft 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


