Chapter 4

Exercise 1

$$\frac{N}{N+1}<1 \text{ for all }N\ge 0 \implies \frac{N}{N+1}=O(1).$$

Expanding $2^N$ and $N!$ gives

$$\lim_{N \to \infty} \frac{2^N}{N!}=\lim_{N \to \infty} \frac{2\times2\times\cdots\times2}{1\times2\times\cdots \times N}=0,$$

thus $2^N=o(N!)$.

Clearly, $\lim_{N \to \infty} e^{1/N}=e^0=1$, so $\sqrt[N]{e} \sim 1$.

Exercise 2 🌟

This example demonstrates that $g(N)=O(f(N))$ can encompass functions that are asymptotically negative. Certain references, like CLRS's Introduction to Algorithms, restrict $g(N)$ to nonnegative functions and employ a specific notation, O', to remove this limitation within O-notation.

We start by factoring $N/(N+1)=1+(-1/(N+1))$. Let’s show that the second summand is $O(1/N)$

$$\left|\frac{-1/(N+1)}{1/N}\right|=\frac{N}{N+1}<1 \text{ for all }N\ge 0,$$

therefore, $N/(N+1)=1+O(1/N)$. We also have

$$\lim_{N \to \infty} \frac{N/(N+1)}{1-1/N}=1,$$

hence, $N/(N+1) \sim1-1/N$.

Exercise 3

$$\lim_{N \to \infty} \frac{N^\alpha}{N^\beta}=\lim_{N \to \infty} \frac{1}{N^{\beta-\alpha}}=0, \qquad \text{when }\alpha<\beta.$$

Therefore, $N^\alpha=o(N^\beta)$ for $\alpha<\beta$.

Exercise 4

The O- and o-notations provide ways to express upper bounds (with o being the stronger assertion). Consequently, $g(N)=o(f(N)) \implies g(N)=O(f(N))$. By combining the results from the previous two exercises, for $r\ge0$ fixed, we can conclude that (see also section 4.3 of the book)

$$1±k/N =1+O(1/N) \text{ for } 0 \le k \le r ,\qquad (1+O(1/N))^r=1+O(1/N).$$

This gives

$$\begin{align*} \binom{N}{r} &= \frac{N(N-1)\cdots(N-r+1)}{r!} \\ &= \frac{N^r}{r!}\prod_{k=0}^{r-1}\Big(1-\frac{k}{N}\Big) \\ &= \frac{N^r}{r!}\Big(1+O\!\Big(\frac{1}{N}\Big)\Big) \\ &\therefore \boxed{\binom{N}{r} = \frac{N^r}{r!}+O(N^{r-1})}. \end{align*}$$

Similarly, we have

$$\begin{align*} \binom{N+r}{r} &= \frac{(N+r)(N+r-1)\cdots(N+1)}{r!} \\ &= \frac{N^r}{r!}\prod_{k=1}^{r}\Big(1+\frac{k}{N}\Big) \\ &= \frac{N^r}{r!}\Big(1+O\!\Big(\frac{1}{N}\Big)\Big) \\ &\therefore \boxed{\binom{N+r}{r} = \frac{N^r}{r!}+O(N^{r-1})}. \end{align*}$$

Alternative Proof

Instead of relying on basic algebraic manipulations involving the O-notation, we can represent the numerator of $\binom{N}{r}$ as a polynomial $P(N)=N(N-1)\cdots(N-r+1)$. Since there are $r$ terms in this product, multiplying the $N$ from each term gives us a leading term of $N^r$. To find the next term (the coefficient of $N^{r-1}$), we sum the constant terms from each factor

$$\text{Sum of constants} = -(0 + 1 + 2 + \dots + (r-1)) = -\frac{(r-1)r}{2}.$$

Thus, the numerator expands to

$$P(N) = N^r - \frac{r(r-1)}{2}N^{r-1} + \dots (\text{lower order terms}).$$

Dividing by $r!$ gives

$$\binom{N}{r} = \frac{N^r}{r!} - \frac{r(r-1)}{2 \cdot r!}N^{r-1} + \dots$$

The first term is our leading term. All subsequent terms form a polynomial of degree $r-1$. Therefore, their sum is $O(N^{r-1})$ (see also the previous exercise). An analogous reasoning applies for the case $\binom{N+r}{r}$.

Exercise 5

