Chapter 4: Asymptotic Approximations

Exercise 4.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 4.2 🌟

This exercise demonstrates that $g(N)=O(f(N))$ also encompasses asymptotically negative functions. 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.

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,$$

thus, $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 4.3

$$\lim_{N \to \infty} \frac{N^\alpha}{N^\beta}=\lim_{N \to \infty} \frac{1}{N^{\beta-\alpha}}=0 \qquad \text{($\alpha<\beta \implies \beta-\alpha>0$)}.$$

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

Exercise 4.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 (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).$$

---

$$\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)^r \\ &= \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*}$$

---

$$\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)^r \\ &= \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 factor 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 4.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 4.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 4.7

The definition in 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. In this context, the O-notation is abused to mean something different than a tight upper bound.

$$\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 4.5, thus $e^{-N^\epsilon}$ is exponentially small.

Exercise 4.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 previously, we see that now $\log \log n$ grows faster than any constant. Therefore, $(\log N)^{-\log N}$ is exponentially small.

Exercise 4.9 🌟

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

$$\begin{align*} (\alpha/\beta)^N &=e^{\ln {(\alpha/\beta)^N}} \\ &=e^{N\ln {(\alpha/\beta)}} \\ &= e^{-N \underbrace{|\ln {(\alpha/\beta)}|}_{\epsilon}}. \end{align*}$$

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.52%.

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

Exercise 4.10

See the remark for Exercise 4.7.

Let $f(N)$ be exponentially small, meaning for any fixed $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 4.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 discrepancy $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 (asymptotically speaking).

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}$.

Exercise 4.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 4.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 (see also Exercise 2.68)

$$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. Because $\alpha > 0$, the geometric series is "head-dominated" (the first few terms contribute the most to the sum). The errors introduced by the perturbation $c$ accumulate at the tail end of the series where the terms are small. See the next section of why/how $f(x)=x^\alpha$ belongs to the class of functions that permits this reasoning.

Extending the Class of Functions

In order to apply the above logic to a broader class of functions $f(x)$, we would need the following to hold:

• The term $f(x/\beta^i)$ behaves like $\beta^{-\alpha i}f(x)$, so we can factor $f(x)$ out of the sum, just like we did with $x^\alpha$.

• The perturbation $c$ disappears for large $x$, since we expect $\frac{f(x+c)}{f(x)} \to 1$ for this class of functions.

If $f(x)$ is a positive non-decreasing regularly varying function with index $\rho \in \R$ (see Definition 4 in the cited paper), meaning

$$\lim_{x \to \infty} \frac{f(\gamma x)}{f(x)} = \gamma^\rho \text{ for any } \gamma > 0,$$

then we may assume the previously listed properties. This covers most functions polynomial in $x$ and $\log x$. For example, $f(x)=x^2\log x$ satisfies this, since

$$f(\gamma x) = (\gamma x)^2 \log(\gamma x) = \gamma^2 x^2 (\log \gamma + \log x) \sim \gamma^2 x^2 \log x.$$

Let’s employ the squeeze theorem to prove that we can perturb the arguments without impacting the asymptotic behavior. For any $\epsilon > 0$, we can choose $x$ large enough, such that the perturbed argument $x+c$ is eventually "sandwiched" between two constant scalings of $x$. The rest follows from $f$ being a positive non-decreasing regularly varying function.

$$x(1 - \epsilon) < x + c < x(1 + \epsilon) \\[0.2cm] f(x(1 - \epsilon)) \leq f(x + c) \leq f(x(1 + \epsilon)) \\[0.2cm] \frac{f(x(1 - \epsilon))}{f(x)} \leq \frac{f(x + c)}{f(x)} \leq \frac{f(x(1 + \epsilon))}{f(x)} \\[0.2cm] \lim_{x \to \infty} \frac{f(x(1 - \epsilon))}{f(x)} \leq \liminf_{x \to \infty} \frac{f(x+c)}{f(x)} \leq \limsup_{x \to \infty} \frac{f(x+c)}{f(x)} \leq \lim_{x \to \infty} \frac{f(x(1 + \epsilon))}{f(x)} \\[0.2cm] (1 - \epsilon)^\rho \leq \liminf_{x \to \infty} \frac{f(x+c)}{f(x)} \leq \limsup_{x \to \infty} \frac{f(x+c)}{f(x)} \leq (1 + \epsilon)^\rho \\[0.2cm] \therefore \lim_{x \to \infty} \frac{f(x+c)}{f(x)} = 1 \implies f(x+c) \sim f(x).$$

The conclusion follows by letting $\epsilon \to 0$.

A full 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 divide-and-conquer recurrences.

Exercise 4.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 4.15

According to Exercise 3.18

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

We have two poles of the 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 4.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 4.17 🌟

This exercise introduces several important theorems from real analysis.

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 4.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 an expression for the leading term.

Exercise 4.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 4.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 displays 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 4.21

Substitute $y=-x+x^2$ and expand $\ln (1+y)$. Tool support is useful, once the underlying mechanisms are properly understood, to save time and reduce a chance for an error. 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 4.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 4.23 🌟

This exercise demonstrates how to convert an asymptotic expansion to another scale.

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})$. Replacing the factors involving $1/(N-1)$ in the above series with the given expansion of $1/(N-1)$ 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 4.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).$$

The computed value is 2.20553, which is to within $10^{-4}$.

Exercise 4.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 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 slot 98 due to the carry from the 100th term:

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 ...

