• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Mathematical induction with the binomial formula

  • Thread starter liorda
  • Start date
28
0
1. 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]

2. Homework Equations
[tex]\dbinom{n}{k} = {{n!} \over {k!(n-k)!}[/tex]


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: [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:

CompuChip

Science Advisor
Homework Helper
4,284
47
You are already done.
In the final expression you gave for the RHS,
[tex] \sum_{k=0}^n \dbinom{k+p}{k} + \sum_{k=0}^n \dbinom{k+p}{k} {{k}\over{p+1}}
[/tex]
apply the induction hypothesis and you'll see that both sides are equal/
 

Related Threads for: Mathematical induction with the binomial formula

Replies
7
Views
2K
  • Posted
Replies
1
Views
898
Replies
5
Views
2K
Replies
1
Views
5K
  • Posted
Replies
3
Views
3K

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
Top