# Factorial asymptotics

This post complements the previous TSP-related post by analyzing some asymptotic properties of the factorial.

#### n! vs n·2n

Let’s start by defining both functions as products:

$\displaystyle n! = \prod_{i=2}^n i$

$\displaystyle n\cdot 2^n = n \prod_{i=1}^n 2$

Extracting some factors:

$\displaystyle n! = n (n - 1) \prod_{i=2}^{n-2} i$

$\displaystyle n\cdot 2^n = n\cdot 2^3 \prod_{i=2}^{n-2} 2$

We can see that

$\displaystyle \prod_{i=2}^{n-2} i \ge \prod_{i=2}^{n-2} 2$,

as it has the first product has the same number of factors and is greater or equal factor by factor. On the other hand, for n greater or equal than 9,

$\displaystyle n (n - 1) \ge n\cdot 2^3$.

Combining this results, for n greater or equal than 9:

$\displaystyle n (n - 1) \prod_{i=2}^{n-2} i \ge n\cdot 2^3 \prod_{i=2}^{n-2} 2$

$\displaystyle n! \ge n\cdot 2^n$.

This is a conservative result, as the factorial is greater starting from n = 6.

#### A bound for the factorial values

One useful way of bounding sums of monotonically growing sequences whose terms follow a relatively simple function is by using the integral of the function. This applies the following identities:

(assuming $\displaystyle a_i = f(i)$ and monotonically growing $f$)

$\displaystyle \sum_{i=1}^n a_i = \sum_{i=1}^n \int_i^{i+1} dx\,f(i) = \sum_{i=1}^n \int_i^{i+1} dx\,f(\lfloor x \rfloor) \le \sum_{i=1}^n \int_i^{i+1} dx\,f(x)$

$\displaystyle \sum_{i=1}^n a_i \le \int_1^{n+1} dx\,f(x)$

$\displaystyle \sum_{i=1}^n a_i = \sum_{i=1}^n \int_{i-1}^i dx\,f(i) = \sum_{i=1}^n \int_{i-1}^i dx\,f(\lceil x \rceil) \ge \sum_{i=1}^n \int_{i-1}^i dx\,f(x)$

$\displaystyle \sum_{i=1}^n a_i \ge \int_0^n dx\,f(x)$.

The factorial is the product of a simple sequence, not a sum, but we can use logarithms to bridge this gap:

$\displaystyle n! = \exp\left( \ln \prod_{i=1}^n i\right) = \exp\left( \sum_{i=1}^n \ln i\right)$.

So, applying the previously found bounds for sums, we get:

$\displaystyle \int_0^n dx\,\ln x \le \sum_{i=1}^n \ln i \le \int_1^{n+1} dx\,\ln x$

$\displaystyle \int_0^n dx\,\ln x \le \ln n! \le \int_1^{n+1} dx\,\ln x$.

Integrating by parts the logarithm function:

$\displaystyle \int dx\,\ln x = \int dx\,1\cdot\ln x$

$\displaystyle \int dx\,\ln x = x \ln x - \int dx\,x\cdot x^{-1}$

$\displaystyle \int dx\,\ln x = x \ln x - \int dx$

$\displaystyle \int dx\,\ln x = x \ln x - x$.

Putting all together:

$\displaystyle n \ln n - n \le \ln n! \le (n + 1) \ln(n + 1) - (n + 1) + 1$

$\displaystyle n \ln n - n \le \ln n! \le (n + 1) \ln(n + 1) - n$.

As the exponential function grows monotonically, we can apply it to all the members of the inequality:

$\displaystyle \exp(n \ln n - n) \le n! \le \exp\left((n + 1) \ln(n + 1) - n\right)$.

Rearranging:

$\displaystyle e^{-n}n^n \le n! \le e^{-n}(n + 1)^{n+1}$.

There are tighter bounds for the factorial, such as the Stirling’s series. But they are harder to prove 😀