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.

$$\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$$

How can I prove using induction for all values of $n$ and $c$? I have no idea how to start it. Please help!

share|improve this question
    
You can use \binom{n}{c} to typeset $\binom{n}{c}$. –  Arturo Magidin Sep 16 '11 at 3:38
3  
This hasn't been done before on MSE? –  The Chaz 2.0 Sep 16 '11 at 3:42
5  
Do you need to use induction? There's a very simple counting argument to prove it... –  Arturo Magidin Sep 16 '11 at 3:42
1  
If your binomial coefficient $\binom{n}{c}$ is defined combinatorially then the easiest way to prove this is by counting. If $\binom{n}{c}$ is defined as $\frac{n!}{c!(n-c)!}$ then in fact it's just a few lines of algebra, using the identity $n! = n (n-1)!$ several times. Induction really is overkill here. (Note: this is an early problem in Spivak's calculus, and I am currently teaching a course out of this text, so I am at this moment as sure about this as I will ever be!) –  Pete L. Clark Sep 16 '11 at 3:46
    
@Pete I cannot think of any way to apply induction here. So even if it's overkill, can you suggest a way? :) –  Srivatsan Sep 16 '11 at 3:48

2 Answers 2

HINT:

Double Induction!

Fix n, and show true for c (one can say it's true for all c, noting that for c 'too large' the equation reads $0 + 0 = 0$). Then fix c, and show true for n. So it's like two induction proofs, and it is way overkill for this problem.

share|improve this answer
    
What should I choose for n and c? :( –  David Taeyang Lee Sep 16 '11 at 4:14
    
I'm so confused now.. Could you explain it more? –  David Taeyang Lee Sep 16 '11 at 4:15

$\dbinom{n}{c}$ is the number of size-$c$ subsets of a size-$n$ set $S$. Suppose you have a list of all of them. Also make a list of all size-$(c+1)$ subsets of your size-$n$ set: there are $\dbinom{n}{c+1}$ of them. Now let $x$ be something that is not a member of $S$, so that $S\cup\{x\}$ is a size-$(n+1)$ set. To each size-$c$ subset in the first list, add $x$ as a new member, getting a size-$(c+1)$ subset, not of the original size-$n$ set, but of the larger set $S\cup\{x\}$. You now have two lists:

  • One list of size-$(c+1)$ subsets of $S\cup \{x\}$, each having $x$ as a member. There are $\dbinom{n}{c}$ of these.
  • One list of size-$(c+1)$ subsets of $S\cup\{x\}$, each not having $x$ as a member. There are $\dbinom{n}{c+1}$ of these.

The union of those two lists contains $\dbinom{n}{c}+\dbinom{n}{c+1}$ members. But the union of those two lists is also a list of all size-$(c+1)$ subsets of the size-$(n+1)$ set $S\cup\{x\}$. Therefore $\dbinom{n}{c}+\dbinom{n}{c+1}=\dbinom{n+1}{c+1}$.

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.