# How to solve the recurrence: T(n) = n*T(n-1) + n?

In a an exercise I'm required to analyze the runtime of recursive function:

 foo(n)
for i from 1 to n
work() // O(1)
foo(n-1)
end for
end foo


The recurrence relation I understand from the code is: T(n) = n*T(n-1) + n

But I'm failing trying to analyze it using the iterative method since I don't see a repeating pattern when I'm opening some of the terms

How do I solve this recurrence ?

• Up to which precision are you expected to solve it? Can you solve it without the $+n$ term? – Raphael Apr 27 '17 at 21:18
• We have collected some useful material here, but I think "guess & proof" is what your teachers expect here. Hint: falling factorials. – Raphael Apr 27 '17 at 21:22
• @Raphael I guess lower and upper bound (theta), as well as figuring out how many times work() will be called as an expression of n – shaqed Apr 27 '17 at 21:23
• So, asymptotics. Ironically, I think the exact figure (in non-closed form) is easier here than a "nice" asymptotic. – Raphael Apr 27 '17 at 21:23
• Possible duplicate of Solving or approximating recurrence relations for sequences of numbers – David Richerby Apr 27 '17 at 23:04

Looks like $$T(n) = n! + \left(\frac{n!}{0!} +\frac{n!}{1!} +\frac{n!}{2!} +\frac{n!}{3!} + \dots + \frac{n!}{(n-2)!} + \frac{n!}{(n-1)!}\right)$$ satisfies the recurrent relation (here $T(0) = 1$).

From this for example $T(n) \leq n!(1+e)$.

• And how do they get there? – Raphael Apr 27 '17 at 22:35

Looking for the pattern (aka "guess and prove") is definitely a workable approach here. Sometimes it's about arranging things in the right way in your head:

(Assuming $T(0) = 0$ as anchor.)

This path leads to an exact solution in terms of "well-known" functions, namely a sum of falling factorials if not a nice closed form. You'd then prove this guess correct using induction, which is elementary here.

Actually, there is a mechanical approach to solve this: using generating functions. Since clearly $T(n) \in \Omega(n!)$, we know we'll have to use exponential generating functions (at least). So, from the ansatz

$\qquad\displaystyle T(z) = \sum_{n \geq 0} t_n \cdot \frac{z^n}{n!} = \sum_{n \geq 1} n \cdot \frac{z^n}{n!} + \sum_{n \geq 1} n \cdot t_{n-1} \cdot \frac{z^n}{n!}$

we obtain, using elementary manipulation of sums/series, that

$\qquad\displaystyle T(z) = ze^z \cdot \frac{1}{1-z}$.

Inserting the well known series for $e^z$ and $(1-z)^{-1}$ and applying the (binomial) convolution, you get the same solution as "seen" above:

$\qquad\displaystyle t_n = \sum_{k=1}^{n} \frac{n!}{(n-k)!}$.

Now, we can rearrange:

$\qquad\displaystyle t_n \ =\ n! \cdot \sum_{k=1}^{n} \frac{1}{(n-k)!} \ =\ n! \cdot \sum_{k=0}^{n-1} \frac{1}{k!} \ \sim\ n! \cdot e$.