Okay I have been thinking about this common combinatorial identity. $$\sum_{r=0}^{n} \binom{n}{r} = 2^n.$$ It is simple to prove this by induction, but it requires some annoying algebraic manipulation which involves other combinatorial identities. What about if we took an approach that takes into factor a specific rephrase of the problem?

My approach is this. Consider a combination lock with n number of on-off switches. To open it require turning on the correct switches. How many combinations are there? clearly, the first switch can be on or off, second on and off etc. so the combintions are $2^n$

We look at it from a different angle. How many ways are there to pick one on switch. $\dbinom{n}{1}$. what about picking 2 switches? $\dbinom{n}{2}$... and so on. Since the number of combinations are supposed to be the same,it gives us the identity.

Now i know this explanation is not rigorous, but can someone point out exactly to me exactly which part of it it fails to be so?

I have also encountered this problem in man other areas of mathematics when I try to prove something, I used a specific problem to do so and thus I doubt the validity of the proof. I can give more examples if needed

  • 6
    $\begingroup$ It's a combinatorial proof. Rigorous enough for me, but I know teachers who don't like proofs without lots of algebra. $\endgroup$ Mar 15, 2013 at 14:05
  • 3
    $\begingroup$ Very clever proof. To me it is the right proof. Rigor is an ambiguous concept, but it's certainly not the case that a rigorous proof of an identity needs be done algebraically. Your argument explains why the identity is true. The algebra does not give any insight. $\endgroup$ Mar 15, 2013 at 14:09
  • $\begingroup$ I have edited your question, employing the $\LaTeX$ notation that is used on MSE. $\endgroup$ Mar 15, 2013 at 14:14
  • $\begingroup$ Better use the standard $\binom{n}{k}$ notation... $\endgroup$
    – vonbrand
    Mar 15, 2013 at 14:14
  • 1
    $\begingroup$ It’s a variant of the standard combinatorial proof: $2^n$ is the number of subsets of $[n]=\{1,\dots,n\}$, and $\binom{n}k$ is the number of subsets of $[n]$ of size $k$, so $2^n=\sum_k\binom{n}k$. As such it is, as others have said, just fine. And while one ought to be able to carry out the details of the proof by induction, combinatorial arguments like this one generally give much more insight into why the result is true. $\endgroup$ Mar 15, 2013 at 14:46

2 Answers 2


Your approach is an often-used (and perfectly valid) proof technique. You should be aware that some instructors don't like it, but it certainly does the job.

  • 5
    $\begingroup$ An instructor who doesn’t accept combinatorial arguments ought not to be teaching the subject. $\endgroup$ Mar 15, 2013 at 14:44
  • 1
    $\begingroup$ @Brian M. Scott: surely it depends on whether the goal is to teach the identity, or whether it is to teach students how to write proofs by induction. I would usually take a car if I need to travel 10 miles, but not if the point is to train for a marathon. $\endgroup$ Mar 15, 2013 at 15:09
  • 3
    $\begingroup$ @Carl: If the goal is to teach students how to write proofs by induction, the instructor should damned well come up with problems for which induction is the best approach. And if even then a student comes up with a different approach, the instructor should be pleased. $\endgroup$ Mar 15, 2013 at 15:11
  • 3
    $\begingroup$ @Carl: My point is that the directions should not begin so. I consider it a failure on the part of the instructor if he or she has to specify a technique in order to give students practice in applying it. $\endgroup$ Mar 15, 2013 at 15:26
  • 4
    $\begingroup$ I strongly agree with Brian here. Questions that prescribe techniques are either lazy pedagogy or bad curriculum design. If technique $Z$—say, induction—is a useful technique, then it is because there is some problem $Y$ such that $Z$ is superior to all other techniques for solving $Y$. If all such $Y$ are outside the scope of the class, then $Z$ is outside the scope of the class too. If, on the other hand, there is some $Y$ that is in the scope of the class, it is the instructor's job to find it and present it to the students, as an instructive example. $\endgroup$
    – MJD
    Mar 15, 2013 at 15:31

You can make such an argument rigorous. When things start to get more sophisticated, it often helps immensely to give more detail than one usually sees in this style of proof.

Let $S$ be a set with $n$ elements. Let $P(S)$ be its powerset -- that is, the set of all subsets of $S$. Let $P_i(S)$ be the set of all subsets of $S$ with exactly $i$ elements.

Your proof is then the invocation of four facts:

  • The well-known formula for the number of elements in $P(S)$
  • The well-known formula for the number of elements in $P_i(S)$
  • The observation that $P(S)$ is the disjoint union of all of the $P_i(S)$
  • The relationship between the number of elements in a sequence of sets and the number of elements in their disjoint union

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.