# How to prove the binomial coefficient identity $\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$ by induction?

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

-
You can use \binom{n}{c} to typeset $\binom{n}{c}$. – Arturo Magidin Sep 16 '11 at 3:38
This hasn't been done before on MSE? – The Chaz 2.0 Sep 16 '11 at 3:42
Do you need to use induction? There's a very simple counting argument to prove it... – Arturo Magidin Sep 16 '11 at 3:42
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

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.

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

-