How to solve recurrence $T(n) = nT(n - 1) + 1$ Assume $T(n) = \Theta(1)$ for $n \leq 1$. Using iterative substitution.
So far I have:
\begin{align*}
&T(n) = nT(n - 1) + 1\\
&= n((n - 1)T(n - 2) + 1) + 1\\
&= n(n - 1)T(n - 2) + n + 1
\end{align*}
I'm stuck on how I'm supposed to get the asymptotic value from this. Or how would I keep expanding? Thanks!
 A: Method 1: Iteration
What you have so far is good. Just keep going!
Here are the next two iterations, to help you:
\begin{align*}
T(n) &= n(n-1)(n-2)T(n-3) + n(n-1) + n + 1 \\
T(n) &= n(n-1)(n-2)(n-3)T(n-4) + n(n-1)(n-2) + n(n-1) + n + 1
\end{align*}
Do you see the pattern? (It's not so obvious!)
Method 2: Generating Functions
Using the exponential generating function $F(x) = \sum_n T(n) x^n / n!$, from
$$
T(n)\frac{x^n}{n!} = n T(n-1) \frac{x^n}{n!} + \frac{x^n}{n!}
$$
we get
$$
F(x) = xF(x) + e^x + T(0) - 1.
$$
Therefore, with $c = T(0) - 1$,
$$
F(x) = \frac{e^x + c}{1-x}.
$$
It follows that the coefficient of $x^n$ is
$$
c + \sum_{i=0}^n \frac{1}{i!}
$$
so that
$$
T(n) = cn! + \sum_{i=0}^n \frac{n!}{i!}.
$$
In fact, for $n \ge 1$ the latter sum is less than $e \cdot n!$ but bigger than $e \cdot n! - 1$, and is also an integer. So we get
$$
T(n) = c \cdot n! + \lfloor{e \cdot n!\rfloor},
$$ 
for $n \ge 1$. For $n = 0$, the floor formula does not work, and we just have $T(0) = c + 1$.
A: As I've said here before,
when a recurrence has a $n$ in it,
$n!$ or $(n+1)!$
usually helps.
You have
$T(n) = nT(n - 1) + 1
$.
After staring at this for a bit,
I decide to divide
by $n!$.
This becomes
$\frac{T(n)}{n!} = \frac{T(n - 1)}{(n-1)!} + \frac1{n!}
$.
Letting
$u(n)
=\frac{T(n)}{n!}
$,
this becomes
$u(n)
=u(n-1)+\frac1{n!}
$
or
$u(n)-u(n-1)=\frac1{n!}
$.
Summing from $2$ to $n$,
$u(n)-u(1)
=\sum_{k=2}^n \frac1{k!}
$
so
$u(n)=u(1)+\sum_{k=2}^n \frac1{k!}
$.
Replacing
$u(n)
=\frac{T(n)}{n!}
$,
$\frac{T(n)}{n!}=T(1)+\sum_{k=2}^n \frac1{k!}
$
or
$T(n)=n!(T(1)+\sum_{k=2}^n \frac1{k!})
$.
