Computing good bounds for $P(n) = n + nP(n-1)$ What is the technique of computing the following recurrence?
$$P(n) = n + nP(n-1)$$
(We assume $P(1) = 1$.)
It is obvious that the lower bound for $P(n)$ is $n!$, and the upper bound is $(n+1)!$, which is pretty good information already. I've been wondering, however, if it's possible to improve those bounds or solve the recurrence exactly.
 A: I don't know of any exact solution, but a quick way to get a more precise bound would be to consider the ratio of $P(n)$ and $n!$. More precisely, define
$$f(n)=\frac{P(n)}{n!}$$
and then note that it satisfies the recurrence relation
$$f(n)=\frac{1}{(n-1)!}+f(n-1).$$
This can be somewhat advantageously rewritten as:
$$f(n)=\sum_{i=0}^{n-1}\frac{1}{i!}$$
from where we can easily derive that
$1\leq f(n)\leq \sum_{i=0}^{\infty}\frac{1}{i!}=e$ which yields the bound
$$n!\leq P(n) \leq e\cdot n!.$$
This is a reasonably tight bound (giving us the function within a constant factor), and, as we additionally have that $\lim_{n\rightarrow\infty}\frac{P(n)}{n!}=e$, gives us a very good idea of the growth rate of the function.

Actually, by considering the two expressions
$$n!\left(\frac{1}{0!}+\frac{1}{1!}+\ldots +\frac{1}{(n-1)!}\right)$$
and
$$n!\left(\frac{1}{0!}+\frac{1}{1!}+\ldots +\frac{1}{(n-1)!}+\frac{1}{n!}+\frac{1}{(n+1)!}+\ldots\right)=n!\cdot e$$
we find that the difference is
$$\frac{n!}{n!} + \frac{n!}{(n+1)!}+\frac{n!}{(n+2)!}+\ldots$$
which is between $1$ and $2$ for $n\geq 1$. Thus, a closed form is as follows:
$$P(n)=\lfloor e\cdot n!\rfloor - 1$$
where $\lfloor \cdot \rfloor$ is the floor function.
A: This is not an answer but it is probably too long for a comment
Using a CAS, if $P(1)=1$, the solution of the recurrence equation $$P_n = n + n\,P_{n-1}$$ is given by $$P_n=e\, n\, \Gamma (n,1)$$ where appears the incomplete gamma function and then $P_n<e\, n!$. 
In fact, the value of $P_n$ is very close to the upper bound since $P_4=64$ while $4! e\approx 65.2388$,  $P_5=325$ while $5! e\approx 326.194$,,  $P_6=1956$ while $6! e\approx 1957.16$.
According to $OEIS$ (sequence $A007526$) $P_n=\lfloor e n!-1\rfloor $.
A: Applying a standard method,
if
$P(n) = n + nP(n-1)
$,
then
$\frac{P(n)}{n!} = \frac1{(n-1)!} + \frac{P(n-1)}{(n-1)!}
$.
Let
$Q(n) = \frac{P(n)}{n!}
$.
Then
$Q(n)
=\frac1{(n-1)!}+Q(n-1)
$,
or
$Q(n)-Q(n-1)
=\frac1{(n-1)!}
$.
Summing from
$n=1$ to $m$,
$\sum_{n=1}^{m}(Q(n)-Q(n-1))
=\sum_{n=1}^{m}\frac1{(n-1)!}
$
or
$Q(m)-Q(0)
=\sum_{n=0}^{m-1}\frac1{n!}
$.
Therefore
$\frac{P(m)}{m!}-\frac{P(0)}{0!}
=\sum_{n=0}^{m-1}\frac1{n!}
$
or
$P(m)
=m!P(0)+m!\sum_{n=0}^{m-1}\frac1{n!}
$.
Since
$\sum_{n=0}^{m-1}\frac1{n!}
\approx e
$,
$P(m)
=m!(P(0)+e)
$.
A: Via generating sequences:
Let $g(x) = \sum_{n=1}^\infty P(n)x^n$.  We note that
$$
\sum_{n=2}^\infty nP(n-1)x^n = \\
\sum_{n=1}^\infty (n+1)P(n)x^{n+1} =\\
x \frac{d}{dx}\left(\sum_{n=1}^\infty P(n)x^{n+1} \right) =\\
x g'(x)
$$
Now, by our recurrence relation, we have
$$
P(n) - nP(n-1) = n \implies\\
\sum_{n=2}^\infty (P(n) - nP(n-1))x^n = \sum_{n=2}^\infty nx^n \implies\\
(g(x) - P(0)) - x\,g'(x) = - \frac{(x-2)x^2}{(x-1)^2} \implies\\
g'(x) - \frac 1x g(x) = \frac{(x-2)x^2}{(x-1)^2} - 1
$$
This is a differential equation that can be solved for $g$.  Once we have $g$, we can find the Taylor expansion of $g$ centered at $x = 0$.  The coefficients of this expansion are the solution to our recurrence relation.
