Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction

  1. Mar 1, 2010 #1
    1. The problem statement, all variables and given/known data

    [tex] \sum_{i=1}^{n} (i \prod_{j=1}^{i}_{j}) = \prod_{i=1}^{n+1}_{i} - 1 [/tex]

    2. Relevant equations



    3. The attempt at a solution

    First show the base case. That easys just shows it holds for n=1. Not sure where to go from there? What term do I add to both sides? Not really sure what the i means in front of the [tex]\prod [/tex] on the left side
     
  2. jcsd
  3. Mar 1, 2010 #2

    radou

    User Avatar
    Homework Helper

    Assume it holds for some k. Now try to evaluate for k + 1 and use the fact that it holds for k.
     
  4. Mar 1, 2010 #3
    Yes. This requires that I need to add some term to both sides. Not really sure what term I need to use to construct the induction for k+1
     
  5. Mar 1, 2010 #4

    radou

    User Avatar
    Homework Helper

    You have and equality which you wish to show holds for k + 1. Evaluate the left side for k + 1 first - try to express this as a sum of two terms one of which equals the sum for k (which you assumed holds).
     
  6. Mar 1, 2010 #5
    Can you give an example?
     
  7. Mar 1, 2010 #6

    radou

    User Avatar
    Homework Helper

    OK, here's how you should start:

    [tex]
    \sum_{i=1}^{k+1} (i \prod_{j=1}^{i}_{j}) = \sum_{i=1}^{k} (i \prod_{j=1}^{i}_{j}) + (k+1) \prod_{j=1}^{k+1}_{j}
    [/tex]
     
  8. Mar 1, 2010 #7
    Ok so first I replaced all the sum stuff with the right hand side to make it easier to read. By substituting the right side of left side of the initial equality with the right side. That should work fine right?

    The I have:

    [tex]
    \prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
    [/tex]

    But it doesn't seem right..
     
  9. Mar 1, 2010 #8

    radou

    User Avatar
    Homework Helper

    Why wouldn't it seem right? You only need to factor out [tex]\prod_{j=1}^{k+1}_{j}[/tex].
     
  10. Mar 1, 2010 #9
    [tex]
    \prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
    [/tex]


    Ok so I also cancel out the -1 on both sides, then I factor out
    [tex]\prod_{j=1}^{k+1}_{j}[/tex] and I get

    [tex]\prod_{j=1}^{k+1}_{j} = 1 +(k+1)(\prod_{j=1}^{k+1}_{j})[/tex]

    then cancel out the prod_{j=1}^{k+1}_{j} ?

    [tex]
    1 = 1 + (k+1)
    [/tex]

    [tex]
    k=-1
    [/tex]

    What now?
     
  11. Mar 2, 2010 #10

    radou

    User Avatar
    Homework Helper

    You should start thinking about what you're doing. Let's start all over:

    [tex]
    \sum_{i=1}^{k+1} (i \prod_{j=1}^{i}_{j}) = \sum_{i=1}^{k} (i \prod_{j=1}^{i}_{j}) + (k+1) \prod_{j=1}^{k+1}_{j} = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
    [/tex]

    You are not canceling out different sides of the equation, you're only evaluating an equality - now factor out [tex]
    \prod_{j=1}^{k+1}_{j}
    [/tex].
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook