Computing good bounds for $P(n) = n + nP(n-1)$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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