<s>[INST] 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!
 [/INST] 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$.
</s>