0

Here's the problem stumping me today:

Let $n \in \mathbb{N}$ and $r \in \mathbb{N}$ such that $r \leq n$, and prove using induction that $\binom{n+1}{r+1} = \sum\limits_{i=r}^n \binom{i}{r}$.

I've setup the basics of my inductive proof, but I'm struggling with the induction step.

Could anyone point me in the right direction?

2 Answers2

2

Hint: By Pascal's Identity, we have: $$ \binom{n}{r+1} + \binom{n}{r} = \binom{n+1}{r+1} $$ Note that this is equivalent to: $$ \binom{k+1}{r+1} + \binom{k+1}{r} = \binom{k+2}{r+1} $$

Adriano
  • 41,576
1

When choosing r+1 items from a set of n+1 items either you (a) choose the n+1 item (and choose the remaining r items from the first n) or (b) choose all r+1 items from the first n.

That means we can write C(r+1, n+1) = C(r, n) + C(r+1, n)

By induction (on n) C(r+1, n) = SUM[i = r...n-1] C(r, i). Including the C(r, n) we get the desired result.

Random Excess
  • 1,076
  • Ah! I see now. This was a helpful angle to approach it by. It still took me a while to see, and I don't think I would've been able to have ever come up with something like that myself...any suggestions as to how to see this kind of pattern in the future? –  Oct 08 '14 at 02:28