# An expression for the number of n-bit binary strings with at most k ones (without summations)

Say we need to find an expression for the number of binary strings of length $n$, which have at most $k$ ones. My solution was to split the problem into $k+1$ cases, where the number of ones, $m=0,1,2,...,k$, and sum the values together.

For example, to find the number of solutions in which at most $3$ ones occur in a $6$ bit string, we compute $\binom{6}{0}+\binom{6}{1}+\binom{6}{2}+\binom{6}{3}=1+6+15+20=42$. More generally,

$$N=\sum_{m=0}^{k}\binom{n}{m}$$

This is pretty nice, but I'd like to find a nicer expression which doesn't involve a summation, if such a thing exists. Any suggestions?

• There is no such summation, I remebered reading it in a book called A course in enumeration by Marting Aigner. It says it doesn't exist and it says why, but I'm too much of a noob to understand it. It's in chapter \$4 which is called hypergeometric series. – Jorge Fernández Hidalgo Jan 6 '15 at 22:15