Solve a recurrence relation $D_{n} = nD_{n-1} + (n-1)!$

Question

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.

Answer 1

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

$$a_n=a_{n-1}+\frac1n\;.$$

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.