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 😀

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s