---

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 4.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 4.27

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

The specific bounds implied by the absolute formula are

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

The specific bounds implied by the relative formula are

$$0 \le \hat H_{1000} < 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 4.28

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

The specific bounds implied by the relative formula are

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

Exercise 4.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 4.30

We can apply Borel's integral summation method, which relies on the Laplace transform (see Exercise 3.14). This immediately gives

$$\begin{align*} \sum_{k\ge0} \frac{k!}{N^k} &= \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 && \text{$\left(\frac{1}{1-z/N}=\frac{N}{N-z}\right)$} \\ &= N e^{-N} \operatorname{Ei}(N) = f(N). \end{align*}$$

The derivation uses the exponential integral to craft the "closed-form" solution (see also section 4.8 of the book). The last line follows after employing the substitution $u=z-N$.

Exercise 4.31

There is a complementary $\omega$-notation for the opposite direction with respect 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 4.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 4.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 4.32

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

$$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 4.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 4.33

We can expand the number of terms for $H_N$ from Table 4.6. The 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 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 4.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+O(x^5)}{x} \\ &= 1/x-x/3-x^3/45+O(x^4). \end{align*}$$

Exercise 4.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 4.36

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

Exercise 4.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*}$$

Exercise 4.38

$$\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 4.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 4.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 4.41

When interest is compounded daily at a 10% annual rate on a $10,000 principal, after 365 days, the amount is $\$10,000(1+0.1/365)^{365}$. Instead of computing this value directly, let’s apply the result from Exercise 4.39. Here, we have $\lambda=-0.1$, so the total amount increases to $\approx \$10,000 \times e^{0.1}=\$11,051.7$. This is about $51.7 more than what would be paid if interest were paid once a year.

The exact formula gives ≈$11,051.6, which is $0.1 less than our quick calculation. This showcases the advantages of using asymptotic approximations.

Exercise 4.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 4.43

$$\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 4.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 4.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)=2N \ln 2 - \frac{3}{2}\ln N + \gamma - \frac{1}{2}\ln \pi + O(1/N).$$

Exercise 4.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=\ln n$ and $L_2=\ln \ln n$. We sketch the steps leading to that expression using the reversion technique from the book.

Start with 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 \sim L_1$. The second iteration gives $a_n \sim L_1 - L_2$. The third iteration gives

$$\begin{align*} a_n &\sim 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) \\ &\sim L_1 - L_2 + \frac{L_2}{L_1}. \end{align*}$$

By carrying out two additional iterations, 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} + \frac{2(\ln \ln n)^3 - 9(\ln \ln n)^2 + 6\ln \ln n}{6(\ln n)^3}+ O\left( \frac{1}{(\log n)^3} \right)}.$$

Exercise 4.47 🌟

This exercise generalizes the reversion method presented in the book.

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_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)}.$$

The expansion of $x$ is in powers of the small quantity $y - c_0$, not $y$ itself (unless $c_0 = 0$). Using purely $y$ is incorrect when $c_0 \neq 0$ because $y$ doesn’t tend to zero.

Exercise 4.48

$\sum_{k\ge 1} 1/k^2=\pi^2/6$ is known as the Basel problem. According to the direct comparison test, the sum $\sum_{k\ge 1} 1/(k^2H_k)$ also converges to some constant $C$. The tail $R_N$ can be approximated using the asymptotic expansion of $H_N\sim\ln N$ (see Table 4.6). This gives

$$R_N=\sum_{k>N} \frac{1}{k^2H_k}<\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 \\ &\approx \frac{1}{N \ln N} - \frac{1}{\ln N}\int_N^\infty \frac{1}{x^2 \ln x} dx \\ &\therefore \boxed{R_N=\frac{1}{N \ln N} +O\left(\frac{1}{N \log^2 N}\right)}. \end{align*}$$

This gives

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

so that $1+1/6+1/16.5+1/(3\ln 3) \approx 1.53$ is already a good approximation to the constant $C$, just by taking the first 3 terms (together with a correction factor). It is a trivial matter to calculate the value of this constant to any reasonable desired accuracy.

Exercise 4.49

$$\sum_{k=0}^{N} \frac{1}{F_k} = \psi - R_N.$$

The infinite sum converges to the reciprocal Fibonacci constant $\psi$. Fibonacci numbers grow exponentially, $F_k \sim\phi^k / \sqrt{5}$ where $\phi$ is the golden ratio. Consequently, the terms in the tail decay exponentially and the tail sum can be approximated by a geometric series. Thus, $R_N=O(\phi^{-N})$.

Exercise 4.50

$$\begin{align*} \sum_{k=0}^{N} \frac{2^k}{2^k+1} &= \sum_{k=0}^{N} \left(1 - \frac{1}{2^k+1}\right) \\ &= N+1 - \sum_{k=0}^{N} \frac{1}{2^k+1} \\ &= N+1 - \left(\underbrace{\sum_{k\ge0} \frac{1}{2^k+1}}_{C}-\underbrace{\sum_{k>N} \frac{1}{2^k+1}}_{R_N}\right). \end{align*}$$

The tail can be bounded analogously to the example given in the book pertaining to tries. Therefore, $R_N=O(2^{-N})$.

Exercise 4.51

Here, we need to use the tail, since the terms in a finite sum are rapidly increasing.

$$\sum_{k=0}^{N} 2^{k^2}=2^{N^2} \left(1 + O\left(2^{-2N}\right)\right).$$

