chap9.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

e^{O(f(n))}&=1+O\bigl(f(n)\bigr)\,,
&\qquad\hbox{if\/ $f(n)=O(1)$}.\eqno\eqref|o-e|\cr
\enddisplay
(Here we assume that $n\to\infty$; similar formulas hold for
 $\ln\bigl(1+O(f(x))\bigr)$
and
 $e^{O(f(x))}$
 as $x\to0$.) For example, let $\ln\bigl(1+g(n)\bigr)$
be any function belonging to the left side of \eq(|o-ln|). Then there are
constants $C$, $n_0$, and~$c$ such that
\begindisplay
\bigl\vert g(n)\bigr\vert\le C\bigl\vert f(n)\bigr\vert\le c<1\,,
\qquad\hbox{for all $n\ge n_0$}.
\enddisplay
It follows that the infinite sum
\begindisplay
\ln\bigl(1+g(n)\bigr)=g(n)\cdot\bigl(\textstyle1-\half g(n)+{1\over3}g(n)^2
 -\cdots\,\bigr)
\enddisplay
converges for all $n\ge n_0$, and the parenthesized series is
bounded by the constant $1+\half c+{1\over3}c^2+\cdots\,$. This proves
\eq(|o-ln|), and the proof of \eq(|o-e|) is similar. Equations
\eq(|o-ln|) and~\eq(|o-e|) combine to give the useful formula
\begindisplay
\bigl(1+O(f(n))\bigr){}^{O(g(n))}&=1+O\bigl(f(n)@g(n)\bigr)\,,
\quad\tworestrictions{if $f(n)\prec1$ and}{$f(n)@g(n)=O(1)$.}\eqno\eqref|o-power|
\enddisplay

\subhead Problem 1: Return to the "Wheel of Fortune".

Let's try our luck now at a few asymptotic problems. In Chapter~3 we
derived equation \equ(3.|wheel-winners|) for the number of winning positions
in a certain game:
\begindisplay
W=\lfloor N/K\rfloor+\textstyle\half K^2+{5\over2}K-3\,,
\qquad\hbox{$K=\lfloor\root 3\of N\rfloor$}.
\enddisplay
And we promised that an asymptotic version of $W$ would be derived
in Chapter~9. Well, here we are in Chapter~9; let's try to estimate~$W$,
as $N\to\infty$.

The main idea here is to remove the floor brackets, replacing $K$
by $N^{1/3}+O(1)$. Then we can go further and write
\begindisplay
K=N^{1/3}\bigl(1+O(N^{-1/3})\bigr)\,;
\enddisplay
this is called ``"pulling out the large part".\qback'' (We will be using
this trick a lot.) Now we have
\begindisplay
K^2&=N^{2/3}\bigl(1+O(N^{-1/3})\bigr){}^2\cr
 &=N^{2/3}\bigl(1+O(N^{-1/3})\bigr)=N^{2/3}+O(N^{1/3})\cr
\enddisplay
by \eq(|o-power|) and \eq(|o-prod-in|). Similarly
\begindisplay
\lfloor N/K\rfloor&=N^{1-1/3}\bigl(1+O(N^{-1/3})\bigr){}^{-1}+O(1)\cr
 &=N^{2/3}\bigl(1+O(N^{-1/3})\bigr)+O(1)
  =N^{2/3}+O(N^{1/3})\,.
\enddisplay
It follows that the number of winning positions is
\begindisplay
W&=\textstyle N^{2/3}+O(N^{1/3})+\half\bigl(N^{2/3}+O(N^{1/3})\bigr)
 +O(N^{1/3})+O(1)\cr
&=\textstyle{3\over2}N^{2/3}+O(N^{1/3})\,.
\eqno
\enddisplay
Notice how the $O$ terms absorb one another until only one remains;
this is typical, and it illustrates why $O$-notation is useful
in the middle of a formula.

\subhead Problem 2: Perturbation of Stirling's formula.

"Stirling's approximation" for $n!$ is undoubtedly the most famous
asymptotic formula of all. We will prove it later in this chapter;
for now, let's just try to get better acquainted with its properties. We can
write one version of the approximation in the form
\begindisplay
n!&=\sqrt{2\pi n}\,\Bigl({n\over e}\Bigr)^{\!n}\biggl(1+{a\over n}
 +{b\over n^2}+O(n^{-3})\biggr)\,,\qquad\hbox{as $n\to\infty$},
 \eqno\eqref|o-factorial-mod|\cr
