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?
Answer
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.
No comments:
Post a Comment