Results 1 to 10 of 10

Math Help - Divisibility Proofs

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    140

    Divisibility Proofs

    Having a bit of trouble with this one. The final part of my attempt, highlighted in black, is meant to be factored in such a way that it ties into the earlier part of 1. I've tried factoring the final part in different ways, but I just can't get it to match 1. Can anyone help?
    Many thanks.

    Q.
    n(n + 1)(2n + 1) is divisible by 3 for 3 for n \in \mathbb{N}_0.

    Attempt:
    Step 1: For n = 1...
    1(1 + 1)(2(1) + 1) => 1(2)(3) => 6, which can be divided by 3.
    Therefore, n = 1 is true.

    Step 2: For n = k...
    Assume k(k + 1)(2k + 1) can be divided by 3,
    i.e. k(k + 1)(2k + 1) = 3Z, where Z is an integer...1
    Show that n = k + 1 is true...
    i.e. (k + 1)(k + 2)(2(k + 1) + 1) can be divided by 3.
    (k + 1)(k + 2)(2(k + 1) + 1) => (k + 1)(k + 2)(2k + 2 + 1) => (k + 1)(k + 2)(2k + 3) =>

    2k(k + 1)(k + 2) + 3(k + 1)(k + 2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Divisibility Proofs

    Represent (k + 1)(k + 2)(2k + 3) as (k+1)[(k+2)((2k+1)+2)] and multiply through the expression in the square brackets.

    If you don't need to use induction, it is easier to note that 2n ≡ -n (mod 3).

    Also, you are repeating the flaws I pointed out in this thread, namely, saying "n = 1 is true" and "n = k + 1 is true" and using undefined notation =>.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,492
    Thanks
    1393

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    Having a bit of trouble with this one. The final part of my attempt, highlighted in black, is meant to be factored in such a way that it ties into the earlier part of 1. I've tried factoring the final part in different ways, but I just can't get it to match 1. Can anyone help?
    Many thanks.

    Q.
    n(n + 1)(2n + 1) is divisible by 3 for 3 for n \in \mathbb{N}_0.

    Attempt:
    Step 1: For n = 1...
    1(1 + 1)(2(1) + 1) => 1(2)(3) => 6, which can be divided by 3.
    Therefore, n = 1 is true.

    Step 2: For n = k...
    Assume k(k + 1)(2k + 1) can be divided by 3,
    i.e. k(k + 1)(2k + 1) = 3Z, where Z is an integer...1
    Show that n = k + 1 is true...
    i.e. (k + 1)(k + 2)(2(k + 1) + 1) can be divided by 3.
    (k + 1)(k + 2)(2(k + 1) + 1) => (k + 1)(k + 2)(2k + 2 + 1) => (k + 1)(k + 2)(2k + 3) =>

    2k(k + 1)(k + 2) + 3(k + 1)(k + 2)
    You're almost there. Note that since k, k+1 and k+2 are three consecutive numbers, one of them must be a multiple of three, and therefore, so must be their product.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Divisibility Proofs

    Quote Originally Posted by Prove It View Post
    You're almost there. Note that since k, k+1 and k+2 are three consecutive numbers, one of them must be a multiple of three, and therefore, so must be their product.
    If we are allowed to use the fact that the product of three consecutive integers is divisible by 3, then the induction hypothesis, and therefore induction itself, is not necessary. We simply say that for any k,

    k(k + 1)(2k + 1) = k(k + 1)(2(k - 1) + 3) = 2(k - 1)k(k + 1) + 3k(k + 1).

    By the way, is \mathbb{N}_0 the set of natural numbers with 0? Then the base case should be considered for n = 0.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Divisibility Proofs

    If n \equiv 0 (\mod 3) then n is divisible by 3.

    If n \equiv 1 (\mod 3) then 2n+1 is divisible by 3.

    If n \equiv 2 (\mod 3) then n+1 is divisible by 3.


    Each of these three cases yields a factor of n(n+1)(2n+1) that is divisible by 3, so we're done.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Multiplying through the square brackets gives me: (k+1)(2k^2+k+2k+4k+2+4) = (k+1)((2k^2+k)+6k+6) = (k + 1)((k)(2k + 1) + 6k + 6) = 3Z + 6k + 6 which can be divided by 3.
    Have I done this correctly?

    Also, thanks for the alternative solution, Richard. I just want to make sure that I understand both methods of the solution. I'm not ignoring you!
    Last edited by GrigOrig99; July 18th 2012 at 09:56 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    ...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(6) = 3Z+6k^2+6k+6k+6 = 3Z+6k^2+12k+6?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    ...or maybe it's 3Z + (k + 1)(6k) + (k + 1)(6) = 3Z+6k^2+6k+6k+6 = 3Z+6k^2+12k+6?
    Correct. I should have said that in rewriting (k+1)[(k+2)((2k+1)+2)] it is better to keep 2k + 1. Then this equals

    (k + 1)[k(2k + 1) + 2k + 2(2k + 1) + 4] = k(k + 1)(2k + 1) + (k + 1)[6k + 6] = 3Z + 6(k + 1)^2 = 3(Z + 2(k + 1)^2).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Great. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,371
    Thanks
    739

    Re: Divisibility Proofs

    without loss of generality, we may assume that neither n nor n + 1 is divisible by 3 (or else the conclusion is obvious). in this case, n + 2 is divisible by 3.

    but if n + 2 = 3k, then 2n + 1 = 2n + 4 - 3 = 2(n + 2) - 3 = 6k - 3 = 3(2k - 1).

    *****
    inductively, if k(k + 1)(2k + 1) = 3t

    then (k + 1)(k + 2)(2k + 3) = k(k + 2)(2k + 3) + (k + 2)(2k + 3)

    = k(k + 1)(2k + 3) + k(2k + 3) + (k + 2)(2k + 3)

    = k(k + 1)(2k + 1) + 2k(k + 1) + k(2k + 3) + (k + 2)(2k + 3)

    = 3t + 2k2 + 2k + 2k2 + 3k + 2k2 + 7k + 6

    = 3t + 6k2 + 12k + 6

    = 3(t + 2k2 + 4k + 2), and of course (0)(1)(1) = 0 = (3)(0).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: July 16th 2012, 10:17 AM
  2. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: July 7th 2012, 09:22 AM
  3. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: September 26th 2011, 03:51 AM
  4. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2010, 10:47 AM
  5. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2009, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum