Each binomial coefficient satisfies $(\frac{N}{i})$<sup>i</sup> <= ${N \choose i}$ < $(\frac{eN}{i})$<sup>i</sup>, so if k <= N/2, you can upper bound the sum by $k(\frac{eN}{k})$<sup>k</sup>