Let C(n,k) be the binomial coefficient "n choose k". We want to bound the sum of these, with k ranging from 0 to d. This is equivalent to bounding the volume of the n-dimensional Hamming ball of radius d. Denote this number by B(n,d).
A well-known bound (appearing, for example, in the Sauer-Shelah-VC lemma) is
B(n,d) <= (en/d)^d .
We are pretty sure that it can be sharpened, for example by writing a (1/2) in front of the RHS. (We actually think it can be sharpened by better than a constant.)
Thus has to be known. Anyone have a reference? Thanks in advance!