$$\begin{align*} \lim_{N \to \infty} \frac{\log N}{N^\epsilon} &\overset{L'Hôpital}{=} \lim_{N \to \infty} \frac{1/N}{\epsilon N^{\epsilon - 1}} \\ &= \lim_{N \to \infty} \frac{1}{\epsilon N^\epsilon} = 0 \\ &\therefore \boxed{\log N = o(N^\epsilon)}. \end{align*}$$

Exercise 6

$$\begin{align*} &\lim_{N \to \infty} \frac{1}{2+\ln N} = 0 \\ &\therefore \boxed{\frac{1}{2+\ln N} = o(1)}. \end{align*}$$

The cosine function oscillates between -1 and 1, thus as $N \to \infty$ we have $1/(2+\cos N) \in[1/3,1]$. Clearly, it’s bounded from above, but doesn’t tend to 0. Therefore, it is $O(1)$ but not $o(1)$.

Exercise 7

The definition from the book "...we often refer informally to a quantity as being exponentially small if it is smaller than any negative power of N—that is, $O(1/N^M)$ for any positive M." is imprecise. Namely, the word "smaller" pertains to an asymptotic property of a decay, so instead of O- it should use o-notation.

$$\begin{align*} \lim_{N \to \infty} \frac{e^{-N^\epsilon}}{N^{-M}} &= \lim_{N \to \infty} \frac{N^M}{e^{N^\epsilon}} \\ &= \lim_{N \to \infty} \frac{e^{\ln N^M}}{e^{N^\epsilon}} \\ &= \lim_{N \to \infty} \frac{e^{M\ln N}}{e^{N^\epsilon}} = 0. \end{align*}$$

The last line follows from Exercise 5, thus $e^{-N^\epsilon}$ is exponentially small.

Exercise 8

$$\begin{align*} \lim_{N \to \infty} \frac{e^{-\log^2 N}}{N^{-M}} &= \lim_{N \to \infty} \frac{N^M}{e^{\log^2 N}} \\ &= \lim_{N \to \infty} \frac{e^{\ln N^M}}{e^{\log^2 N}} \\ &= \lim_{N \to \infty} \frac{e^{M\ln N}}{e^{\log^2 N}} = 0. \end{align*}$$

In the last line $M\ln N = o(\log^2 N)$, since after cancelling one logarithm on both sides, we are left with a constant term "against" a logarithm that grows to infinity. Observe that we don’t care about the base of a logarithm on the RHS, as it’s just a constant multiple of a natural logarithm. Therefore, $e^{-\log^2 N}$ is exponentially small.

$$\begin{align*} \lim_{N \to \infty} \frac{(\log N)^{-\log N}}{N^{-M}} &= \lim_{N \to \infty} \frac{N^M}{(\log N)^{\log N}} \\ &= \lim_{N \to \infty} \frac{e^{\ln N^M}}{e^{\ln {(\log N)^{\log N}}}} \\ &= \lim_{N \to \infty} \frac{e^{M\ln N}}{e^{\log N (\ln {\log N})}} = 0. \end{align*}$$

By employing the same reasoning as above, we see that now $\ln \log n$ grows faster than any constant. Therefore, $(\log N)^{-\log N}$ is also exponentially small.

Exercise 9 🌟

This exercise shows why focusing on an asymptotically most significant term is beneficial. As the calculation shows, it’s a reliable estimator of the performance for sufficiently large problem sizes.

$$\begin{align*} \lim_{N \to \infty} \frac{(\alpha/\beta)^N}{N^{-M}} &= \lim_{N \to \infty} \frac{N^M}{(\beta/\alpha)^N} \\ &= \lim_{N \to \infty} \frac{e^{\ln N^M}}{e^{\ln {(\beta/\alpha)^N}}} \\ &= \lim_{N \to \infty} \frac{e^{M\ln N}}{e^{N\ln {(\beta/\alpha)}}} = 0, \end{align*}$$

so $\alpha^N$ is exponentially small relative to $\beta^N$ (see Exercise 5).

The absolute error is $\alpha^N$, whilst the relative error is $\alpha^N/(\alpha^N+\beta^N)$. We have

• For $N=10$ the absolute error is ≈2.6 and the relative error is ≈29.53%.

• For $N=100$ the absolute error is ≈13,781 and the relative error is ≈0.02%.

Exercise 10

See the remark for Exercise 7.

Let $f(N)$ be exponentially small, meaning for every $M > 0$, $f(N) = o(N^{-M})$. For any polynomial$g(N)=O(N^d)$, where $d \ge 0$ is the degree of the polynomial, we can choose $M'=M+d$, such that $f(N)g(N)=o(N^{-M'})O(N^d)=o(N^{-M})$. This concludes the proof.

Exercise 11 🌟

Chapter 2 of the book explains the Master Theorem with a note that floors/ceilings can be ignored without breaking the asymptotic result. The term $a_{\lfloor n/2 \rfloor}+O(1)$ implies that every time we recurse, we introduce a small constant error $O(1)$ due to potential rounding errors. This gives

$$\begin{align*} a_n &= 2a_{n/2} + f(n) \\ &= 2(a_{\lfloor n/2 \rfloor} + O(1)) + f(n) \\ &= 2a_{\lfloor n/2 \rfloor} + \underbrace{O(1)}_{\text{error}} + f(n). \end{align*}$$

In a binary recursion tree, where every internal node has 2 children, the number of nodes doubles at every level. The sum of this error across the whole tree is proportional to the number of nodes in the tree

$$\text{Total Error} = \sum_{k=0}^{\lg n} 2^k \cdot O(1) = O(n).$$

Consequently, $a_n=(\text{Ideal Solution}) + O(n)$, where ideal solution denotes the case when $n$ is a power of two. We’ll derive these ideal solutions and see that the extra $O(n)$ error has no significance on them.

1. $a_n = 2a_{n/2} + O(n)$ essentially falls under case 2 of the Master Theorem. We have $\lg n$ levels in the recursion tree taking $O(n)$ work per level. Therefore, $\boxed{a_n=O(n\log n)}$. We cannot use $\Theta$-notation because the term $O(n)$ allows for the driving function to be 0 or even negative (see the next exercise).

2. $a_n = 2a_{n/2} + o(n)$ can also be handled using the summation approach. We have $\lg n$ levels in the recursion tree taking $o(n)$ work per level. Therefore, $\boxed{a_n=o(n\log n)}$.

3. $a_n \sim 2a_{n/2} + n$ means that $a_n = 2a_{n/2} + n + o(n)$. Dividing by $n$ and letting $b_n = a_n/n$ yields $b_n = b_{n/2} + 1 + o(1)$. Iterating this recurrence gives $b_n = b_0 + \lg n + o(\lg n)$, so $a_n = n \lg n + o(n \lg n)$. Therefore, $\boxed{a_n \sim n \lg n}$.

Handling the base cases demands $\Theta(n)$ time, so for cases 1 and 2 we also have a lower bound $a_n=\Omega(n)$.

Exercise 12

This is a continuation of the previous exercise, where the first case is already covered:

• $a_n = 2a_{n/2} + \Theta(n)$ entails that $\boxed{a_n=\Theta(n\log n)}$.

• $a_n = 2a_{n/2} + \Omega(n)$ entails that $\boxed{a_n=\Omega(n\log n)}$.

Exercise 13

Both $a(x)$ and $b(x)$ grow like $x^\alpha$, and the additive perturbation $c$ in the argument of $b(x)$ becomes asymptotically negligible. To see this, we just need to iterate the recurrences until hitting the base cases.

For $a(x)$ the recursion unfolds as

$$a(x) = f(x) + f(x/\beta) + f(x/\beta^2) + \cdots + f(x/\beta^k),$$

