Stirling work
Problem
You are going to use a computer to work out the values of
$\sqrt{n}$, $n^n$ and $e^{-n}$ for a few values of the whole number
$n$.
Before you start, can you estimate values of $n$ beyond which each
function is larger than $100$, $1\,000\, 000$ or $1\,000\,
000\,000\, 000$? It would be great if you could specify as tight a
range as possible between which you know these values will be
exceeded.
Try them out on a computer. How close were you?
Excel can cope with numbers up to about $10^{308}$ (to a precision
of 16 places) What values of $n$ do you think will cause Excel to
break down for each function. Were you correct?
For large n, the factorial function can be approximated very well
with an expression of the following form:
$$n! \sim A n^{\pm n\pm 0.5} e^{\pm n}$$
Your challenge is to experiment using a calculator or
spreadsheet to find the constant $A$ and whether or not each $\pm$
is $+$ or $-$
Warning: You will need to think
about this task, as although the approximation gives a smaller and
smaller percentage error as $n$ increases, the absolute error
increases as $n$ increases!
When you find the correct form of the formula, can you numerically
calculate some large factorials to 8 significant figures? How large
a factorial will you be able to calculate?
You can now use this formula algebraically to perform calculations
beyond the limit of the computer. For example, you can estimate the
chance of getting $500$ heads if you toss a coin $1000$ times or
(equivalently) the number of ways of choosing $500$ people from a
group of $1000$ people.
Student Solutions
Part 1: Estimate of n
$\sqrt{n} > 100$
$n> 10^4$
$\sqrt{n} > 1000\ 000$
$n> 10^{12}$
$\sqrt{n} > 1000\ 000\ 000\ 000$
$n> 10^{24}$
$n^n> 100$
$n\log n> \log 100$
Using the interval bisection method: $n$ is greater than 3.59728502354042
$n^n> 1000\ 000$
$n\log n> \log 1\ 000\ 000$
Using the interval bisection method: $n$ is greater than 7.06579672829962
$n^n> 1000\ 000\ 000\ 000$
$n\log n> \log 1000\ 000\ 000\ 000$
Using the interval bisection method: $n$ is greater than
11.3673178030006
Interval
Bisection tables
Part 2:
$n!=1 \times 2 \times 3 \times 4 \times \dots (n-1) \times
n$
Taking logs:
$$
\begin{align*} \ln(n!) &= \ln (1 \times 2 \times 3 \times 4
\times \dots (n-1) \times n) \\&= \ln 1 + \ln 2 +\ln 3
+...\ln(n-1) +\ln(n) \\&= \sum_{i=1}^n\ln(i)
\approx\int^n_1\ln(x)\,dx
\end{align*}$$
where we've assumed n is large when replacing the sum by an integral. We can evaluate this integral using integrating by parts:
$$ \int \ln(x) \,dx = x \ln(x) - \int 1 \,dx = x\ln(x) - x =
\ln(x^x) - x$$
Substituting the limits of integration gives: $$\ln(n!) = \ln(n^n)
-n - (\ln(1^1) - 1)$$
Taking exponentials: $$n!= e^{\ln(n^n) -n + 1}=n^n e^{1-n}$$
Comparing with the form of the approximation given (for large n)
it can be seen that we should use the approximation:
$$n! \sim A n^{ +n\pm 0.5} e^{-n} $$
We now need to find the value of the constant A and work out the
remaining sign in the term $n^{\pm0.5}$.
If we temporarily let the constant $= 1$ and then compare the
values obtained from $An^{n-0.5}e^{-n}$ and $An^{n+0.5}e^{-n}$ with
$n!$ for a range of $n$, the results are listed in the spreadsheet
below.
Spreadsheet
From the spreadsheet it can be seen that $An^{n+0.5}e^{-n}$ with a
constant $A$ greater than unity, will provide the appropriate form.
If we were to use the other possible form, $An^{n-0.5}e^{-n}$, we
would need an extremely large value of $A$.
Estimate of $A$:
By simply dividing column E by coumn D in the above spreadsheet it
can be seen the value of $A$ starts at around 2.6 (for small $n$)
and tends to around 2.5 (for large $n$). The exact value of $A$ is
actually $\sqrt{2\pi} \approx 2.506628275$
Part 3:
There appears to be no limit to the factorial which may be
calculated if the answer is left in an algebraic form. Using the
formula in Excel, $142!$ was the largest number that I was able to
compute. The value of the real and approximated results are listed
below.
$142!= 2.695364137888160 \times 10^{245}$
$\sqrt{2\pi} \times 142^{142 +0.5}e^{-142} =2.693782818480670
\times 10^{245}$
Percentage difference = 0.058668118 %