Please refer to [this link](http://snap.stanford.edu/class/cs224w-readings/erdos59random.pdf). It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it. 


I'm struggling with equations (16), (17) and (21).


(16)
====


* I'm not sure why they are using those two bounds in the summation? It seems redundant
* Why they did not use the result from (15) in (16) in the summation. They only used (14)?


(17)
----


* Why does $\log\log(n)$ replace $M$ in (17)?


(21)
====


* What does the $(-1)^k$ figure do? Why is it necessary?



Random graphs- Erdos and Renyi 1959 paper
**(16)** They split the sum in (13) for $M<s\leq \frac n 2$ and $\frac n 2 < s < n- \frac {2 N\_c} n$. In the first case they use (14) and, since the terms are positive, they enlarge the sum to $M<s<\infty$. In the second range they use (15) to estimate the sum, then they substitute $s'=n-s$, and then they extend to $\frac {2N\_c}n <s'<\infty$.


The elementary estimates (14) and (15) are not redundant, because they show that the same quantity (the LHS) is estimated differently in case $s\leq \frac n 2$ or $s\geq \frac n 2$. Of course (15) can be proved from (14) by symmetry and vice-versa. This explains why, if you substitute $s'=n-s$ *before* applying (14) and (15), then you need only (14).


**(17)** They replace $M$ with $\log \log n$ because they claimed at the beginning of the proof: "*let $M$ be a large enough number that we will choose later*". That's the moment when they choose it. (16) implies (17).


In more detail, they choose this value $M=\log\log n$, not too big and not too small, because it works conveniently for both $E\_{\log \log n}$ and $\bar E\_{\log \log n}$. Indeed their true objective is to prove that $P(\bar A,n,N\_c)\to 0$, and they split the estimate in two parts. First they show that $P(\bar A\bar E\_{\log \log n},n,N\_c)\leq P(\bar E\_{\log \log n},n,N\_c)\to 0$, and then they show more directly that $P(\bar A E\_{\log \log n},n,N\_c)\to 0$.


**(21)** The formula contains $(-1)^k$ because it is a direct application of the inclusion-exclusion principle. 


They want to count only the graphs without isolated vertices. So first they count ($k=0$) all the possible graphs. Then ($k=1$) they subtract the number of graphs with at least one chosen isolated vertex. Then they add up again the graphs with at least $k=2$ chosen (in $\binom n k$ ways) isolated vertices...


