One proof in Random graph Bela Bollobas about Hamiltonian Cycles

72 Views Asked by At

In Random Graphs 2001 (Bela Bollobas), p. 209, the proof for lemma 8.7, it says that $$\sum_{u=u_0-1}^{u_1}\sum_{w=1}^{\llcorner(\gamma - 1)u\lrcorner}(\log n)^w \Bigl(\frac{e}{u}\Bigr)^u\Bigl(\frac{eu}{w}\Bigr)^wn^{\gamma u^2/n} \leq \sum_{u=u_0-1}^{u_1}\gamma u(\log n)^{(\gamma - 1)u} \Bigl(\frac{e}{u}\Bigr)^ue^{(\gamma -1)u}n^{\gamma u^2/n}.$$ How this can be proved?

Actually, it seems to be equivalent to prove that $\sum_{w=1}^{\llcorner(\gamma - 1)u\lrcorner}(\frac{eu}{w})^w \leq \gamma ue^{(\gamma -1)u}$.

Also, how to prove that the formula following the formula above is $o(1)$ as in the book? Thank you in advance.

The theorem is as follows:

Picture from book