where $x/\beta^k < 1$ eventually, so the sum terminates. Since $f(x) = x^\alpha$, each term is $(x/\beta^i)^\alpha$, and the sum behaves like a convergent infinite geometric series as $x \to \infty$

$$a(x) = x^\alpha \sum_{i=0}^{\log_\beta x} \beta^{-\alpha i} \sim \frac{\beta^\alpha}{\beta^\alpha-1}x^\alpha.$$

For $b(x)$ the recurrence is slightly perturbed

$$b(x) = f(x) + f(x/\beta + c) + f(x/\beta^2 + c(1 + 1/\beta)) + \cdots$$

But asymptotically $x/\beta^i + O(1) \sim x/\beta^i$, so each term in the sum is still $\sim (x/\beta^i)^\alpha$, and the same geometric series argument applies.

A generalization of this exercise is part of the Akra-Bazzi method, which should be included in the toolbox of techniques for finding asymptotic approximations of recurrences.

Exercise 14 🌟

According to Exercise 3.17

$$\frac{f(z)}{g(z)} = \frac{1}{1 – 2z}.$$

Thus, $\beta=2$, $\nu=1$, $g'(1/2)=-2$ and $f(1/2)=1$, so the approximate solution is $a_n \sim 2^n$ as before.

The text of the exercise repeats the initial conditions, so we assume that it refers to the example given in section 3.3 of the book with $a_0=0$ and $a_1=1$.

$$\frac{f(z)}{g(z)}=\frac{z}{(1-2z)^2}.$$

Thus, $\beta=2$, $\nu=2$, $g''(1/2)=8$ and $f(1/2)=1/2$, so the approximate solution is $a_n \sim n2^{n-1}$ as before.

Exercise 15 🌟

According to Exercise 3.18

$$\frac{f(z)}{g(z)}=\frac{z^2}{(1-z)^2(1+z)}.$$

We have two poles of same modulus, so we must take the one of highest multiplicity. Thus, $\beta=1$, $\nu=2$, $g''(1)=4$ and $f(1)=1$, so the approximate solution is $a_n \sim n/2$ as expected.

Exercise 16 🌟

According to Exercise 3.20

$$\frac{f(z)}{g(z)}= \frac{z^2}{(1-z)^3}.$$

Thus, $\beta=1$, $\nu=3$, $g^{(3)}(1)=-6$ and $f(1)=1$, so the approximate solution is $a_n \sim n^2/2$ as expected.

Exercise 17

According to the fundamental theorem of algebra a degree $t$ polynomial has exactly $t$ roots, counted with multiplicity.

Showing that the Roots are Distinct

We can rewrite $P(z)=z^t – z^{t–1} – \dots – z – 1$ as

$$P(z) = z^t - \sum_{k=0}^{t-1} z^k = z^t - \frac{z^t - 1}{z - 1} = \frac{z^{t+1} - 2z^t + 1}{z - 1}=\frac{Q(z)}{z-1}.$$

Observe that $P(1) =1-t\neq 0$ for $t>1$, thus $z=1$ isn’t a root. Consequently, the roots of $P(z)$ are exactly the roots of $Q(z)$, excluding $z=1$. A polynomial $Q(z)$ has multiple roots only if $Q(z)$ and its derivative $Q'(z)$ share a root.

$$Q'(z) = (t+1)z^t - 2tz^{t-1} = z^{t-1} [ (t+1)z - 2t ].$$

The unique roots of the derivative are $z=0$ and $z = \frac{2t}{t+1}$. Apparently $Q(0)=1$, so $z=0$ isn’t shared. For the other candidate, we have

$$\begin{align*} Q\left(\frac{2t}{t+1}\right) &= \left(\frac{2t}{t+1}\right)^{t+1} - 2\left(\frac{2t}{t+1}\right)^t + 1 \\ &= \left(\frac{2t}{t+1}\right)^t \left[ \frac{2t}{t+1} - 2 \right] + 1 \\ &= 1 - \left(\frac{2t}{t+1}\right)^t \frac{2}{t+1}. \end{align*}$$

We would need $\left(\frac{2t}{t+1}\right)^t \frac{2}{t+1} = 1$. But for all $t>1$, $\frac{2t}{t+1} > 1$, so the power term grows exponentially. Therefore, all roots of $P(z)$ are distinct.

Showing that Exactly One Root has Modulus > 1

Because the coefficients of $P(z)$ are real, the singleton dominant root must be a real number. We can verify that $P(1) = 1-t < 0$ and $P(2) = 1 > 0$, hence by the intermediate value theorem, there is a real root in $(1,2)$.

By using Rouché's theorem on the unit disk, we show that the remaining $t-1$ roots of $P(z)$ lie inside the unit circle $|z| \le 1$; this theorem relates the number of zeros of two functions, $f(z)$ and $f(z)+g(z)$, inside a region. Let’s rearrange the terms of $Q(z)$

$$\underbrace{ - 2z^t }_{f(z)} +\underbrace{z^{t+1}+ 1}_{g(z)}.$$

We focus our attention on a circle of radius $|z| = 1 + \epsilon$ (where $\epsilon$ is a very small positive number). The magnitudes of our functions on the contour line are:

• $|f(z)| = |-2z^t| = 2(1+\epsilon)^t \approx 2 + 2t\epsilon$

• $|g(z)| \le |z|^{t+1} + 1 = (1+\epsilon)^{t+1} + 1 \approx 1 + (1 + (t+1)\epsilon) = 2 + (t+1)\epsilon$

Since $t > 1$, we have $2t > t+1$, thus $|f(z)| > |g(z)|$. By Rouché's theorem, the polynomial $Q(z) = f(z) + g(z)$ has the same number of roots inside the circle $|z| = 1+\epsilon$ as $f(z)$.

$f(z)$ has a root of multiplicity $t$ at the origin ($z=0$). Therefore, $Q(z)$ has exactly $t$ roots strictly inside the circle $|z| < 1+\epsilon$. Consequently, $P(z)$ has exactly $t-1$ roots inside the same disk; recall that we must exclude $z=1$, which was counted for $Q(z)$.

