Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
It's a combinatorial proof. Rigorous enough for me, but I know teachers who don't like proofs without lots of algebra. –  Jean-Claude Arbaut Mar 15 '13 at 14:05
2  
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. –  Grumpy Parsnip Mar 15 '13 at 14:09
    
I have edited your question, employing the $\LaTeX$ notation that is used on MSE. –  Andreas Caranti Mar 15 '13 at 14:14
    
Better use the standard $\binom{n}{k}$ notation... –  vonbrand Mar 15 '13 at 14:14
1  
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. –  Brian M. Scott Mar 15 '13 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.

share|improve this answer
    
Richard Stanley (and many other combinatorialists) insist on such proofs, and loathe results proved only by other means... –  vonbrand Mar 15 '13 at 14:16
3  
An instructor who doesn’t accept combinatorial arguments ought not to be teaching the subject. –  Brian M. Scott Mar 15 '13 at 14:44
2  
@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. –  Brian M. Scott Mar 15 '13 at 15:11
2  
@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. –  Brian M. Scott Mar 15 '13 at 15:26
2  
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. –  MJD Mar 15 '13 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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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