Each binomial coefficient satisfies $$\left(\frac{N}{i}\right)^i \leq {N \choose i} < \left(\frac{eN}{i}\right)^i,$$ so if $k \leq N/2$, you can upper bound the sum by $k(\frac{eN}{k})^k$
2 of 2
I improved the formatting of the mathematical expressions
Justin Melvin
- 383
- 3
- 8