# Why does $n \choose r$ where $r = 1,n$ track $2^n$?

I bashed together a clunky ruby script to find the sum total of $n \choose r$ where $r = 1,n$

I wanted to determine how many lines of output I could expect from a script that produces all possible combinations of an array. I found that, for any $n$, the sum total $= 2^n$

$ruby nchrsum.rb 6 choose 6 == 1 6 choose 5 == 6 6 choose 4 == 15 6 choose 3 == 20 6 choose 2 == 15 6 choose 1 == 6 6 choose 0 == 1 Total n choose r where n = 6 and r = 1,6: 64  Holds true for all$n$I tried -- but why? • In your array application, consider marking each array element with a 0 for "not taken" or a 1 for "taken". There are two choices for each array element and therefore$2^n$ways to mark the entire array. – Will Orrick Jul 27 '15 at 17:40 •$2^n = (1 + 1)^n = \sum_{i=0}^{n}\binom{n}{i}$– steven gregory Jul 27 '15 at 17:45 ## 3 Answers It's from the Binomial Theorem, expanding$(1+1)^n$• Perfect answer. – David Simmons Jul 27 '15 at 17:35 Another explanation is to observe that, since$\,\dbinom nk$is the number of subsets of$k$elements in a set of$n$elements, the sum of all these coefficients ($n$fixed) is but the number of all subsets of a set of$n$elements – which is known to be$2^n$. • +1, I was just writing this myself. I feel like this explanation doesn't hide the fact that the identity can be obvious. – preferred_anon Jul 27 '15 at 18:05 • @Daniel Littlewood: Technically, the proof with$(1+1)^n$is quite simple. But it doesn't explain, in my opinion, why it is so. – Bernard Jul 27 '15 at 18:08 • @Bernard: They're all explanations, I think; but different explanations can link to the reader's previous knowledge in different ways, which is why having multiple answers to a question can be so useful. – Brian Tung Jul 27 '15 at 23:48 • I totally agree with this point of view. – Bernard Jul 27 '15 at 23:57 One more explanation, given a CS or CS-like background: Consider the set of all$n$-bit numbers, from$0$through$2^n-1$, inclusive; there are thus$2^n$of them, by inspection. (For instance, there are$2^3 = 8$numbers from$0$through$2^3-1 = 7: 0, 1, 2, 3, 4, 5, 6, 7$.) We could, also, count them as follows: How many of the numbers have no$1$bits? We choose none of the$n$bits to be equal to$1$, so the answer is $$\binom{n}{0}$$ How many of them have exactly one$1$bit? We choose one of the$n$bits to be equal to$1$, so the answer is $$\binom{n}{1}$$ How many of them have exactly two$1$bits? We choose two of the$n$bits to be equal to$1\$, so the answer is

$$\binom{n}{2}$$

And so on.

Of course, this way of counting must equal our first answer, so we can combine all of these separate counts to obtain

$$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n} = 2^n$$