Exercise 4.11: Completion of Proof of Proposition 4.18
(a)
Observe that the sum is equal to the number of subsets of \(n\) balls up to size \(\nu\). If we instead choose with replacement, we need to choose \(\nu\) times out of \(n + 1\) options (no balls is also an option), which gives the upper bound.
(b)
The trick is to use the monotonic limit representation of \(e^{\nu}\) in combination with the binomial theorem: \begin{equation} e^\nu \ge \parens{1 + \frac{\nu}{n}}^n = \sum_{i=1}^n \binom{n}{i}\parens{\frac{\nu}{n}}^i. \end{equation} If \(\nu \le n\), then \begin{equation} e^\nu \ge \sum_{i=1}^\nu \binom{n}{i}\parens{\frac{\nu}{n}}^i \ge \sum_{i=1}^\nu \binom{n}{i}\parens{\frac{\nu}{n}}^\nu \implies \parens{\frac{n}{\nu}}^\nu e^\nu \ge \sum_{i=1}^\nu \binom{n}{i}. \end{equation}