$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

Argue by induction. I will prove that

$$n! \le T(n) \le 2 \cdot n!-1$$

Base case $n=1$, it works.

Inductive step, for $n \ge 2$:

$$T(n) = n T(n-1)+1 \ge n((n-1)!)+1 = n! +1 \ge n!$$

and $$T(n) = n T(n-1) +1 \le n (2 \cdot (n-1)! -1) +1 = 2 \cdot n! -n +1 \le 2 \cdot n!-1$$

This concludes the proof that $T(n) = \Theta (n!)$.

Answer 2

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