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

Proof Question: Mathematical Induction

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

    Use mathematical induction to prove, for all integers [itex]n >= 1[/itex]

    [itex]n^3 - n[/itex] is divisible by 3

    2. Relevant equations

    Found equations with addition but no subtract involved.

    3. The attempt at a solution

    Another question suggests you expand the brackets, then insert the original theorem which prooves that the whole statement is true? (divisible by 3)
     
  2. jcsd
  3. Mar 22, 2008 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I don't know what you mean by
    but that is indeed how induction works.

    So, first you need to show that it is true for n = 1 (or if you want, for the slightly less trivial case n = 2). Then you assume you have proven that [itex]n^3 - n[/itex] is divisible by 3, and you try to show that [itex](n + 1)^3 - (n + 1)[/itex] is divisible by 3 as well.
    Then usually one stops writing down the proof, but the reasoning is: it has been shown that if it is true for n = 1, it will be true for n = 2. Also, it has been shown that if it is true for n = 2, it will be true for n = 3; et cetera. We have shown explicitly that it holds for n = 1. Therefore, it is true for n = 2, hence for n = 3, et cetera.

    So first, check the statement for some low numbers (in principle, n = 1 would suffice, but you can check it for 2 and 3 if you want). Then assume it is true for n ("induction hypothesis") and try to prove it for n + 1. This can indeed by done by working out the brackets and trying to get [itex]n^3 - n[/itex] which is divisible by 3 by the induction hypothesis, plus something of which you can easily show that it is divisible by 3.
     
  4. Mar 22, 2008 #3
    Yeah, i did the sum for 1 to 3 and they were all divisible by 3.


    I did attempt to break down [itex](n + 1)^3 - (n + 1)[/itex] but wasnt sure how.


    Is that the lowest form it can be displayed it?

    Would i expand the brackets to (n+1)(n+1)(n+1) - (n - 1)

    = n^3 - n - 1 +1

    = n^3 - n
     
  5. Mar 22, 2008 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    OK.

    Not quite. First of all, you want to expand
    [tex](n + 1)^3 - (n \operatorname{\color{red}+} 1) = (n + 1)(n + 1)(n + 1) - n - 1[/tex]
    (note the sign in the first part, and the absence of brackets in the second part: ... - (n - 1) = ... - n + 1 is something different).
    Then, you made an error in the expansion of the cubic:
    [tex](n + 1)^3 = (n + 1)(n + 1)(n + 1) = (n + 1)(n^2 + 2n + 1) = \cdots [/tex]
     
  6. Mar 22, 2008 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi Lococard! Welcome to PF! :smile:

    You must learn these expansions:

    (n+1)(n+1) = n^2 + 2n + 1

    (n+1)(n+1)(n+1) = n^3 + 3n^2 + 3n + 1

    (n+1)(n+1)(n+1)(n+1) = n^4 + 4n^3 + 6n^2 + 4n + 1​

    So (n + 1)^3 - (n + 1) = ? :smile:
     
  7. Mar 24, 2008 #6
    n^3 + 3n^2 + 3n + 1 - (n + 1)?

    How can i make this any smaller?
     
  8. Mar 24, 2008 #7

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Regroup as follows
    [tex]n^3 + 3n^2 + 3n + 1 - (n + 1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + (3n^2 + 3n + 1 - 1)[/tex]
    and use the induction hypothesis.

    (You want to show that this is divisible by 3. What condition for a and b is sufficient to let a + b be divisible by 3?)
     
  9. Mar 24, 2008 #8
    That n is being multiplied by 3 on the RHS.


    Do i have to have the +1 - 1?

    Or can i just leave it as (n^3-n)+(3n^2+3n)?
     
  10. Mar 24, 2008 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Lococard! :smile:

    This is proof by induction. So you can assume that n^3 - n is divisible by 3.

    So … ? :smile:

    oh, and yes, definitely add the +1 and -1 to get 0.
     
  11. Mar 24, 2008 #10
    So assuming that n^3-n is divisible by 3.

    (n^3-n)+(3n^2+3n)

    Knowing the first part is divisible by 3, the second part is divisible by 3 because n is being multiplied by 3, resulting in a number divisible by 3.


    Solved?
     
  12. Mar 24, 2008 #11

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Yep, now all you have to do is write it out readably :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof Question: Mathematical Induction
Loading...