# How many distinct binary strings have Hamming distance at most $k$?

Given a binary string of length $$n$$, how many distinct binary strings have Hamming distance at most $$k$$ from it?

There are $${n \choose k}$$ sets of $$k$$ locations to flip a bit but many of those overlap. Is there a simple closed form for the value I am looking for?

You would have to count every bitstring that has edit distance $$x$$ from your original bitstring $$b$$ for all $$x \leq k$$. So the sum you're looking for is $$S = \sum_{x=0}^k {n \choose x}$$ which has no closed-form expression in general, unfortunately.