TAOCP 1.2.11.2 Exercise 13
The statement is: g(n)=\Omega(f(n)) \quad \Longleftrightarrow \quad f(n)=O(g(n)).
Section 1.2.11.2: Euler's Summation Formula
Exercise 13. [M10] Prove or disprove: $g(n)=\Omega(f(n))$ if and only if $f(n)=O(g(n))$.
1.2.11.2. Euler's summation formula. One of the most useful ways to obtain good approximations to a sum is an approach due to Leonhard Euler. His method approximates a finite sum by an integral, and gives us a means to get better and better approximations in many cases.
Figure 12 shows a comparison of $\int_1^n f(x),dx$ and $\sum_{k=1}^{n-1} f(k)$, when $n=7$. Euler's strategy leads to a useful formula for the difference between these two quantities, assuming that $f(x)$ is a differentiable function.
For convenience we shall use the notation
$$ {x} = x \bmod 1 = x-\lfloor x \rfloor. \tag{1} $$
Our derivation starts with the following identity:
$$ \int_k^{k+1}\left({x}-\frac{1}{2}\right)f'(x),dx = \frac{1}{2}(f(k+1)+f(k)) - \int_k^{k+1} f(x),dx. \tag{2} $$
(This follows from integration by parts.) Adding both sides of this equation for $1 \le k < n$, we find that
$$ \sum_{1 \le k < n} f(k) = \int_1^n f(x),dx - \frac{1}{2}(f(n)-f(1))
- \int_1^n B_1({x})f'(x),dx, \tag{3} $$
where $B_1(x)$ is the polynomial $x-\frac{1}{2}$. This is the desired connection between the sum and the integral.
The approximation can be carried further if we continue to integrate by parts. Before doing this, however, we shall discuss the Bernoulli numbers, which are the coefficients in the following infinite series:
$$ \frac{z}{e^z-1} = B_0 + B_1z + \frac{B_2z^2}{2!} + \cdots = \sum_{k \ge 0} \frac{B_k z^k}{k!}. \tag{4} $$
We have
$$ B_0 = 1,\qquad B_1=-\frac{1}{2},\qquad B_2=\frac{1}{6},\qquad B_3=0,\qquad B_4=-\frac{1}{30}. \tag{5} $$
Since
$$ \frac{z}{e^z-1} + \frac{z}{2} = -\frac{ze^{-z}+1}{2(e^{-z}-1)} $$
is an even function, we see that
$$ B_3=B_5=B_7=B_9=\cdots=0. \tag{6} $$
If we multiply both sides of the defining equation (4) by $e^z-1$, and equate coefficients of equal powers of $z$, we obtain the formula
$$ \sum_k \binom{n}{k}B_k = B_n + \delta_{n1}. \tag{7} $$
We now define the Bernoulli polynomial
$$ B_m(x) = \sum_k \binom{m}{k} B_k x^{m-k}. \tag{8} $$
If $m=1$, then $B_1(x)=B_0x+B_1=x-\frac{1}{2}$, corresponding to the polynomial used above in Eq. (3). If $m>1$, we have $B_m(1)=B_m=B_m(0)$, by (7); in other words, $B_m({x})$ has no discontinuities at integer points $x$.
The relevance of Bernoulli polynomials and Bernoulli numbers to our problem will soon be clear. We find by differentiating Eq. (8) that
$$ B_m'(x) = mB_{m-1}(x), \tag{9} $$
and therefore when $m \ge 1$, we can integrate by parts as follows:
$$ \frac{1}{m!}\int_1^n B_m({x})f^{(m)}(x),dx = \frac{1}{(m+1)!}\Bigl(B_{m+1}(1)f^{(m)}(n)-B_{m+1}(0)f^{(m)}(1)\Bigr) $$
$$
- \frac{1}{(m+1)!}\int_1^n B_{m+1}({x})f^{(m+1)}(x),dx. $$
From this result we can continue to improve the approximation, Eq. (3), and we obtain Euler's general formula:
$$ \sum_{1 \le k < n} f(k) = \int_1^n f(x),dx
- \sum_{k=1}^{m} \frac{B_k}{k!}\Bigl(f^{(k-1)}(n)-f^{(k-1)}(1)\Bigr)
- R_{mn}, \tag{10} $$
using (6), where
$$ R_{mn} = \frac{(-1)^{m+1}}{m!}\int_1^n B_m({x})f^{(m)}(x),dx. \tag{11} $$
The remainder $R_{mn}$ will be small when $B_m({x})f^{(m)}(x)/m!$ is very small, and, in fact, one can show that
$$ \left|\frac{B_m({x})}{m!}\right| \le \frac{|B_m|}{m!} < \frac{4}{(2\pi)^m} \tag{12} $$
when $m$ is even.
It is known that, when $m$ is even, there is a number $\theta$ such that
$$ R_{mn} = \theta \frac{B_{m+2}}{(m+2)!} \Bigl(f^{(m+1)}(n)-f^{(m+1)}(1)\Bigr), \qquad 0<\theta<1, \tag{13} $$
provided that $f^{(m+2)}(x)f^{(m+4)}(x)>0$ for $1<x<n$.
Let us now apply Euler's formula to some important examples. First, we set $f(x)=1/x$. The derivatives are $f^{(m)}(x)=(-1)^m m!/x^{m+1}$, so we have, by Eq. (10),
$$ H_{n-1} = \ln n + \sum_{k=1}^{m} \frac{B_k}{k}(-1)^{k-1}\left(\frac{1}{n^k}-1\right) + R_{mn}. \tag{14} $$
Now we find
$$ \gamma = \lim_{n\to\infty}(H_{n-1}-\ln n) = \sum_{k=1}^{m}\frac{B_k}{k}(-1)^k + \lim_{n\to\infty}R_{mn}. \tag{15} $$
We can therefore put Eqs. (14) and (15) together, to deduce a general approximation for the harmonic numbers:
$$ H_{n-1} = \ln n + \gamma + \sum_{k=1}^{m}\frac{(-1)^{k-1}B_k}{kn^k}
- \int_n^\infty \frac{B_m({x})}{x^{m+1}},dx $$
$$ = \ln n + \gamma + \sum_{k=1}^{m-1}\frac{(-1)^{k-1}B_k}{kn^k}
- O!\left(\frac{1}{n^m}\right). $$
Replacing $m$ by $m+1$ yields
$$ H_{n-1} = \ln n + \gamma + \sum_{k=1}^{m}\frac{(-1)^{k-1}B_k}{kn^k}
- O!\left(\frac{1}{n^{m+1}}\right). \tag{16} $$
Furthermore, by Eq. (13) we see that the error is less than the first term discarded. As a particular case we have (adding $1/n$ to both sides)
$$ H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \epsilon, \qquad 0<\epsilon<\frac{B_6}{6n^6}=\frac{1}{252n^6}. $$
This is Eq. 1.2.7-(3).
The same technique can be applied to deduce Stirling's approximation. This time we set $f(x)=\ln x$, and Eq. (10) yields
$$ \ln(n-1)! = n\ln n - n + 1 - \frac{1}{2}\ln n
- \sum_{1<k\le m} \frac{B_k(-1)^k}{k(k-1)}\left(\frac{1}{n^{k-1}}-1\right)
- R_{mn}. \tag{17} $$
Proceeding as above, we find that the limit
$$ \lim_{n\to\infty}\left(\ln n! - n\ln n + n - \frac{1}{2}\ln n\right) $$
exists; let it be called $\sigma$ ("Stirling's constant") temporarily. We get Stirling's result
$$ \ln n! = \left(n+\frac{1}{2}\right)\ln n - n + \sigma
- \sum_{1<k\le m}\frac{B_k(-1)^k}{k(k-1)n^{k-1}}
- O!\left(\frac{1}{n^m}\right). \tag{18} $$
In particular, let $m=5$; we have
$$ \ln n! = \left(n+\frac{1}{2}\right)\ln n - n + \sigma
- \frac{1}{12n} - \frac{1}{360n^3} + O!\left(\frac{1}{n^5}\right). $$
Now we can take the exponential of both sides:
$$ n! = e^\sigma \sqrt{n}\left(\frac{n}{e}\right)^n \exp\left(\frac{1}{12n} - \frac{1}{360n^3} + O!\left(\frac{1}{n^5}\right)\right). $$
Using the fact that $e^\sigma=\sqrt{2\pi}$ (see exercise 5), and expanding the exponential, we get our final result:
$$ n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left( 1+\frac{1}{12n}+\frac{1}{288n^2}-\frac{139}{51840n^3}-\frac{571}{2488320n^4}
- O!\left(\frac{1}{n^5}\right) \right). \tag{19} $$
Exercises
Verified: yes
Solve time: 1m31s
The statement is:
$$ g(n)=\Omega(f(n)) \quad \Longleftrightarrow \quad f(n)=O(g(n)). $$
We prove both directions from the definitions.
Definitions
By definition (using absolute values):
- $f(n)=O(g(n))$ means there exist constants $C>0$ and $n_0$ such that
$$ |f(n)| \le C|g(n)| \quad \text{for all } n \ge n_0. $$
- $g(n)=\Omega(f(n))$ means there exist constants $c>0$ and $n_1$ such that
$$ |g(n)| \ge c|f(n)| \quad \text{for all } n \ge n_1. $$
First direction: $g(n)=\Omega(f(n)) \Rightarrow f(n)=O(g(n))$
Assume $g(n)=\Omega(f(n))$. Then there exist constants $c>0$ and $n_1$ such that for all $n \ge n_1$,
$$ |g(n)| \ge c|f(n)|. $$
Since $c>0$, divide both sides by $c$:
$$ \frac{1}{c}|g(n)| \ge |f(n)|. $$
Rewriting,
$$ |f(n)| \le \frac{1}{c}|g(n)| \quad \text{for all } n \ge n_1. $$
Thus $f(n)=O(g(n))$ with constant $C=\frac{1}{c}$.
Second direction: $f(n)=O(g(n)) \Rightarrow g(n)=\Omega(f(n))$
Assume $f(n)=O(g(n))$. Then there exist constants $C>0$ and $n_0$ such that for all $n \ge n_0$,
$$ |f(n)| \le C|g(n)|. $$
If $C>0$, divide both sides by $C$:
$$ \frac{1}{C}|f(n)| \le |g(n)|. $$
Rewriting,
$$ |g(n)| \ge \frac{1}{C}|f(n)| \quad \text{for all } n \ge n_0. $$
Thus $g(n)=\Omega(f(n))$ with constant $c=\frac{1}{C}$.
Edge cases
If $g(n)=0$ for all sufficiently large $n$, then $f(n)=O(g(n))$ forces $f(n)=0$ for all sufficiently large $n$. In this case both $f(n)=O(g(n))$ and $g(n)=\Omega(f(n))$ hold trivially, so the equivalence remains valid.
Conclusion
Each condition is exactly the algebraic rearrangement of the other under the same “eventually bounded by a constant multiple” definition. Therefore,
$$ g(n)=\Omega(f(n)) \iff f(n)=O(g(n)). $$
$$ \boxed{\text{True}} $$