Exercise 18

We need to apply the result from the previous exercise. Since the recurrence formula reflects $P(z)=z^t – z^{t–1} – \dots – z – 1$, we know there is a single root $\beta$ (approaches 2 as $t \to \infty$) of highest modulus. According to Theorem 4.1, $F_N^{[t]} \sim C\beta^N$. Wikipedia describes this variant as $n$-acci sequence and provides a precise expression for the leading term.

Exercise 19

According to Exercise 3.55

$$\frac{f(z)}{g(z)}= \frac{1}{(1-z^{d_1})(1-z^{d_2})\times \dots \times (1-z^{d_t})}.$$

Thus, $\beta=1$, $\nu=t$ and $f(1)=1$. We need to compute $g^{(t)}(1)$.

Each factor can be written as

$$1 - z^{d_i} = (1 - z)h_i(z), \qquad h_i(z)=z^{d_i-1}+z^{d_i-2}+\dots+1.$$

Apparently, $h_i(1)=d_i$ and $g(z)=(1-z)^th(z)$, where $h(z)=\prod_{i=1}^th_i(z)$. Consequently, $h(1)=\prod_{i=1}^td_i$. By the general Leibniz rule we have

$$g^{(t)}(z) = \sum_{k=0}^{t} \binom{t}{k} \frac{d^k}{dz^k}(1-z)^t \cdot h^{(t-k)}(z).$$

At $z = 1$ all terms with $k<t$ vanish because $\frac{d^k}{dz^k}(1-z)^t$ still contains a factor of $1-z$. For $k=t$ we have $\frac{d^t}{dz^t}(1-z)^t = (-1)^tt!$. Thus,

$$g^{(t)}(1) = \binom{t}{t}(-1)^t \,t! \, h(1) = (-1)^t\,t! \prod_{i=1}^{t} d_i.$$

By inserting all components into the formula from Theorem 4.1, we get the required identity of this exercise.

Exercise 20

The Python script below generates the extended table. It uses pandas to produce formatted output.

import numpy as np
import pandas as pd
from scipy.special import digamma

gamma = 0.5772156649015328606

def harmonic(n):
    return digamma(n + 1) + gamma

def estimate_1(n):
    return 2 * (n + 1) * (harmonic(n + 1) - 1)

def estimate_2(n):
    return 2 * n * np.log(n)

def estimate_3(n):
    return (2 * gamma - 2) * n

def estimate_4(n):
    return 2 * (np.log(n) + gamma) + 1

Ns = [10, 100, 1_000, 10_000, 100_000, 1_000_000]

rows = []
for n in Ns:
    e1 = estimate_1(n)
    e2 = estimate_2(n)
    e3 = e2 + estimate_3(n)
    e4 = e3 + estimate_4(n)
    rows.append([n, e1, e2, e3, e4])

df = pd.DataFrame(rows, columns=[
    "N",
    "2(N+1)(H_{N+1} - 1)",
    "2N ln N",
    "+(2γ - 2)N",
    "+2(ln N + γ) + 1"
])
pd.set_option("display.float_format", "{:,.2f}".format)
print(df)

The code outputs the following table:

         N  2(N+1)(H_{N+1} - 1)       2N ln N    +(2γ - 2)N  +2(ln N + γ) + 1
0       10                44.44         46.05         37.60             44.36
1      100               847.85        921.03        836.48            847.84
2     1000            12,985.91     13,815.51     12,969.94         12,985.91
3    10000           175,771.70    184,206.81    175,751.12        175,771.70
4   100000         2,218,053.41  2,302,585.09  2,218,028.23      2,218,053.41
5  1000000        26,785,482.23 27,631,021.12 26,785,452.45     26,785,482.23

Exercise 21 🌟

Tool support is useful here. For example, we can type in WolframAlpha the following command

series ln(1-x+x^2) to order 3

It produces the requested expansion

$$-x + \dfrac{1}{2}x^{2} + \dfrac{2}{3}x^{3} + O(x^{4}).$$

Exercise 22

$$\begin{align*} \ln(N^\alpha+N^\beta) &= \ln N^\alpha + \ln \left(1+\underbrace{\frac{1}{N^{\alpha-\beta}}}_{x \to 0}\right) \\ &= \alpha\ln N + \frac{1}{N^{\alpha-\beta}}-\frac{1}{2N^{2(\alpha-\beta)}}+\frac{1}{3N^{3(\alpha-\beta)}}+O\left(\frac{1}{N^{4(\alpha-\beta)}}\right). \end{align*}$$

Exercise 23 🌟

Let’s start with a Taylor expansion of the expression in terms of $x=1/(N-1)$

$$\begin{align*} \frac{N}{N-1}\ln \frac{N}{N-1} &= \left(1+\underbrace{\frac{1}{N-1}}_{x}\right)\,\ln \left(1+\frac{1}{N-1}\right) \\ &= \frac{1}{N-1}+\frac{1}{2(N-1)^2}-\frac{1}{6(N-1)^3}+O\left(\frac{1}{(N-1)^4}\right) \qquad (1+x)(x-x^2/2+x^3/3+O(x^4))=x+x^2/2-x^3/6+O(x^4). \end{align*}$$

A more streamlined version would be stated in terms of $1/N$, since $N-1 \sim N$. By taking $x=1/N$ in the geometric series, we get $1/(N-1)=1/N+1/N^2+1/N^3+O(N^{-4})$. We need to replace the factors involving $1/(N-1)$ in the above series with the given expansion of $1/(N-1)$. This gives

$$\boxed{\frac{N}{N-1}\ln \frac{N}{N-1} = \frac{1}{N}+\frac{3}{2N^2}+\frac{11}{6N^3}+O\left(\frac{1}{N^4}\right)}.$$

Exercise 24

Let $x=0.1$, so $\ln 0.9=\ln (1-0.1)$. By using Table 4.2 and expanding each function to within $O(x^5)$, we get

