Prove sum of combinations

Question

Let n and r be positive integers with n ≥ r. Prove that C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1)

I would like to approach with mathematical induction. However, I don't understand what to do with the "r". The questions I've answered before have only had the n (which would be substituted for 1 in the basis step, and by k and k + 1 in the inductive hypothesis step) so the expressions could be solved.

For example the basis step P(1), 1 = C(1 + 1, r + 1). How can I proceed?

Answer 1

Prove $\forall n: (n>r)\to P(n)$ for the premise: $P(n) \mathop{:=} \sum_{k=r}^{n} {^{k}C_r} = {^{n+1}C_{r+1}}$

The base case is $P(r)$. $\quad\sum_{k=r}^r {^kC_r} = {^rC_r} = {^{r+1}C_{r+1}}$

The induction step: is $$\begin{align} \sum_{k=r}^{n+1} {^kC_r} & = {^{n+1}C_r} + \sum_{k=r}^n {^kC_r} \\ & ={^{n+1}C_r} + {^{n+1}C_{r+1}} & \impliedby P(n), \text{assumed} \\ & = \frac{(n+1)!}{r!(n+1-r)!}+\frac{(n+1)!}{(r+1)!(n-r)!} \\ & = \frac{(n+1)! ((r+1)+(n+1-r))}{(r+1)!(n+1-r)!} \\ & = \frac{(n+1)!(n+2)}{(r+1)!(n+2-(r+1))!} \\ & = {^{n+2}C_{r+2}} \\[4ex] \therefore P(n) & \implies P(n+1) \end{align}$$

Thus $P(r) \wedge [P(n)\to P(n+1)] \vdash \forall n: (n\geq r) \to P(n)$

Hence we have $\forall n: (n\geq r) \to \sum_{k=r}^n {^kC_r} = {^{n+1}C_{r+1}}$

Answer 2

It can be proved by induction.

When $n=r$, it holds. Suppose that $n=k$, it also holds. Now let $n=k+1$,

$$C_r^r + C_{r+1}^r + \cdots + C_{k+1}^r+ C_{k+2}^r=C_{k+1}^{r+1}+C_{k+2}^{r}=C_{k+2}^{r+1}$$