Mathematical induction with the binomial formula

[liorda]

Homework Statement

prove, using mathematical induction, that the next equation holds for all positive t.
$$\sum_{k=0}^n \dbinom{k+t}{k} = \dbinom{t+n+1}{n}$$

Homework Equations

$$\dbinom{n}{k} = {{n!} \over {k!(n-k)!}$$

The Attempt at a Solution

checked that the base is correct (for t=0, and even for t=1), and made the induction assumption, by replacing t with p.

the next step, replacing t with p+1 holds me back:

I need to prove the next statement: $$\sum_{k=0}^{n} \dbinom{k+p+1}{k} = \dbinom{n+p+2}{n}$$

LHS: $$\sum_{k=0}^n \dbinom{k+p+1}{k} = \sum_{k=0}^n \left[ \dbinom{k+p}{k} \left(k \over {p+1} +1 \right) \right] = {{1} \over {p+1}} \sum_{k=0}^n \left[ \dbinom{k+p}{k} k \right] + \dbinom{n+p+1}{n}$$

RHS: $$\sum_{k=0}^n {{(k+p+1)!}\over{k!(p+1)!}} = \sum_{k=0}^n {{(k+p)!(k+p+1)}\over{k!p!(p+1)}} = \sum_{k=0}^n \dbinom{k+p}{k} + \sum_{k=0}^n \dbinom{k+p}{k} {{k}\over{p+1}}$$

where can I go from here?

 

[CompuChip]

You are already done.
In the final expression you gave for the RHS,
$$\sum_{k=0}^n \dbinom{k+p}{k} + \sum_{k=0}^n \dbinom{k+p}{k} {{k}\over{p+1}}$$
apply the induction hypothesis and you'll see that both sides are equal/