\enddisplay
for certain constants $a$ and $b$. Since this holds for all large~$n$,
it must also be asymptotically true when $n$ is replaced by~$n-1$:
\begindisplay \openup4pt
(n-1)!&=\sqrt{2\pi(n-1)}\,\Bigl({n-1\over e}\Bigr)^{\!n-1}\cr
&\qquad\times\biggl(1+{a\over n{-}1}
 +{b\over(n{-}1)^2}+O\bigl((n{-}1)^{-3}\bigr)\biggr)\,.
 \eqno\eqref|o-factorial-dim|\cr
\enddisplay
We know, of course, that $(n-1)!=n!/n$; hence the right-hand side of this
formula must simplify to the right-hand side of \eq(|o-factorial-mod|),
divided by~$n$.

Let us therefore try to simplify \eq(|o-factorial-dim|). The first factor becomes
tractable if we pull out the large part:
\begindisplay \openup3pt
\sqrt{2\pi(n-1)}&=\sqrt{2\pi n}\,(1-n^{-1})^{1/2}\cr
&=\sqrt{2\pi n}\,\Bigl(1-{1\over2n}-{1\over8n^2}+O(n^{-3})\Bigr)\,.
\enddisplay
Equation \eq(|o-binomial|) has been used here.

Similarly we have
\begindisplay \openup6pt
{a\over n-1}&={a\over n}(1-n^{-1})^{-1}={a\over n}+{a\over n^2}+O(n^{-3})\,;\cr
{b\over(n-1)^2}&={b\over n^2}(1-n^{-1})^{-2}={b\over n^2}+O(n^{-3})\,;\cr
O\bigl((n-1)^{-3}\bigr)&=O\bigl(n^{-3}(1-n^{-1})^{-3}\bigr)=O(n^{-3})\,.\cr
\enddisplay
The only thing in \eq(|o-factorial-dim|) that's slightly tricky to deal with
is the factor ${(n-1)^{n-1}}$, which equals
\begindisplay
n^{n-1}(1-n^{-1})^{n-1}=n^{n-1}(1-n^{-1})^n\bigl(1+n^{-1}+n^{-2}+O(n^{-3})\bigr)\,.
\enddisplay
(We are expanding everything out until we get a relative error of~$O(n^{-3})$,
because the relative error of a product is the sum of the relative errors
of the individual factors. All of the $O(n^{-3})$ terms will coalesce.)

In order to expand $(1-n^{-1})^n$, we first compute $\ln(1-n^{-1})$ and
then form the exponential, $e^{n\ln(1-n^{-1})}$:
\begindisplay \openup3pt
(1-n^{-1})^n&=\exp\bigl(n\ln(1-n^{-1})\bigr)\cr
&=\exp\bigl(n\bigl(\textstyle-n^{-1}-\half n^{-2}-{1\over3}n^{-3}
 +O(n^{-4})\bigr)\bigr)\cr
&=\exp\bigl(\textstyle-1-\half n^{-1}-{1\over3}n^{-2}+O(n^{-3})\bigr)\cr
&=\textstyle\exp(-1)\cdot\exp(-\half n^{-1})\cdot\exp(-{1\over3}n^{-2})
 \cdot\exp\bigl(O(n^{-3})\bigr)\cr
&=\textstyle\exp(-1)\cdot\bigl(1-\half n^{-1}+{1\over8}n^{-2}+O(n^{-3})\bigr)\cr
&\qquad\qquad\textstyle
 \cdot\bigl(1-{1\over3}n^{-2}+O(n^{-4})\bigr)\cdot\bigl(1+O(n^{-3})\bigr)\cr
&=e^{-1}\bigl(\textstyle1-\half n^{-1}-{5\over24}n^{-2}+O(n^{-3})\bigr)\,.
\enddisplay
Here we use the notation $\exp z$ instead of $e^z$, since it allows us to
work with a complicated exponent on the main line of the formula instead
of in the superscript position. We must expand $\ln(1-n^{-1})$
with absolute error $O(n^{-4})$ in order to end with a relative error
of $O(n^{-3})$, because the logarithm is being multiplied by~$n$.