$$2+2x+x^2/2+x^3/2+x^4/3+O(x^5).$$

We should be careful when summing up the terms of a logarithm, due to subtraction and negative value of $x$. After substituting $x$ into the above expression, we find that the result is 2.20553, which is to within $10^{-4}$.

Exercise 25

Observe that $9801=99^2=(100-1)^2$, so

$$\frac{1}{9801}=\frac{1}{(100-1)^2}=\frac{1}{10^4(1-0.01)^2}.$$

Table 4.2 has an expansion of the geometric series. By differentiating both sides of that identity, we get

$$\frac{1}{(1-x)^2} = \sum_{k=1}^{\infty} k x^{k-1}.$$

Now, we substitute $x$ into our derived series

$$\begin{align*} \frac{1}{9801} &= \frac{1}{10^4} \times \left[ 1 + 2(0.01) + 3(0.01)^2 + 4(0.01)^3 + \dots \right] \\ &= 0.00|01|02|03|04í\dots|47|48|49|50|\dots \end{align*}$$

Vertical bars are used to delineate slots, each of which is populated with successive natural numbers. Each slot accommodates two digits, enabling this sequence to progress up to the number 97. In other words, we can predict digits in this manner within $100^{-196}$. The pattern breaks at the slot with 98, as illustrated below:

Slot:   [97] [98] [99] [00] [01]
k = 97:  97
k = 98:       98
k = 99:            99
k = 100:           01   00   
k = 101:                01   01
--------------------------------
Result:  97   99   00   01   02 ...

The carry from the 100th term impacts the slots containing 98 and 99.

We can generalize this to generate sequences of integers padded to $n$ digits

$$\frac{1}{(10^n - 1)^2}=\frac{1}{10^{2n}(1 - 10^{-n})^2}.$$

For example, $1/81=0.012345679\dots$ (8 is missing due to the carry-over from 9).

Exercise 26

If we apply the nonasymptotic version of Stirling’s formula to describe $\binom{2N}{N}$, we get

$$\binom{2N}{N} =\frac{(2N)!}{(N!)^2} =\frac{4^N}{\sqrt{\pi N}}\;\frac{1+\dfrac{\theta_{2N}}{24N}}{\bigg(1+\dfrac{\theta_N}{12N}\bigg)^2}.$$

Our equation becomes

$$\underbrace{\frac{N4^{N-1}}{\binom{2N}{N}}}_{R_N} =\underbrace{\frac{N\sqrt{\pi N}}{4}}_{A_N}\;\underbrace{\frac{\bigg(1+\dfrac{\theta_N}{12N}\bigg)^2}{1+\dfrac{\theta_{2N}}{24N}}}_{E_N},$$

where $R_N,A_N,E_N$ represent the reference, approximate and error terms, respectively.

Since $0<\theta_N<1$ and $0<\theta_{2N}<1$, we have the following bounds

$$1 < \big(1+\tfrac{\theta_N}{12N}\big)^2 < \Big(1+\tfrac{1}{12N}\Big)^2, \qquad 1 < 1+\tfrac{\theta_{2N}}{24N} < 1+\tfrac{1}{24N}.$$

This gives

$$A_N\cdot\frac{1}{1+\dfrac{1}{24N}} <R_N < A_N\cdot\Bigg(1+\dfrac{1}{12N}\Bigg)^2.$$

Let the relative error $\delta_N$ be defined such that $R_N = A_N(1 + \delta_N)$. This gives

$$\begin{align*} \frac{1}{1 + \frac{1}{24N}} &< 1 + \delta_N < \left(1 + \frac{1}{12N}\right)^2 \\ \frac{1}{1 + \frac{1}{24N}} - 1 &< \delta_N < \left(1 + \frac{1}{12N}\right)^2 - 1 \\ -\frac{1}{24N+1} &< \delta_N < \frac{1}{6N} + \frac{1}{144N^2}. \end{align*}$$

We can assert that $\delta_N=O(1/N)$.

Exercise 27

According to Table 4.4, $H_{1000}=7.4854709$.

The specific bounds implied by the absolute formula are

$$7.4749709 \le \hat H_{1000} \le 7.4949709$$

The specific bounds implied by the relative formula are

$$0 \le \hat H_{1000} \le 16.9077553$$

The LHS is truncated to zero as a negative lower bound is meaningless. The RHS is huge, since the assumed constant is too large. In a relative formula, we expect $h(N)=o(1)$ that should decay rapidly even for small problem sizes.

Recall that $O(h(N))$ with a constant $|C|<10$ covers the range $±Ch(N)$.

Exercise 28

The exact value is $T_{10}=16,796$.

The specific bounds implied by the relative formula are

$$0 \le \hat T_{10} \le 37,416.$$

Exercise 29

Let’s split the original recurrence at the threshold value $M>0$

$$f(N)=\sum_{k\ge 0} a_k N^{-k} =\sum_{0\le k< M} a_k N^{-k}+\underbrace{\sum_{k\ge M} a_k N^{-k}}_{R_M(N)}.$$

Since $f(N)$ converges then $R_M(N)$ converges, too. We can rearrange the remainder term as

$$R_M(N) = \sum_{j\ge 0} a_{M+j}N^{-(M+j)} = N^{-M}\underbrace{\sum_{j\ge 0} a_{M+j}N^{-j}}_{C}= C\cdot N^{-M}.$$

Hence, $R_M(N)=O(N^{-M})$, which concludes the proof.

Exercise 30

It’s not hard to see from Table 3.3 that terms of the sum can be represented with an EGF

$$A(z)=\frac{1}{1-\cfrac{z}{N}}=\frac{N}{N-z}=\sum_{k\ge0} \frac{k!}{N^k} \frac{z^k}{k!} = \sum_{k\ge0}\left(\frac{z}{N}\right)^k.$$

This gives

$$\begin{align*} S(N) &=\sum_{k\ge0} \frac{k!}{N^k} \\ &= \sum_{k\ge0} \frac{1}{N^k} \underbrace{\int_0^\infty e^{-z} z^k \, dz}_{k!=\Gamma(k+1)} \\ &= \int_0^\infty e^{-z} \sum_{k\ge0} \left(\frac{z}{N}\right)^k \, dz \\ &= \int_0^\infty e^{-z}\frac{N}{N - z} \, dz \\ &= N e^{-N} \operatorname{Ei}(N). \end{align*}$$

The derivation uses the gamma function and exponential integral to craft the "closed-form" solution. The last line follows after employing the substitution $u=z-N$.

Of course, we can make $f(N)=S(N)$ or construct a function that can be approximated by using few terms of $S(N)$. Let’s use expansion of the geometric series from Table 4.2 with $x=1/N$. This gives

$$g(x)=\frac{1}{1-x}+\frac{x^2}{1-x}+\frac{4x^3}{1-x}=1+x+2x^2+6x^3+O(x^4), \qquad f(N)=g(1/N).$$

Exercise 31

There is a complementary $\omega$-notation that reflects the opposite relationship compared to the o-notation. It denotes a strict lower bound (grows strictly faster than). We use it in our list below:

• $e^N=O(N^2)$ is false, since $\lim_{N \to \infty}\frac{e^N}{N^2}=\infty$. We can say that $e^N=\omega(N^2)$.

• $e^N=O(2^N)$ is false (see Exercise 9). We can say that $e^N=\omega(2^N)$.

• $2^{-N}$ is exponentially small, so $2^{-N}=O(1/N^{10})$ is true (see Exercise 7).

• $N^{\ln N}=O(e^{\ln^2 N})$ is true, since $N^{\ln N}=e^{\ln {N^{\ln N}}}=e^{\ln^2 N}$.

Exercise 32

The Taylor expansion of $e^x$ in terms of $x=1/(N+1)$ is (see Table 4.2)

$$e^{\frac{1}{N+1}}=1+\frac{1}{N+1}+\frac{1}{2(N+1)^2}+O\bigg(\frac{1}{(N+1)^3}\bigg).$$

We can provide a more streamlined version in terms of $1/N$ (see also Exercise 23). The book shows the expansion of $1/(N+1)=1/N-1/N^2+O(N^{-3})$. We need to replace the factors involving $1/(N+1)$ in the expansion of $e^{1/(N+1)}$ with the given expansion of $1/(N+1)$. We get

$$\boxed{e^{\frac{1}{N+1}} = 1 + \frac{1}{N} - \frac{1}{2N^2} + O\left(N^{-3}\right)}.$$

Exercise 33

We can expand the number of terms for $H_N$ from Table 4.6. The first approximation to within $O(1/N)$ is

$$\begin{align*} (H_N)^2 &= \bigg(\ln N+\gamma+\frac{1}{2N}+O(N^{-2}) \bigg) \bigg(\ln N+\gamma+\frac{1}{2N}+O(N^{-2}) \bigg) \\ &= \ln^2 N+2\gamma\ln N+\gamma^2+\frac{\ln N}{N}+O(1/N). \end{align*}$$

The second approximation to within $o(1/N)$ simply includes $\gamma/N$ that was previously absorbed into $O(1/N)$. Thus,

$$(H_N)^2 = \ln^2 N+2\gamma\ln N+\gamma^2+\frac{\ln N}{N}+\frac{\gamma}{N}+o(1/N).$$

Exercise 34

$$\begin{align*} \cot x &= \frac{\cos x}{\sin x} = \frac{1-x^2/2+x^4/24+O(x^6)}{x-x^3/6+x^5/120+O(x^7)} \\ &= (1-x^2/2+x^4/24+O(x^6))\,\frac{1}{x-x^3/6+x^5/120+O(x^7)} \\ &= \frac{1-x^2/2+x^4/24+O(x^6)}{x}\,\frac{1}{1-x^2/6+x^4/120+O(x^6)} \\ &= \frac{1-x^2/2+x^4/24+O(x^6)}{x}\,(1+x^2/6-x^4/120+x^4/36+O(x^6)) \\ &= \frac{1-x^2/3-x^4/45}{x} \\ &= 1/x-x/3-x^3/45+O(x^5). \end{align*}$$

Notice that $O(x^5)$ is a sharper remainder than $O(x^4)$; we should always seek tightest bounds. In the derivation, we have used the first 3 terms of the geometric series, instead of just two as in the example from the book.

Exercise 35

$$\begin{align*} \frac{x}{e^x-1} &= -\frac{x}{1-e^x} \\ &= -\frac{x}{1-(1+x+x^2/2+x^3/6+x^4/24+x^5/120+O(x^6))} \\ &= \frac{1}{1+x/2+x^2/6+x^3/24+x^4/120+O(x^5)} \\ &= 1-x/2-x^2/6-x^3/24-x^4/120+(-x/2-x^2/6-x^3/24)^2+(-x/2-x^2/6)^3+(-x/2)^4+O(x^5) \\ &= 1-x/2+x^2/12-x^4/720+O(x^5). \end{align*}$$

Exercise 36

A full treatment of this topic is available in the paper Asymptotic Expansions of Central Binomial Coefficients and Catalan Numbers.

Exercise 37 🌟

$$\begin{align*} \frac{1}{N+1}\binom{3N}{N} &= \exp\bigg\{\ln ((3N)!)-\ln (N!)-\ln ((2N)!)-\ln(N+1)\bigg\} \\ &= \exp\bigg\{\left(3N+\frac{1}{2}\right)\ln (3N)-3N+\ln \sqrt{2\pi}+O(1/N) \\ &\qquad -\left(N+\frac{1}{2}\right)\ln N+N-\ln \sqrt{2\pi}+O(1/N) \\ &\qquad -\left(2N+\frac{1}{2}\right)\ln (2N)+2N-\ln \sqrt{2\pi}+O(1/N) \\ &\qquad -\ln N+O(1/N)\bigg\} \\ &= \exp\bigg\{\left(3N+\frac{1}{2}\right)\ln 3-\left(2N+\frac{1}{2}\right)\ln 2-\frac{3}{2}\ln N-\ln \sqrt{2\pi}+O(1/N)\bigg\} \\ &= \frac{27^N}{4^N}\cdot\frac{\sqrt 3}{2\sqrt{\pi} N^{3/2}}\left(1+O(1/N)\right). \end{align*}$$

