2
$\begingroup$

Prove the following statement is true: $$\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$$.

Since $\binom{r}{r}=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$, is that to form a basis step? If so, how do I induce k+1 for n+1 and r+1 (where n ≥ r and both positive integers)? At the same time, or in two steps?

$\endgroup$

marked as duplicate by David, Graham Kemp, user147263, Jyrki Lahtonen, Jonas Meyer Nov 21 '14 at 5:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ Assuming you mean $\binom{n}{r}$ it is horribly confusing to use the notation $(n/r)$ which looks like division. $\endgroup$ – Mark Fischler Nov 21 '14 at 4:04
  • $\begingroup$ This equality is unreadable since as Mark points out you are using the exact same notation for combination and division. If you don't know how to use LaTeX, at least write C(n,r) as you have used in the second paragraph. $\endgroup$ – Mario Carneiro Nov 21 '14 at 4:13
  • $\begingroup$ This has been asked at least twice in the last two or three days, 1, 2. $\endgroup$ – David Nov 21 '14 at 4:19
  • $\begingroup$ Sorry, yes it is n above r. I did not use C(n+1,r+1) for the first one because, for the second, I mean to show that I would be using the definition of a combination as my basis step. Is that appropriate in this case? $\endgroup$ – Joey Nov 21 '14 at 4:19
  • $\begingroup$ I did not see these. Maybe it has to do with my division symbols. Thanks David! And thanks everyone else, I will look at these pages for help $\endgroup$ – Joey Nov 21 '14 at 4:21
2
$\begingroup$

You can prove this combinatorially without induction. Hint: consider the $(r+1)$-sets from $\{1, \ldots, n+1\}$, grouped by their largest element.

$\endgroup$
0
$\begingroup$

You prove the theorem for any given $r$ it by induction on $k = n-r$. The basis is $$ \binom{r}{r}=\binom{r+1}{r+1} $$ which is true sine $1=1$. Now assume that $$ \sum_{m=0}^k \binom{r+m}{r} = \binom{r+k+1}{r+1} $$ Then examine $$ \binom{r+k+2}{r+1} - \binom{r+k+1}{r+1}= \frac{r+k+2-(k+1)}{r+1} \binom {r+k+1}{r} $$ as can be seen by writing out the factorials and factoring out the common part. This is in fact $$\frac{r+1}{r+1} \binom {r+k+1}{r} $$ which then shows $$ \sum_{m=0}^k \binom{r+m}{r} +\binom{r+k+1}{r} =\sum_{m=0}^{k+1} \binom{r+m}{r} =\binom{r+m+2}{r+1} $$ establishing induction.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.