# Mathematical induction with the binomial formula

#### liorda

1. 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}$$

2. Homework Equations
$$\dbinom{n}{k} = {{n!} \over {k!(n-k)!}$$

3. 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?

Last edited:
Related Calculus and Beyond Homework Help News on Phys.org

#### CompuChip

Science Advisor
Homework Helper
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/

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving