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