There is an important technical detail not explicitly mentioned in the book, which is $e^{O(1/N)}=1+O(1/N)$ (see Table 4.2).

Exercise 38

This is simpler variant of the previous exercise.

$$\begin{align*} \frac{(3N!)}{(N!)^3} &= \exp\bigg\{\ln ((3N)!)-3\ln (N!)\bigg\} \\ &= \exp\bigg\{\left(3N+\frac{1}{2}\right)\ln (3N)-3N+\ln \sqrt{2\pi}+O(1/N) \\ &\qquad -3\left(N+\frac{1}{2}\right)\ln N+3N-3\ln \sqrt{2\pi}+O(1/N)\bigg\} \\ &= \exp\bigg\{\left(3N+\frac{1}{2}\right)\ln 3-\ln N-2\ln \sqrt{2\pi}+O(1/N)\bigg\} \\ &= 27^N\frac{\sqrt 3}{2\pi N}\left(1+O(1/N)\right). \end{align*}$$

Exercise 39 🌟

$$\begin{align*} \left(1-\frac{\lambda}{N}\right)^N &= \exp\bigg\{N\ln \left(1-\frac{\lambda}{N}\right)\bigg\} \\ &= \exp\bigg\{N\left(-\frac{\lambda}{N}+O(1/N^2)\right)\bigg\} \\ &= \exp\bigg\{-\lambda+O(1/N)\bigg\} \\ &= e^{-\lambda}+O(1/N). \end{align*}$$

Based on the asymptotic expansion, the approximate value of the expression is $e^{-\lambda}$ for large $N$.

Exercise 40

$$\begin{align*} \left(1-\frac{\ln N}{N}\right)^N &= \exp\bigg\{N\ln \left(1-\frac{\ln N}{N}\right)\bigg\} \\ &= \exp\bigg\{N\left(-\frac{\ln N}{N}-\frac{\ln^2 N}{2N^2}-\frac{\ln^3 N}{3N^3}+O(\ln^4 N/N^4)\right)\bigg\} \\ &= \exp\bigg\{-\ln N-\frac{\ln^2 N}{2N}-\frac{\ln^3 N}{3N^2}+O(\ln^4 N/N^3)\bigg\} \\ &= \frac{1}{N}\exp\bigg\{-\frac{\ln^2 N}{2N}-\frac{\ln^3 N}{3N^2}\bigg\}(1+O(\ln^4 N/N^3)) \\ &= \frac{1}{N}-\frac{\ln^2 N}{2N^2}+\frac{\ln^4 N}{8N^3}+o(\ln^4 N/N^3). \end{align*}$$

The middle term in the penultimate line must be expanded as $1+x+x^2/2$, where $x$ is the argument to the exponential function. We must retain the three asymptotically largest components.

Exercise 41

When interest is compounded daily at a 10% annual rate on a $10,000 principal, after 365 days, the amount is . Instead of computing this value directly, let’s apply the result from Exercise 39. Here, we have $\lambda=-0.1$, so the total amount increases to . This is about $51.8 more than what would be paid if interest were paid once a year.

The exact formula gives $51.6, which is $0.02 less than our quick calculation. This showcases the advantages of using asymptotic approximations.

Exercise 42

$$\begin{align*} \exp\bigg\{1+\frac{1}{N}+O(1/N^2)\bigg\} &= e \cdot \exp\bigg\{\frac{1}{N}+O(1/N^2)\bigg\} \\ &= e\left(1+\frac{1}{N}+O(1/N^2)\right) \\ &= e+.\frac{e}{N}+O(1/N^2). \end{align*}$$

Exercise 43

For large $N$, using Stirling's approximation for $N!$ and expansion of the geometric series, we get

$$\frac{1}{N!} = \frac{1}{\sqrt{2\pi N}} \left(\frac{e}{N}\right)^N \left(1 - \frac{1}{12N} + O\left(\frac{1}{N^2}\right)\right).$$

Nonetheless, if we would substitute this into the sine function, then we would go down the rabbit hole. $\frac{1}{N!}$ is already a rational function of $N$, hence we can directly use it in further expansions.

$$\begin{align*} \ln\left(\sin\left(\frac{1}{N!}\right)\right) &= \ln\left(\frac{1}{N!} \left(1+O\left(\frac{1}{N^2}\right)\right)\right) \\ &= \ln\left(\frac{1}{N!}\right) + \ln\left(1+O\left(\frac{1}{N^2}\right)\right) \\ &= -\ln (N!) + O\left(\frac{1}{N^2}\right) \\ &= -N \ln N + N - \ln \sqrt N - \ln \sqrt{2\pi} - \frac{1}{12N} + O\left(\frac{1}{N^2}\right). \end{align*}$$

Exercise 44

$$\begin{align*} \sin(\tan(1/N)) &= \sin\left(\frac{1}{N}+\frac{1}{3N^3}+O\left(\frac{1}{N^5}\right)\right) \\ &= \frac{1}{N}+\frac{1}{3N^3}-\frac{1}{6N^3}+O\left(\frac{1}{N^5}\right) \\ &= \frac{1}{N}+\frac{1}{6N^3}+O\left(\frac{1}{N^5}\right) \sim \frac{1}{N}. \end{align*}$$

$$\begin{align*} \tan(\sin(1/N)) &= \tan\left(\frac{1}{N}-\frac{1}{6N^3}+O\left(\frac{1}{N^5}\right)\right) \\ &= \frac{1}{N}-\frac{1}{6N^3}+\frac{1}{3N^3}+O\left(\frac{1}{N^5}\right) \\ &= \frac{1}{N}+\frac{1}{6N^3}+O\left(\frac{1}{N^5}\right) \sim \frac{1}{N}. \end{align*}$$

At this point, we could say that the order of growth of $\sin(\tan(1/N)) –\tan(\sin(1/N))$ is $O(N^{-5})$, but this would be a loose bound. Since the first two terms match, we must expand until we find a difference. Let $x=1/N$ and leverage WolframAlpha to perform the hard work.

$$\begin{align*} \text{series sin(tan(x)) to order 7} &= x + \frac{1}{6}x^3 - \frac{1}{40}x^5 - \frac{55}{1008}x^7 + O(x^9) \\ \text{series tan(sin(x)) to order 7} &= x + \frac{1}{6}x^3 - \frac{1}{40}x^5 - \frac{107}{5040}x^7 + O(x^9). \end{align*}$$

Apparently, we have a mismatch at the 4th term, thus the order of growth of $\sin(\tan(1/N)) –\tan(\sin(1/N))$ is $O(N^{-7})$.

Exercise 45

$$\begin{align*} T_N &= \frac{4^N}{\sqrt {\pi N^3}}(1+O(1/N)) \\ H_N &= \ln N+\gamma+O(1/N). \end{align*}$$

By substituting $N=T_N$ into the expansion of $H_N$, we get

$$H_{T_N} = 2N\ln 2-\ln \sqrt {\pi N^3}+\gamma+O(1/N).$$

Exercise 46

This exercise is about the asymptotic expansion of the Lambert W function. The cited article contains the full expansion in terms of substitutions $L_1$ and $L_2$. We depict here the steps leading to the that expression using those symbols.

We derive the basic equation marked with an asterisk

$$\begin{align*} n &= a_n e^{a_n} \\ \ln n &= \ln a_n + a_n \\ a_n &= L_1 - \ln a_n \qquad \text{(*)}. \end{align*}$$

The first iteration of bootstrapping gives $a_n \approx L_1$. The second iteration gives $a_n \approx L_1 - L_2$. The third iteration gives

$$\begin{align*} a_n &\approx L_1 - \ln(L_1 - L_2) \\ &= L_1 - \ln \left( L_1 \left( 1 - \frac{L_2}{L_1} \right) \right) \\ &= L_1 - L_2 - \ln \left( 1 - \frac{L_2}{L_1} \right) \\ &\approx L_1 - L_2 + \frac{L_2}{L_1}. \end{align*}$$

By carrying out one more iteration, we get the equation from the cited article to within the requested accuracy. For the sake of completeness, here is the identity without using symbols $L_1$ and $L_2$

$$\boxed{a_n = \ln n - \ln \ln n + \frac{\ln \ln n}{\ln n} + \frac{(\ln \ln n)^2 - 2\ln \ln n}{2(\ln n)^2} + O\left( \frac{1}{(\log n)^3} \right)}.$$

Exercise 47 🌟

We need to provide the reversion of the power series y = c₀ + c₁x + c₂x² + c₃x³ + O(x⁴). By applying the hint from the book, this equation transform into $z = x + c'_2x^2 + c'_3x^3 + O(x^4)$. We already know the reversion of this form from the book:

$$x=z-c'_2z^2+(2c'_2-c'_3)z^3+O(z^4).$$

Now, we just need to express it again in terms of $y$ and the original coefficients

$$\boxed{x=\frac{y-c_0}{c_1} - \frac{c_2}{c_1^3}(y-c_0)^2 + \frac{2c_2^2 - c_1 c_3}{c_1^5}(y-c_0)^3 + O((y-c_0)^4)}.$$

In series reversion, the expansion for $x$ is in powers of the small quantity $y - c_0$, not $y$ itself (unless $c_0 = 0$). Therefore, the error term should be written as $O((y-c_0)^4)$. Using $O(y^4)$ is incorrect when $c_0 \neq 0$ because $y$ doesn’t tend to zero.

Exercise 48

$\sum_{k\ge 1} 1/k^2=\pi^2/6$, which is known as the Basel problem. According to the direct comparison test, our sum $\sum_{k\ge 1} 1/(k^2H_k)$ converges, too. The tail $R_N$ can be approximated using the asymptotic expansion of $H_N=\ln N+\delta$ (see Table 4.6), where $\delta>0$ for large $N$. This gives

$$R_N=\sum_{k>N} \frac{1}{k^2H_k}=\sum_{k>N} \frac{1}{k^2(\ln k+\delta)}\sim\sum_{k>N} \frac{1}{k^2\ln k} \approx \int_N^\infty \frac{1}{x^2 \ln x} \, dx.$$

We can estimate $R_N$ by using integration by parts to find the leading asymptotic term. Let $u = (\ln x)^{-1}$ and $dv = x^{-2} dx$. Then $du = -x^{-1}(\ln x)^{-2} dx$ and $v = -x^{-1}$.

$$\begin{align*} \int_N^\infty \frac{1}{x^2 \ln x} dx &= -\frac{1}{x \ln x} \bigg|_N^\infty - \int_N^\infty \frac{1}{x^2 (\ln x)^2} dx \\ &= \frac{1}{N \ln N} - \int_N^\infty \frac{1}{x^2 (\ln x)^2} dx \\ &\therefore \boxed{R_N=\frac{1}{N \ln N} + O\left(\frac{1}{N (\log N)^2}\right)}. \end{align*}$$

We can conclude that

$$\sum_{k=1}^{N} \frac{1}{k^{2} H_{k}} =C - \frac{1}{N \ln N} + O\left(\frac{1}{N (\log N)^2}\right).$$

What’s the purpose of all this? Without our asymptotic estimate, if we wanted to find the value of $C$, we would just sum the first $N$ terms. Because the original error is $\approx \frac{1}{N \ln N}$, the series converges excruciatingly slowly. But now we can rearrange the equation to compute $C$ differently

$$C =\sum_{k=1}^N \frac{1}{k^2 H_k} + \frac{1}{N \ln N} + O\left(\frac{1}{N (\log N)^2}\right).$$

The new error rate drops much faster, so we save both time and increase accuracy. In spirit, this technique of boosting numerical computations is known as Richardson extrapolation. There are many other similar methods to speed up convergence of series.

Exercise 49