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

Proof by Induction

  1. Sep 18, 2004 #1
    I have to prove, using mathematical induction, that:
    n^3 - n is divisible by 6.
    When n = 1 its true.

    Assuming that k^3 - k is divisible by 6

    (k+1)^3 - (k+1)
    =k^3 + 3k^2 + 2k
    = k^3 - k + 3k^2 + 3k
    k^3 - k is true by induction hypothesis

    but how would i prove that 3k^2 + 3k is divisible by 6? (or did i do this completely wrong?)
     
    Last edited: Sep 18, 2004
  2. jcsd
  3. Sep 18, 2004 #2

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    You're on the right track.
    Since 3k^2+3k=3(k^2+k), all you have to show is that k^2+k is divisible by 2.
     
  4. Sep 18, 2004 #3
    How would I do that?
     
  5. Sep 18, 2004 #4

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you don't really need induction since factoring it makes it obvious. i.e. (n-1)(n)n+1) is a number that is clearly divisible by both 2 and 3, hence also by 6.
     
  6. Sep 18, 2004 #5
    It has to be done using induction.... and im not sure i see how that is clearly divisible by 2 and 3.
     
  7. Sep 18, 2004 #6
    (k^2+k) = k(k+1)
    if k is odd then (k+1) is even
    if k is even then well nothing much left

    -- AI
     
  8. Sep 18, 2004 #7
    Ah, ok, thx alot.
     
  9. Sep 18, 2004 #8

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    every other number is divisible by 2 and every third number is divisible by three so if you have three consecutive numbers then at least one is divisible by two and at least one is divisible by three.

    i know you were supposed to do it by induction, but i enjoy puncturing the balloon of the book that gives a question which is artificial, in the sense that it should really be done more naturally or mroe intelligently another way.

    drill is ok, but it helps i think if you give an induction proof that really requires induction, or is easier by induction.

    for example try proving every integer greater than one is either prime or factors into primes without induction.
     
    Last edited: Sep 18, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by Induction
  1. Proof by Induction (Replies: 2)

Loading...