Lemma 1.3 in "Random graphs" by Frieze and Karoński contains the following treatment of asymptotics unclear to me.
Claim. Let $n,m \in \mathbb N, N = \binom n2, p= \frac mN$. Define $$u_k = \binom Nk p^k (1-p)^{N-k}$$ Assume $m,\frac {N-m}{\sqrt m} \to \infty$, then for large $n$:
$$\sum _{k=m}^{m+\sqrt m} u_k \geq \frac 13.$$
Proof. They notice $$u_m = \frac {1+o(1)}{\sqrt {2 \pi m}}.$$ and for $m \leq k \leq m+\sqrt m$ they compute $$\frac {u_{k+1}} {u_k}\geq 1-o(1).$$
So I guess they want to bound $$\sum_{k=m}^{m+\sqrt m} u_k = \frac {1+o(1)}{\sqrt {2 \pi m}} (\sum_{t=0}^{\sqrt m} \prod_{j=0}^{t-1} \frac {u_{m+j+1}}{u_{m+j}})^k$$
Questions
- It seems we can simply argue that since $u_k = \frac {1+o(1)}{\sqrt {2 \pi k}}$, we have $$\sum u_k = \frac {1+o(1)}{\sqrt {2 \pi}} \int_m^{n+\sqrt m} \frac 1{\sqrt x} dx = \frac {1+o(1)}{\sqrt {2 \pi}} \sqrt {(m+\sqrt m) - \sqrt m} = \frac {1+o(1)}{\sqrt {2 \pi}} \frac{\sqrt {(m+\sqrt m) + \sqrt m}}{\sqrt m} \geq \frac {1+o(1)}{\sqrt {2 \pi}} \geq \frac 13.$$
Is this correct? And if so, why does the book use such a technical argument on bounding consecutive quotients?
How does the conclusion follow from the book's calculations?
Where does the integral of $e^{-x^2/2}$ come from in the end of the book's proof? (In the "spoiler" below)
