- #1
liorda
- 28
- 0
Homework Statement
prove, using mathematical induction, that the next equation holds for all positive t.
[tex]\sum_{k=0}^n \dbinom{k+t}{k} = \dbinom{t+n+1}{n}[/tex]
Homework Equations
[tex]\dbinom{n}{k} = {{n!} \over {k!(n-k)!}[/tex]
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: [tex]\sum_{k=0}^{n} \dbinom{k+p+1}{k} = \dbinom{n+p+2}{n}[/tex]
LHS: [tex]\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}[/tex]
RHS: [tex]\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}}[/tex]
where can I go from here?
Last edited: