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

Induction Question

  1. Oct 30, 2007 #1
    Hi all, been struggling with my course material regarding Induction. My prof is really not great at explaining this proof method. I don't know what the learning curve or expectations here are like but I'm really struggling with this conceptually.

    Any assistance with these problems would be much appreciated:

    1. Prove that 3 divides n^3+2n whenever n is a positive integer.
    I know I can't use a summation progression so how do I solve this induction?
    (n+1)^3+2(n+1) is the next step but I get lost when I try to factor out the (n+1)^3
    This is as far as I can take this one.

    2. Prove that 1x1! + 2x2! + ... + nxn! = (n+1)!-1
    Let P(n) be 1x1!+…+nxn!=(n+1)!-1
    Basis Step: 1 x 1! = (1+1)!+1
    1 = 1
    Therefore our basis step is true.
    Inductive Step: We know that P(n) is true thus we must prove P(n+1)
    1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!)
    1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)(n+1)!)
    1x1!+…+nxn!+((n+1)(n+1)!)= ((n+1)(n+1)!)

    I believe this one is solved however I'm not sure if I must take it further?
    Last edited: Oct 31, 2007
  2. jcsd
  3. Oct 31, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    1. Why are you factoring out (n+1)^3? You can't.

    The philosophy of induction is to relate one statement to previous ones.

    So, given (n+1)^3 + 2(n+1) and n^3+2n, what have you tried to do with both?
  4. Oct 31, 2007 #3
    Tried to divide both by 3 in order to redue the formula to a positive integer. Yet I still don't understand how to write or show this?
  5. Oct 31, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Divide both sides of what by 3?

    Do the only possible thing that you can do. Expand (n+1)^3+2(n+1). Then think.
  6. Oct 31, 2007 #5
    Ok I think I got it, the expansion is a little messy but here goes :
    Prove that 3|n^3+2n whenever n is a positive integer.
    Basis Step: 1^3+2(1)/3 = 3/3 = 1 then we know that the first step in the formula is true.
    Inductive Step: 3|(n+1)^3+2(n+1) If both terms are multiples of 3 then they are divisible by 3 so:
    3|(n+1)^3+2(n+1)- (n^3+2n)

    Insert back into equation
    Subtract Original formula
    n^3+2n^2+4n+3 - (n^3+2n)

    Since the values are multiples of 3 the formula is divisible by 3 thus 3|(n+1)^3+2(n+1) is true.

    Last edited: Oct 31, 2007
  7. Oct 31, 2007 #6
    You made a mistake, by the binominal formula: (K+1)^3 = K^3 +3K^2+3K+1. (It is always true that if the power is a prime, (a+b)^p = a^p+b^p +p(middle terms).

    We start with Basis: let n=1, 1^3+2(1) = 3.

    If true for K, (K+1)^3 +2(K+1) = [k^3+2K] +3K^2+3K+1 +2 . The first part is divisible by 3 by the induction hypothesis and the second is 3K^2+3K+3, all terms divisible.
    Last edited: Oct 31, 2007
  8. Nov 1, 2007 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    As robert says, you don't have the correct binomial expansion. Plus you also write something that implies you think 2n^2=(2n)(2n)=4n which is also not true in two different ways.
  9. Nov 3, 2007 #8


    User Avatar
    Science Advisor

    I got a bad feeling whn you declared "My prof is really not great at explaining this proof method." Now I see I was right. Your problem is not induction-your prof seems to have taught you that well. Your problem is algebra:
    No, (n+1)^2= n^2+ 2n + 1, not n^2+ 1
    should be n^3+ 2n^2+ n+ n^2+ 2n+1 and you get n^3+ 3n^2+ 3n+ 1.

    But far, far worse!
    A thousand lashes with a wet noodle! 2n^2 is NOT(2n)(2n), that would be 4n^2. But anyway, (2n)(2n) is NOT 4n! You took the square off the n and put it on the 2- that's not cricket.
    Last edited by a moderator: Nov 3, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook