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