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