Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$ I'm trying to solve the following problem: 

Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$.  Is $T(n) \in \mathcal O(2^n)$?

I started by finding the time complexity of $T(n) = n\cdot T(n-1) + n$ and I got something weird:
$$n!\cdot\left(\frac{1}{n!} + \frac{1}{(n-1)!} + \cdots + \frac{1}{(n-n)!}\right)$$
I found this by drawing a tree and simplifying the expression I got, but it doesn't really make sense.
 A: Just let us see what we get if we expand  $T(n) = n⋅T(n-1) + n$:
\begin{align}T(n) &= n⋅T(n-1) + n\\
      &= n⋅((n-1)⋅T(n-2) + n-1) + n\\
      &= n⋅((n-1)⋅((n-2)⋅T(n-3) + (n-2)) + (n-1)) + n\\
      &= n⋅(n-1)⋅(n-2)⋅T(n-3) + n⋅(n-1)⋅(n-2) + n⋅(n-1) + n\\
      &= \sum_{k=1}^n \frac{n!}{k!}
\end{align}
Since $n!$ is a summand of this sum and with $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ (see Stirling's approximation), we know 
$$\lim_{n\to\infty} \frac{n!}{2^n} \approx \lim_{n \to\infty} \frac{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{2^n} = \frac{n^n}{(2e)^n} \to \infty$$
So there does not exist any constant $c$ to fulfill $T(n) \leq c\cdot 2^n$ for every $n \geq n_0$, so $T(n)$ cannot be in $\mathcal O(2^n)$. Or in other words: $T(n)$ is in $\omega(2^n)$.
Notice: I ignored the biggest part of the sum, but to show that $T(n)$ is not in $\mathcal O(2^n)$, we don't have to look at the whole sum, but only on this part, that is big enough to see that $T(n)$ is not in $\mathcal O(2^n)$.  
An easier approach: $T_1(n) = n⋅T_1(n-1) + n$ is greater than $T_2(n) = n\cdot T_2(n-1)$, so if $T_2(n)$ is not in $\mathcal O(2^n)$, this holds for $T_1(n)$ too.
A: Suppose that $T(n)=\Theta (2^n)$.  Then your recurrence would become
$$Θ(2^n) = n\cdot\Theta(2^n-1) + n = n\cdot \Theta(2^n)$$
...which is false.
Your explicit formulation is actually more informative.  If you reverse what's in the parentheses, you can write it as:
$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$$  
As $n$ grows, this converges to $e$ (which means that we can bound it by a constant).  So you've found that $T(n)=\Theta(n!)$, which does agree with your recurrence.
