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

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.

-
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. – Agustí Roig Jan 10 at 7:24

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!$.