Exercise 4.52

$$\begin{align*} \sum_{k=1}^N k^t &= \sum_{k=0}^N k^t \\ &= \frac{N^{t+1}}{t+1} + \frac{N^t}{2} + \sum_{i=1}^{\lfloor t/2 \rfloor} \frac{B_{2i}}{(2i)!} t^{\underline{2i-1}} N^{\,t-2i+1}. \end{align*}$$

Notice the usage of the falling factorial (see also Chapter 3 of the book).

Exercise 4.53

Let $h(x)=\frac{1}{1+x}$, so $h^{(n)}(x)=(-1)^n\frac{n!}{(1+x)^{n+1}}$. This gives

$$\begin{align*} \sum_{0\le k\le N} h(k/N) &\sim N\int_0^1 h(x)\,dx+\frac{h(0)+h(1)}{2}+\sum_{i\ge1}\frac{B_{2i}}{(2i)!}\frac{1}{N^{2i-1}}\;h^{(2i-1)}(x)\Big|_0^1 \\ &= N\ln 2+\frac{3}{4}+\sum_{i\ge1} \frac{B_{2i}}{2i}\,\frac{1-2^{-2i}}{N^{2i-1}} \\ &= N\ln 2+\frac34+\frac{1}{16N}-\frac{1}{128N^{3}}+\cdots \\ &= N\ln 2+\frac34+O(N^{-1}). \end{align*}$$

Exercise 4.54

Let $h(x)=\frac{1}{1+x^2}$, so $h'(x)=-\frac{2x}{(1+x^{2})^{2}}$. We don’t need higher derivatives, since only the first Bernoulli correction is required. This gives

$$\begin{align*} \sum_{0\le k\le N} h(k/N) &\sim N\int_0^1 h(x)\,dx+\frac{h(0)+h(1)}{2}+\sum_{i\ge1}\frac{B_{2i}}{(2i)!}\frac{1}{N^{2i-1}}\;h^{(2i-1)}(x)\Big|_0^1 \\ &= \frac{\pi N}{4}+\frac{3}{4}-\frac{1}{24N}+O(N^{-3}). \end{align*}$$

The definite integral can be computed using WolframAlpha by issuing Integrate[1/(1+x^2),{x,0,1}].

Exercise 4.55

Let’s use the formula from the book

$$\gamma = H_n - \ln n - \frac{1}{2n} + \frac{1}{12n^2} - \frac{1}{120n^4}.$$

The following Python script dumps the value of $\gamma$ accurate to 10 decimal places. By uncommenting (adding) additional correction terms, we can attain the same accuracy in third of the time, since we only need to take seven summands from the harmonic sum.

from decimal import Decimal, getcontext
getcontext().prec = 20

def calculate_gamma(n):
    h_n = sum(Decimal(1) / Decimal(i) for i in range(1, n + 1))
    ln_n = Decimal(n).ln()
    # Euler-Maclaurin correction terms from the book.
    term1 = Decimal(1) / (Decimal(2) * n)
    term2 = Decimal(1) / (Decimal(12) * n ** 2)
    term3 = Decimal(1) / (Decimal(120) * n ** 4)
    # These are higher-order terms that can be included for speeding things up.
    term4 = Decimal(1) / (Decimal(252) * n ** 6)
    term5 = Decimal(1) / (Decimal(240) * n ** 8)

    # Uncomment the last two terms for faster convergence.
    return h_n - ln_n - term1 + term2 - term3  #+ term4 - term5

# Reduce this to 7 if you have uncommented the last two terms for faster convergence.
n_val = 21
result = calculate_gamma(n_val)
print(f"Euler's Constant (γ) ≈ {result:.10f}")

The code prints

Euler's Constant (γ) ≈ 0.5772156649

Wikipedia has a full description of the Euler’s constant.

Exercise 4.56

We’ve already mentioned in Exercise 4.48 that $\sum_{k=1}^\infty \frac{1}{k^2}=\zeta(2)=\pi^2/6$. Let’s take $f(x)=1/x^2$ and compute the Euler-Maclaurin constant

$$C_f=\lim_{N \to \infty} \left(\sum_{1 \le k \le N} \frac{1}{k^2} -\int_1^N\frac{dx}{x^2}-\frac{f(N)}{2}\right)=\frac{\pi^2}{6}-1.$$

Employing Theorem 4.3 gives

$$\begin{align*} H_N^{(2)} &= \sum_{1 \le k \le N}\frac{1}{k^2} \\ &= \int_1^N\frac{dx}{x^2}+\frac{1}{2N^2}+C_f + \sum_{i>0} \frac{B_{2i}}{(2i)!} f^{(2i-1)}(N) \\ &= -\frac{1}{N} +1+ \frac{1}{2N^2} +\frac{\pi^2}{6}-1+ \sum_{i>0} \frac{B_{2i}}{(2i)!} \left( -\frac{(2i)!}{N^{2i+1}} \right) \\ &= \frac{\pi^2}{6}-\frac{1}{N} + \frac{1}{2N^2} - \sum_{i>0} \frac{B_{2i}}{N^{2i+1}} \\ &\sim \frac{\pi^2}{6}-\frac{1}{N} + \frac{1}{2N^2} - \frac{1}{6N^3} + \dots \end{align*}$$

Exercise 4.57

This is a variation of the previous exercise. The infinite sum converges to the Apéry's constant. Without repeating the technical details, we get

$$H_N^{(3)} = \zeta(3) - \frac{1}{2N^2} +O(N^{-3}).$$

Further generalization is covered in the article about asymptotic expansions of the generalized harmonic numbers on StackExchange for Mathematics.

Exercise 4.58

Using Theorem 4.3, as in the previous two exercises, we obtain the following asymptotic estimates

$$\begin{align*} \sum_{k=1}^{N} \sqrt{k} &= \frac{2}{3} N^{3/2} + \frac{1}{2} N^{1/2} + \zeta(-1/2) + \frac{1}{24} N^{-1/2} + O(N^{-2}) \\[4pt] \sum_{k=1}^{N} \frac{1}{\sqrt{k}} &= 2\sqrt{N} + \zeta(1/2) + \frac{1}{2} N^{-1/2} - \frac{1}{24} N^{-3/2} + O(N^{-2}) \\[4pt] \sum_{k=1}^{N} \frac{1}{\sqrt[3]{k}} &= \frac{3}{2} N^{2/3} + \zeta(1/3)+ \frac{1}{2} N^{-1/3} - \frac{1}{36} N^{-4/3} + O(N^{-2}). \end{align*}$$

The fractional arguments of the Riemann zeta function do not have known simple closed forms, like in Exercise 4.56; they’re typically evaluated numerically.

Exercise 4.59 🌟

This exercise introduces a summation technique for alternating series.

The main idea is presented in the article about the asymptotic expansion of the alternating harmonic numbers on Wikipedia. In both subtasks, we separate the terms based on the parity of $N$.

---

Expansion of $\sum_{1 \le k \le N} \frac{(-1)^k}{k}$

Let’s start by assuming $N=2n$. This gives

$$\begin{align*} S_{2n} &= \sum_{k=1}^{2n} \frac{(-1)^k}{k} \\ &= -\sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} \qquad \text{(form used on Wikipedia)} \\ &= \sum_{k=1}^n \frac{1}{2k} - \sum_{k=1}^n \frac{1}{2k-1} \\ &= \sum_{k=1}^n \frac{1}{2k} - \left( H_{2n} - \sum_{k=1}^n \frac{1}{2k} \right) \\ &= 2 \cdot \frac{1}{2} H_n - H_{2n} \\ &= H_n - H_{2n} \\ &\sim -\ln 2 + \frac{1}{4n} - \frac{1}{16n^2} + \cdots \\ &= -\ln 2 + \frac{1}{2N} - \frac{1}{4N^2} + \cdots \end{align*}$$

When $N=2n-1$, we’ve

$$\begin{align*} S_N &= S_{2n} - \frac{(-1)^{2n}}{2n} \\ &= S_{N+1} - \frac{1}{N+1} \\ &\sim -\ln 2 + \frac{1}{2(N+1)} - \frac{1}{4(N+1)^2} - \frac{1}{N+1} \\ &= -\ln 2 - \frac{1}{2(N+1)} - \frac{1}{4(N+1)^2} \\ &\sim -\ln 2 - \frac{1}{2N} + \frac{1}{4N^2} + \cdots \end{align*}$$

The last line follows by transforming $1/(N+1)$ in terms of $1/N$, as explained in the book (see also Exercise 4.32). But notice the similarity, only the signs are flipped. Therefore, we can combine the two cases into the following generic formula

$$\sum_{k=1}^N \frac{(-1)^k}{k} = -\ln 2 + (-1)^N \left( \frac{1}{2N} - \frac{1}{4N^2} + \cdots \right)$$

Euler–Boole summation is a method for summing alternating series, that could be regarded as an alternating equivalent of Euler-Maclaurin summation.

---

Expansion of $\sum_{1 \le k \le N} \frac{(-1)^k}{\sqrt k}$

The alternating zeta function is known as the Dirichlet eta function.

Let’s start by assuming $N=2n$. This gives (see also the previous exercise about the expansion of $H_n^{(1/2)}$)

$$\begin{align*} S_{2n} &= \sum_{k=1}^{2n} \frac{(-1)^k}{\sqrt{k}} \\ &= \sum_{k=1}^n \frac{1}{\sqrt{2k}} - \sum_{k=1}^n \frac{1}{\sqrt{2k-1}} \\ &= \frac{1}{\sqrt{2}}H_n^{(1/2)} - \left( H_{2n}^{(1/2)} - \frac{1}{\sqrt{2}}H_n^{(1/2)} \right) \\ &= \sqrt{2}H_n^{(1/2)} - H_{2n}^{(1/2)} \\ &\sim (\sqrt{2}-1)\zeta(1/2) + \frac{1}{2\sqrt{N}}- \frac{1}{8N^{3/2}}\cdots \end{align*}$$

When $N=2n-1$, we’ve

$$S_N = S_{N+1} - \frac{1}{\sqrt{N+1}}.$$

As before, we can conclude that the odd case differs only in flipped signs. Thus,

$$\sum_{k=1}^N \frac{(-1)^k}{\sqrt{k}} = (\sqrt{2} - 1)\zeta(1/2) + (-1)^N \left( \frac{1}{2\sqrt{N}} - \frac{1}{8N^{3/2}} + \cdots \right)$$

Exercise 4.60

To find the asymptotic behavior of the generalized binomial coefficient, our primary goal is to determine the asymptotic expansion of the ratio $\frac{\Gamma(n+\alpha+1)}{\Gamma(n+1)}$ as $n \to \infty$. According to corollary of Theorem 4.3, we’ve

$$\ln \Gamma(n+1) = \left(n+\frac{1}{2}\right)\ln n - n + \ln \sqrt{2 \pi} + o(1).$$

The continuous extension for large $x$ is

$$\begin{align*} \ln \Gamma(x+1) &= \left(x + \frac{1}{2}\right)\ln x - x + \ln \sqrt{2 \pi} + o(1) \\ \therefore \ln \Gamma(n+\alpha+1) &= \left(n+\alpha+\frac{1}{2}\right)\ln(n+\alpha) - (n+\alpha) + \ln \sqrt{2 \pi} + o(1). \end{align*}$$

Substituting the two equations gives

$$\ln \frac{\Gamma(n+\alpha+1)}{\Gamma(n+1)} = \left(n+\alpha+\frac{1}{2}\right)\ln(n+\alpha) - \left(n+\frac{1}{2}\right)\ln n - \alpha + o(1).$$

We can apply Taylor expansion on $\ln (n+\alpha)$ to get

$$\ln(n+\alpha) = \ln\left(n\left(1 + \frac{\alpha}{n}\right)\right) = \ln n + \ln\left(1 + \frac{\alpha}{n}\right) = \ln n + \frac{\alpha}{n} + o(1).$$

Now, substituting back this expansion and simplifying yields

$$\ln \frac{\Gamma(n+\alpha+1)}{\Gamma(n+1)} = \alpha \ln n + o(1) \implies \frac{\Gamma(n+\alpha+1)}{\Gamma(n+1)} = n^\alpha e^{o(1)} \sim n^\alpha.$$

We get the required result

$$\binom{n+\alpha}{n} \equiv \frac{\Gamma(n+\alpha+1)}{\Gamma(n+1)\Gamma(\alpha+1)} \sim \frac{n^\alpha}{\Gamma(\alpha+1)}.$$

Exercise 4.61

Replace the asymptotic estimate used in the derivation of Theorem 4.5 with the inequality $-\ln(1+x)\ge-x$, valid for all $x \ge 0$. See the proof of the corollary of Theorem 4.5 for context.

Exercise 4.62

The proofs of the relative bounds for the Ramanujan Q- and R-distributions are literally the same. Stirling’s formula for $\ln N!$ is available in Table 4.6 in the book.

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

Notice that the above approximation is valid only for $k=o(N^{2/3})$. Under this regime, both Stirling error terms, $O(1/N)$ and $O(1/(N-k))$, "vanish" for large $N$. Furthermore, the $O(k^4/N^3)$ term is absorbed into $O(k^3/N^2)$.

The R-distribution is handled in an analogous fashion starting with

$$\ln \frac{N!N^k}{(N+k)!} = \ln N! - \ln(N+k)! + k \ln N .$$

Exercise 4.63

The best approach here is to simply reuse a high-quality implementation of the PMF for the binomial distribution. The following Python snippet demonstrates the typical usage scenario.

from scipy.stats import binom

# Create a binomial distribution object to reuse for different values of k.
dist = binom(n=9, p=0.5)

# Get probability for specific value of k.
print(dist.pmf(3))

Exercise 4.64

If $k=\sqrt N+O(1)$ we cannot reach the required accuracy by relying on Theorem 4.6 alone. We must go back to the proof from the book and add more terms to every component in the product. The augmented central binomial coefficient is

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

The extended product of the Ramanujan Q- and R-distributions is

$$\begin{align*} \frac{N!}{(N-k)!}\,\frac{N!}{(N+k)!} &= \exp\left\{\sum_{1 \le j < k} \ln\left(1 - \frac{j}{N}\right) - \sum_{1 \le j \le k} \ln\left(1 + \frac{j}{N}\right)\right\} \\ &= \exp\left\{\sum_{j=1}^k \left[ \ln\left(1 - \frac{j}{N}\right) - \ln\left(1 + \frac{j}{N}\right) \right] - \ln\left(1 - \frac{k}{N}\right)\right\} \\ &= \exp\left\{\sum_{j=1}^k \left( -\frac{2j}{N} - \frac{2j^3}{3N^3} + O\left(\frac{j^5}{N^5}\right) \right) - \ln\left(1 - \frac{k}{N}\right)\right\} \\ &= \exp\left\{-\frac{2}{N}\left(\frac{k^2+k}{2}\right) - \frac{2}{3N^3}\left(\frac{k^4+2k^3+k^2}{4}\right) + O\left(\frac{1}{N^2}\right) - \ln\left(1 - \frac{k}{N}\right)\right\} \\ &= \exp\left\{-\frac{2}{N}\left(\frac{k^2+k}{2}\right) - \frac{2}{3N^3}\left(\frac{k^4+2k^3+k^2}{4}\right) + \frac{k}{N} + \frac{k^2}{2N^2} + \frac{k^3}{3N^3} + O\left(\frac{1}{N^2}\right)\right\} \\ &= \exp\left\{-\frac{k^2}{N} - \frac{k^4}{6N^3} + \frac{k^2}{2N^2} - \frac{k^2}{6N^3} + O\left(\frac{1}{N^2}\right)\right\} \\ &= \exp\left\{-\frac{k^2}{N} - \frac{k^4}{6N^3} + \frac{k^2}{2N^2} + O\left(\frac{1}{N^2}\right)\right\} \\ &= \exp\left\{-1 - \frac{2\delta}{\sqrt{N}} + \frac{1/3 - \delta^2}{N} + \frac{\delta}{3N^{3/2}} + O\left(\frac{1}{N^2}\right)\right\} \\ &= e^{-1} \left( 1 - \frac{2\delta}{\sqrt{N}} + \frac{\delta^2 + 1/3}{N} + \frac{2\delta^3 - \delta}{3N^{3/2}} + O\left(\frac{1}{N^2}\right) \right). \end{align*}$$