The right-hand side of \eq(|o-factorial-dim|) has now been reduced to
$\sqrt{2\pi n}$ times $n^{n-1}\!/e^n$ times a product of several factors:
\begindisplay
&\textstyle\bigl(1-\half n^{-1}-{1\over8}n^{-2}+O(n^{-3})\bigr)\cr
&\qquad\cdot\textstyle\bigl(1+ n^{-1}+n^{-2}+O(n^{-3})\bigr)\cr
&\qquad\cdot\textstyle\bigl(1-\half n^{-1}-{5\over24}n^{-2}+O(n^{-3})\bigr)\cr
&\qquad\cdot\textstyle\bigl(1+a n^{-1}+(a+b)n^{-2}+O(n^{-3})\bigr)\,.\cr
\enddisplay
Multiplying these out and absorbing all asymptotic terms into one $O(n^{-3})$
yields
\begindisplay
\textstyle 1+an^{-1}+(a+b-{1\over12})n^{-2}+O(n^{-3})\,.
\enddisplay
Hmmm; we were hoping to get $1+an^{-1}+bn^{-2}+O(n^{-3})$, since that's what
we need to match the right-hand side of \eq(|o-factorial-mod|). Has
something gone awry? No, everything is fine, provided that
$a+b-{1\over12}=b$.

This perturbation argument doesn't prove the validity of Stirling's
approximation, but it does prove something: It proves that formula
\eq(|o-factorial-mod|) cannot be valid unless $a={1\over12}$. If we had
replaced the $O(n^{-3})$ in \eq(|o-factorial-mod|) by $cn^{-3}+O(n^{-4})$
and carried out our calculations to a relative error of~$O(n^{-4})$, we
could have deduced that $b$ must be
${1\over288}$, as claimed in Table~|o-special|.
(This is not the easiest way to determine the values of $a$ and~$b$,
but it works.)

\subhead Problem 3: The nth prime number.

Equation \eq(|o-pi|) is an asymptotic formula for $\pi(n)$, the number
of primes that do not exceed~$n$. If we replace $n$ by $p=P_n$, the
$n$th "prime" number, we have $\pi(p)=n$; hence
\begindisplay
n={p\over\ln p}+O\Bigl({p\over(\log p)^2}\Bigr)
\eqno\eqref|o-pi-trunc1|
\enddisplay
as $n\to\infty$. Let us try to ``solve'' this equation for~$p$;
then we will know the approximate size of the $n$th prime.

The first step is to simplify the $O$ term. If we divide both sides
by $p/\!@\ln p$, we find that $n\ln p/p\to1$; hence $p/\!@\ln p=O(n)$ and
\begindisplay
O\Bigl({p\over(\log p)^2}\Bigr)=
O\Bigl({n\over\log p}\Bigr)=
O\Bigl({n\over\log n}\Bigr)\,.
\enddisplay
(We have $(\log p)^{-1}\le(\log n)^{-1}$ because $p\ge n$.)

The second step is to transpose the two sides of \eq(|o-pi-trunc1|),
except for the $O$~term. This is legal because of the general rule
\begindisplay
a_n=b_n+O\bigl(f(n)\bigr)\iff
b_n=a_n+O\bigl(f(n)\bigr)\,.
\eqno\eqref|o-switch|
\enddisplay
(Each of these equations follows from the other if we multiply both sides
by~$-1$ and then add $a_n+b_n$ to both sides.) Hence
\begindisplay
{p\over\ln p}
=n+O\Bigl({n\over\log n}\Bigr)
=n\bigl(1+O(1/\!@\log n)\bigr)\,,
\enddisplay
and we have
\begindisplay
p=n\ln p\bigl(1+O(1/\!@\log n)\bigr)\,.
\eqno\eqref|pn-rec1|
\enddisplay
This is an ``approximate recurrence'' for $p=P_n$ in terms of itself.
"!recurrence, approximate or asymptotic"
Our goal is to change it into an ``approximate closed form,\qback'' and
we can do this by "unfolding the recurrence asymptotically".
So let's try to unfold \thiseq.

By taking logarithms of both sides we deduce that
\begindisplay
\ln p=\ln n+\ln\ln p+O(1/\!@\log n)\,.
\eqno\eqref|pn-rec1-ln|
\enddisplay
This value can be substituted for $\ln p$ in \eq(|pn-rec1|), but we
would like to get rid of all $p$'s on the right before making the substitution.
Somewhere along the line, that last~$p$ must disappear; we can't get rid of
it in the normal way for recurrences, because \eq(|pn-rec1|) doesn't
specify initial conditions for small~$p$.

One way to do the job is to start by proving the weaker result $p=O(n^2)$.
This follows if we square \eq(|pn-rec1|) and divide by $pn^2$,
\begindisplay
{p\over n^2}&={(\ln p)^2\over p}\bigl(1+O(1/\!@\log n)\bigr)\,,
\enddisplay
since the right side approaches zero as $n\to\infty$. OK, we know that
$p=O(n^2)$; therefore $\log p=O(\log n)$ and $\log\log p=O(\log\log n)$.
We can now conclude from \thiseq\ that
\begindisplay
\ln p=\ln n+O(\log\log n)\,;
\enddisplay
in fact, with this new estimate in hand we can conclude that
$\ln\ln p=\ln\ln n+O(\log\log n/\!@\log n)$, and \thiseq\ now yields
\begindisplay
\ln p=\ln n+\ln\ln n+O(\log\log n/\!@\log n)\,.
\enddisplay
And we can plug this into the right-hand side of \eq(|pn-rec1|),
obtaining
\begindisplay
p=n\ln n + n\ln\ln n+ O(n)\,.
\enddisplay
This is the approximate size of the $n$th prime.

We can refine this estimate
by using a better approximation of $\pi(n)$ in place of
\eq(|o-pi-trunc1|). The next term of \eq(|o-pi|) tells us that
\begindisplay
n={p\over\ln p}+{p\over(\ln p)^2}+O\Bigl({p\over(\log p)^3}\Bigr)\,;
\eqno\eqref|o-pi-trunc2|
\enddisplay
proceeding as before, we obtain the recurrence
\g Get out the scratch paper again, gang.\bigskip Boo, Hiss.\g
\begindisplay
p=n\ln p\,\bigl(1+(\ln p)^{-1}\bigr)^{-1}\bigl(1+O(1/\!@\log n)^2\bigr)\,,
\eqno\eqref|pn-rec2|
\enddisplay
which has a relative error of $O(1/\!@\log n)^2$ instead of $O(1/\!@\log n)$.
Taking logarithms and retaining proper accuracy (but not too much) now yields
\begindisplay \openup3pt
\ln p&=\ln n+\ln\ln p+O(1/\!@\log n)\cr
&=\ln n\Bigl(1+{\ln\ln p\over\ln n}+O(1/\!@\log n)^2\Bigr)\,;\cr
\ln\ln p&=\ln\ln n+{\ln\ln n\over\ln n}+O\Bigl({\log\log n\over\log n}\Bigr)^2\,.
\enddisplay
Finally we substitute these results into \eq(|pn-rec2|) and our answer finds
its way out:
\begindisplay
P_n=n@\ln n+n@\ln\ln n-n+n@
{\ln\ln n\over\ln n}+O\Bigl({n\over\log n}\Bigr)\,.
\eqno\eqref|pn-rel2|
\enddisplay
For example, when $n=10^6$ this estimate comes to $15631363.8+O(n/\!@\log n)$;
the millionth prime is actually $15485863$. Exercise~|pn-rel3| shows that
a still more accurate approximation to~$P_n$ results if we begin with a still more
accurate approximation to~$\pi(n)$ in place of~\eq(|o-pi-trunc2|).

\subhead Problem 4: A sum from an old final exam.

When Concrete Mathematics was first taught at Stanford University
during the 1970--1971 term, students were asked for the asymptotic value of
the sum
\begindisplay
S_n={1\over n^2+1}+
 {1\over n^2+2}+\cdots
 +{1\over n^2+n}\,,
\eqno
\enddisplay
with an absolute error of $O(n^{-7})$. Let's imagine that we've just been
given this problem on a (take-home) final; what is our first instinctive
reaction?

No, we don't panic.
 Our first reaction is to {\sc "think big"}. If we set $n=10^{100}$,
"!thinking big"
say, and look at the sum, we see that it consists of $n$~terms, each of
which is slightly less than $1/n^2$; hence the sum is slightly less than~$1/n$.
In general, we can usually get a decent start on an asymptotic problem
by taking stock of the situation and getting a ballpark estimate of the answer.

Let's try to improve the rough estimate by pulling out the largest part of
each term. We have
\begindisplay
{1\over n^2+k}={1\over n^2(1+k/n^2)}
 ={1\over n^2}\biggl(1-{k\over n^2}+{k^2\over n^4}-{k^3\over n^6}
  +O\Bigl({k^4\over n^8}\Bigr)\biggr)\,,
\enddisplay