Closed form for $T(1) = K, T(x) = xT(x-1) + x$? 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.
 A: $$\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!$.
A: $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. 
A: 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$.
