Results 1 to 5 of 5

Math Help - Using my assumption when proving by induction

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    20

    Using my assumption when proving by induction

    I had to prove by induction that n - n is divisible by 3.

    What I did was expanded (n + 1) - (n + 1) and simplified it and I got n(n + 1)(n + 2). From my assumption that it is true for all n, I can see that this is also divisible by n and so it has been proved for the (n + 1) term.

    Is that correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    It's a little hard to understand...
    What I did was expanded (n + 1) - (n + 1) and simplified it and I got n(n + 1)(n + 2). From my assumption that it is true for all n, I can see that this is also divisible by n
    What is true for all n? Do you mean that n(n + 1)(n + 2) is divisible by 3 (not n) because one of the factors is a multiple of 3? You are correct, but you have a direct proof rather than a proof by induction because you never use the induction hypothesis. (Coming up with a direct proof is usually more difficult than with a proof by induction.) Indeed, given some n, you have to prove that n - n is divisible by 3. Let k = n - 1. Then n - n = (k + 1) - (k + 1), and then you proceed as before.

    In a proof by induction, you assume that n - n is divisible by 3. Then (n + 1) - (n + 1) = n - n + 3(n^2 + n), which is divisible by 3 using the assumption.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    q
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Here is how you would write the inductive proof:

    Proving n^3 - n is divisible by 3 for natural numbers  n \geq 0

    =================

    Base case:
    0^3 - 0 = 0 is divisible by 3.

    =================

    Induction step:
    Assume n^3 - n is divisible by 3 for some n.
    We need to prove that (n+1)^3 - (n+1) is divisible by 3 given the assumption.

    (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n)
    n^3 - n is divisible by 3 by our assumption.
    3(n^2 + n) is divisible by 3.
    This means the sum is also divisible by 3.

    So we have proved our induction step (n+1)^3 - (n+1) is divisible by 3 (assuming n^3 - n is divisible by 3).

    =================

    With the proofs of the base case and inductive step, we have proved by induction:
    n^3 - n is divisible by 3 for natural numbers  n \geq 0
    Last edited by snowtea; December 28th 2010 at 04:31 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,449
    Thanks
    1864
    Quote Originally Posted by snowtea View Post
    Here is how you would write the inductive proof:

    Proving n^3 - n is divisible by 3 for natural numbers  n \geq 0

    =================

    Base case:
    0^3 - 0 = 0 is divisible by 3.

    =================

    Induction step:
    Assume n^3 - n is true
    is divisible by 3
    for some n.
    We need to prove that (n+1)^3 - (n+1) is true
    is divisible by 3
    given the assumption.

    (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n)
    n^3 - n is divisible by 3 by our assumption.
    3(n^2 + n) is divisible by 3.
    This means the sum is also divisible by 3.

    So we have proved our induction step (n+1)^3 - (n+1) is divisible by 3 (assuming n^3 - n is divisible by 3).

    =================

    With the proofs of the base case and inductive step, we have proved by induction:
    n^3 - n is divisible by 3 for natural numbers  n \geq 0
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving an inequation with induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 9th 2011, 12:17 PM
  2. is this a 'safe' assumption?
    Posted in the Algebra Forum
    Replies: 10
    Last Post: August 19th 2011, 05:25 AM
  3. Confidence intervals and assumption of normality
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 20th 2011, 03:32 AM
  4. Replies: 13
    Last Post: June 1st 2010, 04:52 PM
  5. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 05:50 PM

Search Tags


/mathhelpforum @mathhelpforum