> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-aofa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/chapter-4-asymptotic-approximations.md). # 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 🌟 {% hint style="success" %} 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. {% endhint %} 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 {% hint style="warning" %} 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. {% endhint %} $$ \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](#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 🌟 {% hint style="success" %} 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. {% endhint %} $$ \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 {% hint style="warning" %} See the remark for [Exercise 4.7](#exercise-4.7). {% endhint %} 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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/Sy1KF5Jq9j0bEpfHwXvN#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 ](https://www.math.u-szeged.hu/~kevei/tanitas/1819regvar/RegVar_notes.pdf)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](https://mathworld.wolfram.com/SqueezeTheorem.html) 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$$. {% hint style="info" %} A full generalization of this exercise is part of the [Akra-Bazzi method](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method), which should be included in the toolbox of techniques for finding asymptotic approximations of divide-and-conquer recurrences. {% endhint %} ## Exercise 4.14 According to [Exercise 3.17](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#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. {% hint style="warning" %} 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$$. {% endhint %} $$ \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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#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 🌟 {% hint style="success" %} This exercise introduces several important theorems from real analysis. {% endhint %} According to the [fundamental theorem of algebra](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Intermediate_value_theorem), there is a real root in $$(1,2)$$. By using [Rouché's theorem](https://en.wikipedia.org/wiki/Geometrical_properties_of_polynomial_roots#Discs_containing_some_roots) 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](https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Higher_orders) and provides an expression for the leading term. ## Exercise 4.19 According to [Exercise 3.55](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#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](https://en.wikipedia.org/wiki/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\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}} \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](https://en.wikipedia.org/wiki/Borel_summation#Borel's_integral_summation_method), which relies on the Laplace transform (see [Exercise 3.14](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#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](https://en.wikipedia.org/wiki/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](#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](#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](#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](https://cs.uwaterloo.ca/journals/JIS/VOL17/Elezovic/elezovic5.pdf). ## 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](#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. {% hint style="info" %} The exact formula gives ≈$11,051.6, which is $0.1 less than our quick calculation. This showcases the advantages of using asymptotic approximations. {% endhint %} ## 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](https://en.wikipedia.org/wiki/Lambert_W_function#Asymptotic_expansions). 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 🌟 {% hint style="success" %} This exercise generalizes the reversion method presented in the book. {% endhint %} 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)}. $$ {% hint style="info" %} 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. {% endhint %} ## Exercise 4.48 $$\sum\_{k\ge 1} 1/k^2=\pi^2/6$$ is known as the [Basel problem](https://en.wikipedia.org/wiki/Basel_problem). According to the [direct comparison test](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Falling_and_rising_factorials) (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. {% code expandable="true" %} ```python 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}") ``` {% endcode %} The code prints ``` Euler's Constant (γ) ≈ 0.5772156649 ``` {% hint style="info" %} Wikipedia has a full description of the [Euler’s constant](https://en.wikipedia.org/wiki/Euler%27s_constant). {% endhint %} ## Exercise 4.56 We’ve already mentioned in [Exercise 4.48](#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](https://en.wikipedia.org/wiki/Ap%C3%A9ry%27s_constant). Without repeating the technical details, we get $$ H\_N^{(3)} = \zeta(3) - \frac{1}{2N^2} +O(N^{-3}). $$ {% hint style="info" %} Further generalization is covered in the article about [asymptotic expansions of the generalized harmonic numbers](https://math.stackexchange.com/a/1583465/753413) on StackExchange for Mathematics. {% endhint %} ## 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](#exercise-4.56); they’re typically evaluated numerically. ## Exercise 4.59 🌟 {% hint style="success" %} This exercise introduces a summation technique for alternating series. {% endhint %} The main idea is presented in the article about the [asymptotic expansion of the alternating harmonic numbers](https://en.wikipedia.org/wiki/Harmonic_series_\(mathematics\)#Alternating_harmonic_series) 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](#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) $$ {% hint style="info" %} [Euler–Boole summation](https://en.wikipedia.org/wiki/Euler%E2%80%93Boole_summation) is a method for summing alternating series, that could be regarded as an alternating equivalent of Euler-Maclaurin summation. {% endhint %} ***

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

{% hint style="info" %} The alternating zeta function is known as the [Dirichlet eta function](https://en.wikipedia.org/wiki/Dirichlet_eta_function). {% endhint %} 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. ```python 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](https://scipp-legacy.pbsci.ucsc.edu/~haber/ph116C/NormalApprox.pdf) 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. {% hint style="info" %} More formally, this is known as the [De Moivre–Laplace theorem](https://en.wikipedia.org/wiki/De_Moivre%E2%80%93Laplace_theorem); take a look at the alternative proof employing the log/exp technique from the book. {% endhint %} ## Exercise 4.68 🌟 {% hint style="success" %} 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. {% endhint %} 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](https://aofa.cs.princeton.edu/40asymptotic/) 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](https://algo.inria.fr/flajolet/Publications/FlGrKiPr95.pdf) 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\*} $$ {% hint style="info" %} For the generalized version of this exercise refer to the article [An Asymptotic Formula for Binomial Sums](https://www.sciencedirect.com/science/article/pii/S0022314X96900724) (see the beginning of section 4). A sequence of values of the sum for different $$N$$ is known as the [Franel numbers.](https://mathworld.wolfram.com/FranelNumber.html) {% endhint %} ## Exercise 4.74 Theorem 7.4 (Involutions) from the book provides all the details. {% hint style="info" %} Wikipedia also offers a summary of the problem, including the required asymptotic estimate, known as [telephone numbers](https://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29#Summation_formula_and_approximation). {% endhint %} ## Exercise 4.75 🌟 {% hint style="success" %} This exercise demonstrates in detail the Laplace method for sums. {% endhint %} 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 ```wolfram 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.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). $$ --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/chapter-4-asymptotic-approximations.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.