[Math] $T(n) = nT(n-1) + 1$ with $T(1)=1$

Question

I'm trying to figure out the order class of this recursion:

\begin{align}
T(n) &= n\cdot T(n-1) + 1 \\
T(1) &= 1
\end{align}

I have to answer it, using the tree method.

I've done a little research and came to idea the solution is $Θ(n!)$.

But from what I've tried to do, I'm stuck with no clue how to continue

\begin{equation}
\begin{split}
T(n) = 1 + n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots\\
+ n(n-1)(n-2)\cdot\ldots\cdot4\cdot3\cdot2
\end{split}
\end{equation}

Thank you.

Answer 1

You've essentially got $T(n) = n!\displaystyle\sum_{k=1}^{n}\frac{1}{k!}$. It follows that $n! \leqslant T(n) < (e-1) n!$.