2
$\begingroup$

$$\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!

  • 0
    You can use `\binom{n}{c}` to typeset $\binom{n}{c}$.2011-09-16
  • 3
    This hasn't been done before on MSE?2011-09-16
  • 5
    Do you need to use induction? There's a very simple counting argument to prove it...2011-09-16
  • 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!)2011-09-16
  • 0
    @Pete I cannot think of *any* way to apply induction here. So even if it's overkill, can you suggest a way? :)2011-09-16
  • 0
    @Srivatsan: well, anything that you can prove without using induction you can also prove by induction if you insist...But no, I don't see how using induction gains you anything at all here. (This problem appears in the chapter on induction in Spivak's text, so a lot of students seem to think that it should be proved by induction. But actually this is only the first part of a multi-part problem. For instance, knowing this one can prove *by induction* that the binomial coefficients are always non-negative integers...)2011-09-16
  • 0
    @The Chaz: It [has](http://math.stackexchange.com/questions/20475/proving-n-choose-r-n-1-choose-r-1n-1-choose-r-when-1-leq-r), although induction wasn't specifically requested.2011-09-16

2 Answers 2

1

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.

  • 0
    What should I choose for n and c? :(2011-09-16
  • 0
    I'm so confused now.. Could you explain it more?2011-09-16
1

$\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}$.