1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction with the binomial formula

  1. Mar 22, 2009 #1
    1. The problem statement, all variables and given/known data
    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. Relevant 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: Mar 22, 2009
  2. jcsd
  3. Mar 22, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    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}}
    apply the induction hypothesis and you'll see that both sides are equal/
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Mathematical induction binomial Date
Induction Proof Jan 16, 2015
Solve this mathematical induction Aug 27, 2014
Mathematical induction ''all horses are the same color'' Aug 12, 2014
Mathematical Induction Jul 11, 2014
Mathematical induction inequality Sep 20, 2013