Closed form for $T(1) = K, T(x) = xT(x-1) + x$?

Question

I'm looking for a closed form for the following recurrence:

$T(1) = K$

$T(x) = xT(x-1) + x$

I know it is factorial-like but I am unable to get an exact answer.

Answer 1

$$\begin{align*} T(n)&=nT(n-1)+n\\ &=n\Big((n-1)T(n-2)+(n-1)\Big)+n\\ &=n(n-1)T(n-2)+n(n-1)+n\\ &=n(n-1)\Big((n-2)T(n-3)+(n-2)\Big)+n(n-1)+n\\ &=n(n-1)(n-2)T(n-3)+n(n-1)(n-2)+n(n-1)+n\\ &\;\vdots\\ &=\left(\prod_{k=2}^nk\right)T(1)+\prod_{k=2}^nk+\prod_{k=3}^nk+\ldots+\prod_{k=n}^nk\\ &=Kn!+\sum_{i=2}^n\prod_{k=i}^nk\\ &=Kn!+\sum_{i=2}^n\frac{n!}{(i-1)!}\\ &=Kn!+\sum_{k=1}^{n-1}\frac{n!}{k!}\\ &=\left(K+\sum_{k=1}^{n-1}\frac1{k!}\right)n!\;, \end{align*}$$

which you can verify by induction if you like.

Now $$e^x=\sum_{k\ge 0}\frac{x^k}{k!}=1+\sum_{k\ge 1}\frac{x^k}{k!}\;,$$ so $$\sum_{k\ge 1}\frac1{k!}=e-1\;.$$ The series converges rapidly, so $T(n)\approx(K+e-1)n!$.

Answer 2

$T(x) = (K-1) x! + x e \Gamma(x,1)$ where $\Gamma(x,1) = \int_1^\infty e^{-t} t^{x-1}\ dt$ is an incomplete Gamma function.

Answer 3

Using the method I outlined in this answer, and substituting $S_{n}=T(n+1)$, we have a recurrence relationship in the form $(2)$ with:

$$a_{n}=1\qquad b_{n}=n\qquad c_{n}=n$$

We therefore have our summation factor $s_{n}$ as $\frac{1}{n!}$, therefore using equation $(4)$ in the linked answer, we get:

$$S_{n}=n!\left(K+\sum_{k=1}^{n}{\frac{k}{k!}}\right)={\rm e}\Gamma(n+1,1)+K(n+1)!-1,$$

Where $\Gamma(n+1,1)=\int_{1}^{\infty}{t^{n}{\rm e}^{-t}\:dt}$ is the incomplete gamma function.

Therefore, as we have $S_{n}=T(n+1)$, we have $T(n)=S_{n-1}={\rm e}\Gamma(n,1)+Kn!-1$.