The last two steps follow from substituting $k=\sqrt N + \delta$, where $\delta$ is the displacement (hidden constant inside the O-notation) and expanding $e^x$. Multiplying together the two components, we get

$$\frac{1}{2^{2N}}\binom{2N}{N-k} = \frac{e^{-1}}{\sqrt{\pi N}} \left( 1 - \frac{2\delta}{\sqrt{N}} + \frac{\delta^2 + 5/24}{N} + \frac{8\delta^3 - \delta}{12 N^{3/2}} + O\left(\frac{1}{N^2}\right) \right).$$

To get an absolute error, we would just distribute the leading term all the way through in the formula above and simplify.

Exercise 4.65

Exercise 4.66

This is the case when the binomial distribution can be efficiently approximated by a normal distribution centered at $pN$ (mean). For example, the book already uses such an approximation $\sim 1/\sqrt {\pi N/2}$ with $p=1/2$ in Figure 4.3. More generally, the estimated probability is

$$\sim \frac{1}{\sqrt {2 \pi N pq}}.$$

Exercise 4.67

The paper The Normal Approximation to the Binomial Distribution shows a full derivation by employing the hint from the book (see section 2); the shift factor $k$ is denoted as $\delta$. At the end, we get a formula similar to the one from Theorem 4.6.

More formally, this is known as the De Moivre–Laplace theorem; take a look at the alternative proof employing the log/exp technique from the book.

Exercise 4.68 🌟

This exercise demonstrates the principles of reuse within mathematics. Rather than constructing analyses from the ground up, it presents a systematic approach to modifying existing work to accommodate varying conditions.

Theorem 4.7 isn’t appropriate here because the mean $\mu=pN=\lambda \sqrt N$ isn’t bounded as $N \to \infty$. The previous exercise handles the case when $p$ is fixed. Nonetheless, we can tweak the method from the cited paper to arrive at a different approximation. In other words, the method itself needs to be adapted to a different asymptotic regime.

We list here the recipe for arriving at the final formula:

1. Our starting point with Stirling's formula is precisely equation (1) in the notes.

2. The $k$ in this exercise is analogous to $\delta$ in the paper. We set $x = Np + \delta$. The standard deviation in our new regime is $\sigma = \sqrt{Npq}=\sqrt{Np(1-p)} \sim \sqrt{\lambda \sqrt{N}} = \sqrt \lambda N^{1/4}$. So, allowing $\delta=O(N^{1/4})$ is exactly the same as allowing $x$ to deviate by a few standard deviations.

3. The notes expand $\ln(Np/x)$ and $\ln(Nq/(N-x))$ in powers of $\delta/(Np)$ and $\delta/(Nq)$. Nonetheless, $\delta/(Np) \gg \delta/(Nq)$, hence $\delta/(Nq)$ term's higher-order corrections are negligible compared to the former (only the one contributing to the exponent of $e$ matters). Observe that the largest correction $O(\delta^3/(Np)^2)$ cannot hide $p$, since it isn’t a constant anymore. At any rate, this boils down to $O(\delta^3/N)$.

4. The square root pre-factor is $\sqrt{\frac{n}{2\pi (np+\delta)(nq-\delta)}} = \frac{1}{\sqrt{2\pi npq}} \left(1 + \frac{\delta}{np}\right)^{-1/2} \left(1 - \frac{\delta}{nq}\right)^{-1/2}$ Using the Taylor expansion $(1 + u)^{-1/2} \sim 1 - \frac{1}{2}u$ for small $u$, we get that the dominant correction term becomes $O(\delta/(Np))=O(\delta/\sqrt N)$.

After incorporating all previously mentioned changes, we obtain (using $k$ instead of $\delta)$

$$P\{X=\mu+k\}=\frac{1}{\sqrt{2\pi} \sigma} \, e^{-\frac{k^2}{2\sigma^2}} \left(1 + O(1/\sqrt N)+ O(k/\sqrt N)+O(k^3/N)\right).$$

If $k=O(\sigma)$ then the relative error is $O(N^{-1/4})$. If $k = O(N^{1/3})$ then the error jumps to $O(1)$, so we must have at least $k=o(N^{1/3})$. Finally, the baseline error term $O(N^{-1/2})$ covers the edge case $k=0$.

Exercise 4.69

This is a variation of the previous exercise, so we don’t repeat all the steps again; the methodology is the same. Let $\mu = Np = \lambda N / \ln N$ and $\sigma^2 = Npq = \mu(1-p) = \mu(1 - \lambda/\ln N)\sim \mu$. The following asymptotic holds:

$$P\{X=\mu+k\}=\frac{1}{\sqrt{2\pi} \sigma} \, e^{-\frac{k^2}{2\sigma^2}} \left(1 + O\left(\frac{\ln N}{N}\right)+ O\left(\frac{k\ln N}{N}\right)+O\left(\frac{k^3\ln^2 N}{N^2}\right)\right).$$

