Recurrence relations of the form $T(n) = n T(n-1) + ...$

Question

In the analysis of algorithms, you often get recurrence relations of the form $$ T(0) = 1 \\ T(n) = n T(n - 1) + f(n) $$ where the $f(n)$ varies depending on the details. For certain $f$, the solution is well-known. For example if $f(n)$ is in $\Theta(n)$, the solution is $\Theta(n!)$. Or if $f(n) = n!$, the solution is $\Theta((n+1)!)$.

But I sometimes encounter situations where I don't have an answer. For example, I have no idea what happens if $f$ is a higher-degree polynomial, or if $f = (n+1)!$. When does the switch from $\Theta(n!)$ to $\Theta((n+1)!)$ occur? How "bad" may $f$ be for $T(n)$ to still stay within the $\Theta((n+1)!)$ bound?

So my question is whether there is a kind of Master Theorem or general rule for this form of recurrence relation.

Answer 1

The sequence $\left(\frac{T(n)}{n!}\right)_{n\geqslant 0}$ verifies the recursive relation $$ \frac{T(n)}{n!}=\frac{T(n-1)}{(n-1)!}+\frac{f(n)}{n!} $$ Summing this identity gives $$ T(n)=n!\left(1+\sum_{k=1}^n\frac{f(k)}{k!}\right) $$ Therefore if $f(n)=(n+1)!$, then $T(n)\underset{n\rightarrow +\infty}{\sim} \frac{n^2}{2}n!$, or if $f(n)=\sum_{i=0}^p a_in^i$ with $a_p\neq 0$, then $$ T(n)=n!\left(1+\sum_{i=0}^p a_i\sum_{k=1}^n\frac{k^i}{k!}\right)=\Theta(n! ) $$

Answer 2

We have for any $ k\in\mathbb{N}^{*} $ : \begin{aligned}\frac{T\left(k\right)}{k!}=\frac{T\left(k-1\right)}{\left(k-1\right)!}+\frac{f\left(k\right)}{k!}\end{aligned}

Thus for any $ n\in\mathbb{N}^{*} $ : \begin{aligned}\sum_{k=1}^{n}{\left(\frac{T\left(k\right)}{k!}-\frac{T\left(k-1\right)}{\left(k-1\right)!}\right)}&=\sum_{k=1}^{n}{\frac{f\left(k\right)}{k!}}\\ \iff\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \frac{T\left(n\right)}{n!}-1&=\sum_{k=1}^{n}{\frac{f\left(k\right)}{k!}}\\ \iff \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\left(n\right)&=n!\left(1+\sum_{k=1}^{n}{\frac{f\left(k\right)}{k!}}\right)\end{aligned}