1. Not finding help here? Sign up for a free 30min 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

    CompuChip

    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}}
    [/tex]
    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 Discussions: Mathematical induction with the binomial formula
  1. Mathematical Induction (Replies: 6)

  2. Mathematical Induction (Replies: 5)

  3. Mathematical induction (Replies: 8)

  4. Mathematical Induction (Replies: 11)

Loading...