If $k=O(\sigma)$ then the relative error is $O\left(\sqrt{\frac{\ln N}{N}}\right)$. Notice, as in the previous exercise, the explicit baseline error term that covers $k=0$.

Exercise 4.70

Let $x=k/\sqrt N$ so that $dk=\sqrt N dx$. This gives

$$\sum_{1 \le k \le k_0}e^{-k^2/(2N)}O\left(\frac{k}{N}\right)=\sqrt N \int_0^\infty e^{-x^2/2}O\left(\frac{x}{\sqrt N}\right)dx+O(1)=O\left(\underbrace{\int_0^\infty xe^{-x^2/2}dx}_{=1}\right)+O(1)=O(1).$$

$$\sum_{1 \le k \le k_0}e^{-k^2/(2N)}O\left(\frac{k^3}{N^2}\right)=\sqrt N \int_0^\infty e^{-x^2/2}O\left(\frac{x^3}{\sqrt N}\right)dx+O(1)=O\left(\underbrace{\int_0^\infty x^3e^{-x^2/2}dx}_{=2}\right)+O(1)=O(1).$$

The definite integrals can be easily computed in WolframAlpha.

Exercise 4.71

Let’s follow the hint from the book’s website for this exercise. This gives

$$\begin{align*} p_k=\frac{(N−k)^k(N−k)!}{N!} &= \prod_{0 \le j < k} \frac{N-k}{N-j} \qquad \text{(see Table 4.11)} \\ &= \exp\left\{\sum_{0 \le j < k} \bigg(\ln (N-k)-\ln (N-j)\bigg)\right\} \\ &= \exp\left\{\sum_{0 \le j < k} \bigg(\ln N(1-k/N)-\ln N(1-j/N)\bigg)\right\} \\ &= \exp\left\{\sum_{0 \le j < k} \bigg(\ln N+\ln(1-k/N)-\ln N-\ln (1-j/N)\bigg)\right\} \\ &= \exp\left\{k\ln(1-k/N)-\sum_{0 \le j < k} \ln (1-j/N)\right\} \\ &= \exp\left\{k\left(-\frac{k}{N}+O\left(\frac{k^2}{N^2}\right)\right)+\sum_{0 \le j < k} \left(\frac{j}{N}+O\left(\frac{j^2}{N^2}\right)\right)\right\} \\ &= \exp\left\{-\frac{k^2}{N}+O\left(\frac{k^3}{N^2}\right)+ \frac{k(k-1)}{2N}+O\left(\frac{k^3}{N^2}\right)\right\} \\ &= \boxed{e^{−k^2/(2N)}(1+O(k/N)+O(k^3/N^2))}. \end{align*}$$

Notice that $p_k$ is strictly decreasing as $k$ grows and has the same asymptotic approximation as the Q-distribution. Hence, by the same arguments as in the proof of Theorem 4.8, together with the solution of the previous exercise, we can confirm the validity of the approximation of $P(N)$.

Exercise 4.72

The paper On Ramanujan's Q-function by Flajolet et al. elaborates in detail the developments around Q- and R- distributions and provides the proof of this exercise.

Exercise 4.73

Assume $N$ is even for simplicity (odd $N$ gives the same asymptotic behavior). Let $k = N/2 ± \delta$ with $\delta = o(N^{2/3})$. We know that most of the probability mass will be concentrated around the mean. We can now apply Theorem 4.6 to get

$$\begin{align*} \binom{N}{k} &\sim \frac{2^N}{\sqrt{\frac{\pi N}{2}}} e^{-2\delta^2/N} \\ \binom{N}{k}^3 &\sim \frac{2^{3N}}{(\frac{\pi N}{2})^{3/2}} e^{-6\delta^2/N}. \end{align*}$$

Here, we’re only working with binomial coefficients rather than distribution. Therefore, we don’t divide by the normalization factor. By leveraging the Laplace method, similarly as in Theorem 4.8, we can uniformly bundle the diminishing tails (far away from the mean) into a single formula.

$$\begin{align*} \sum_{k} \binom{N}{k}^3 &\sim \frac{2^{3N}}{(\frac{\pi N}{2})^{3/2}} \sum_{\delta} e^{-6\delta^2/N} \\ &\sim \frac{2^{3N}}{(\frac{\pi N}{2})^{3/2}} \int_{-\infty}^{\infty} e^{-6\delta^2/N} d\delta \\ &= \frac{2^{3N}}{(\frac{\pi N}{2})^{3/2}} \cdot \sqrt{\frac{\pi N}{6}} \\ &= \frac{2^{3N+1}}{\sqrt{3} \pi N}. \end{align*}$$

For the generalized version of this exercise refer to the article An Asymptotic Formula for Binomial Sums (see the beginning of section 4). A sequence of values of the sum for different $N$ is known as the Franel numbers.

Exercise 4.74

Theorem 7.4 (Involutions) from the book provides all the details.

Wikipedia also offers a summary of the problem, including the required asymptotic estimate, known as telephone numbers.

Exercise 4.75 🌟

This exercise demonstrates in detail the Laplace method for sums.

To derive the asymptotic estimate for our sum, we use Stirling's approximation (see Table 4.6) to transform the discrete sum into a continuous integral dominated by a single "peak". This is the main idea behind the Laplace method. We start by dissecting the summand

$$\binom{N-k}{k} = \frac{(N-k)!}{k! (N-2k)!}.$$

Observe that it’s nonzero for $0 \le k \le N/2$, so let $k=\alpha N$ with $0 \le \alpha \le 1/2$. Substituting the approximation for each factorial and simplifying, we get

$$\begin{align*} \binom{N-\alpha N}{\alpha N} \sim \frac{1}{\sqrt{2\pi N}} \sqrt{\frac{1-\alpha}{\alpha(1-2\alpha)}} \cdot \left[ \frac{(1-\alpha)^{1-\alpha}}{\alpha^\alpha (1-2\alpha)^{1-2\alpha}} \right]^N \\ \binom{N-\alpha N}{\alpha N}^2 \sim \frac{1}{2\pi N} \left( \frac{1-\alpha}{\alpha(1-2\alpha)} \right) \cdot \exp\left( 2N \cdot f(\alpha) \right), \end{align*}$$

where

$$f(\alpha) = (1-\alpha)\ln(1-\alpha) - \alpha\ln\alpha - (1-2\alpha)\ln(1-2\alpha).$$

We can find the maximum $\alpha_0$ by typing in WolframAlpha

maximize (1-\alpha)\ln(1-\alpha) - \alpha\ln\alpha - (1-2\alpha)\ln(1-2\alpha)

It outputs $\alpha_0=1/2-1/(2\sqrt 5)$. At this specific point, $e^{f(\alpha_0)} = \phi$ (golden ratio). To see this, we should just raise $e$ to the maximum value reported by WolframAlpha. The square of this value is $\phi^2$.

Since the function $\binom{N-k}{k}^2$ drops rapidly from $\alpha_0$, we can approximate the sum using the Euler-Maclaurin formula. We expand $2N f(\alpha)$ as a Taylor series around $\alpha_0$

$$2N f(\alpha) \approx 2N f(\alpha_0) + N f''(\alpha_0)(\alpha - \alpha_0)^2.$$

With the help of WolframAlpha, we can compute symbolically the second derivative and evaluate it at $\alpha_0$

D[(1-\alpha)\ln(1-\alpha) - \alpha\ln\alpha - (1-2\alpha)\ln(1-2\alpha),{\alpha,2}]

This gives

$$f''(\alpha_0) = -\frac{\sqrt{5}}{\alpha_0(1-\alpha_0)(1-2\alpha_0)} = -5\sqrt{5}.$$

The sum is then approximated by the integral

$$\sum_k \binom{N-k}{k}^2 \sim \frac{1}{2\pi N} \frac{1-\alpha_0}{\alpha_0(1-2\alpha_0)} \phi^{2N} \int_{-\infty}^{\infty} e^{-5\sqrt{5}N (\alpha-\alpha_0)^2} N d\alpha= \frac{\phi^{2N+2}}{2 \sqrt{\pi N \sqrt{5}}}.$$

In essence, the Laplace method relies on the fact that as $N \to \infty$, the function becomes so incredibly "sharp" at the peak $\alpha_0$ that the tails of the distribution become negligible. Therefore, the error introduced by extending the integration limits to $\pm \infty$ is exponentially small. For example, just at some $\epsilon>0$ distance from $\alpha_0$ the contribution decreases to only $\phi^{2N} \cdot e^{-N(5\sqrt{5})\epsilon^2}$ (see also Exercise 4.10).

Exercise 4.76

We’ve a flipped Figure 4.7, where the first $\lg N$ terms are negligible, whilst the rest contribute around 1. Using the same bounds as in Theorem 4.10, we get

$$\sum_{0 \le j \le N} \left(1-\frac{1}{2^j}\right)^N = N - \lg N +O(\log \log N).$$

As noted in Theorem 4.10, the error bound can be tightened all the way down to $O(1)$.

Exercise 4.77

The first $\sqrt[t]{N}$ terms are significant, whilst the rest drops very quickly to zero. For large $N$, we can approximate this sum with an integral over the whole possible range for $j$. This gives

$$\begin{align*} \sum_{j \ge 0} \left(1-e^{-N/j^t}\right) &\sim \int_{0}^{\infty} \left(1 - e^{-N/x^t}\right) dx \\ &= \int_{\infty}^{0} (1 - e^{-u}) \left( -\frac{1}{t} N^{1/t} u^{-1 - 1/t} \right) du \\ &= \frac{N^{1/t}}{t} \int_{0}^{\infty} (1 - e^{-u}) u^{-1 - 1/t} du. \end{align*}$$

The second line follows after the substitution $u = N/x^t$, so that

$$dx = -\frac{1}{t} N^{1/t} u^{-1 - 1/t} du.$$

The last integral can be evaluated using integration by parts. Let $\alpha = 1/t$. Notice that $t>1$ implies $0<\alpha<1$. Using $v = (1 - e^{-u})$ and $dw = u^{-1-\alpha}du$ gives

$$\int_{0}^{\infty} u^{-1-\alpha} (1 - e^{-u}) du = \frac{u^{-\alpha}}{-\alpha} (1 - e^{-u}) \bigg|_{0}^{\infty} - \int_{0}^{\infty} \frac{u^{-\alpha}}{-\alpha} e^{-u} du= \frac{1}{\alpha}\Gamma(1 - \alpha).$$

Thus,

$$\sum_{j \ge 0} \left(1-e^{-N/j^t}\right) \sim \sqrt[t]N \,\, \Gamma\left(1 - \frac{1}{t}\right).$$