Results 1 to 12 of 12

Math Help - Induction - Divisibility

  1. #1
    Junior Member
    Joined
    Nov 2011
    From
    Karachi
    Posts
    36

    Induction - Divisibility

    We have to prove that n(n^2+5) is divisible by 6. How do we go about it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Induction - Divisibility

    Quote Originally Posted by cosmonavt View Post
    We have to prove that n(n^2+5) is divisible by 6. How do we go about it?
    Do it for the base case: n=1.

    Suppose that it is true for n=k then look at the expansion of (k+1)((k+1)^2+5)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,082
    Thanks
    66

    Re: Induction - Divisibility

    Quote Originally Posted by cosmonavt View Post
    We have to prove that n(n^2+5) is divisible by 6. How do we go about it?
    n^3 + 5n - 6k = 0 where k is any integer

    n = m - 5/(3m)
    where:
    m = {[SQRT(243k^2 + 125)] / 3^(3/2) + 3k}^(1/3)

    Thassa hint?!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Induction - Divisibility

    To use induction, as mentioned, we first check the base case P_1:

    1\left(1^2+5\right)=1(6)=6(1) true. So we state our induction hypothesis P_n:

    n\left(n^2+5\right)=6k_n where k_n\in\mathbb Z

    Then we would like to add some expression f(n) to each side such that:

    n\left(n^2+5\right)+f(n)=(n+1)\left((n+1)^2+5 \right)
    Last edited by MarkFL; December 24th 2011 at 10:53 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Quacky's Avatar
    Joined
    Nov 2009
    From
    Windsor, South-East England
    Posts
    901

    Re: Induction - Divisibility

    Quote Originally Posted by MarkFL2 View Post
    To use induction, as mentioned, we first check the base case P_1:

    ...etc...

    Thus, we have derived P_{n+1} from P_n thereby completing the proof by induction.
    ...Which the OP would have been able to try themselves had they followed Plato's advice, which was rendered obsolete by your full solution.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Induction - Divisibility

    there is another proof, which does not use induction (there is always more than one way to skin a cat, although a skinning knife is recommended).

    suppose n is odd. then n = 2k+1. so n^2 = (2k+1)(2k+1) = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, so n^2 is odd.

    then, n^2 + 5 is even, so n(n^2 + 5) is even.

    on the other hand, if n is even, then so is n(n^2 + 5). so in all cases (n even or odd), n(n^2 + 5) is even. so 2 divides n(n^2 + 5).

    now if 3 divides n, then both 2 and 3 divide n(n^2 + 5), so 6 must divide n(n^2 + 5), since 2 and 3 are relatively prime.

    but...3 may not divide n. there are two ways this could happen:

    n = 3k - 1, or n = 3k + 1. we will look at each, in turn.

    if n = 3k - 1, then n(n^2 + 5) = (3k - 1)((3k - 1)^2 + 5) = (3k - 1)(9k^2 - 6k + 1 + 5)

    = (3k - 1)(9k^2 - 6k + 6) = 3[(3k - 1)(3k^2 - 2k + 2)], so in this case, as well, 3 divides n(n^2 + 5).

    if n = 3k + 1, then n(n^2 + 5) = (3k + 1)((3k + 1)^2 + 5) = (3k + 1)(9k^2 + 6k + 1 + 5)

    = (3k + 1)(9k^2 + 6k + 6) = 3[(3k + 1)(3k^2 + 2k + 2)], which is certainly divisible by 3.

    so, in all cases (no matter if n is even, or odd, a multiple of 3, one less than a multiple of 3, or 1 more than a multiple of 3),

    n(n^2 + 5) is divisible by both 2 and 3, and so is divisible by 6.

    (the astute reader will notice that the above proof can be simplified greatly using modular arithmetic).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Induction - Divisibility

    We know that the multaplication of every 3 consecutive numbers is divisible by 6.

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

    Now, n(n^2+5)=n^3+5n

    Hence, n^3+5n=n^3+3n^2+2n-(3n^2+3n)=(n^3+3n^2+2n)-3n(n+1)

    And 3n(n+1) is divisible by 6.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Induction - Divisibility

    Just for fun, we could begin with the non-homogeneous recurrence:

    (1) S_{n+1}=S_{n}+\frac{n(n+1)}{2}+1 where S_0=0

    (2) S_{n+2}=S_{n+1}+\frac{(n+1)(n+2)}{2}+1

    Subtracting (1) from (2) yields:

    (3) S_{n+2}=2S_{n+1}-S_{n}+n+1

    (4) S_{n+3}=2S_{n+2}-S_{n+1}+(n+1)+1

    Subtracting (3) from (4) yields:

    (5) S_{n+3}=3S_{n+2}-3S_{n+1}+S_{n}+1

    (6) S_{n+4}=3S_{n+3}-3S_{n+2}+S_{n+1}+1

    Subtracting (5) from (6) yields:

    S_{n+4}=4S_{n+3}-6S_{n+2}+4S_{n+1}-S_{n}

    Now we have a homogeneous recurrence whose associated characteristic equation is:

    r^4-4r^3+6r^2-4r+1=0

    (r-1)^4=0

    We have the root r = 1 of multiplcity 4, thus, the closed-form for S_n will take the form:

    S_n=k_1+k_2n+k_3n^2+k_4n^3

    S_0=0\:\therefore\:k_1=0

    Computing:

    S_1=1

    S_2=3

    S_3=7

    We now have the 3X3 system:

    k_2+k_3+k_4=1

    2k_2+4k_3+8k_4=3

    3k_2+9k_3+27k_4=7

    and we find:

    k_2=\frac{5}{6}

    k_3=0

    k_4=\frac{1}{6}

    Therefore, we have:

    S_n=\frac{5n}{6}+\frac{n^3}{6}=\frac{n\left(n^2+5 \right)}{6}

    Thus:

    n\left(n^2+5\right)=6S_n

    From (1), noting that the product of two consecutive integers is always even, we know S_n is an integer.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Induction - Divisibility

    so far, i count 4 ways to skin this cat. outstanding!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,082
    Thanks
    66

    Re: Induction - Divisibility

    https://oeis.org/

    enter sequence# A004006
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Induction - Divisibility

    In a method very similar to that of Also sprach Zarathustra, we know:

    (n-1)n(n+1) is divisible by 6, and so must:

    (n-1)n(n+1)+6n be divisible by 6.

    (n-1)n(n+1)+6n=n\left(n^2-1\right)+6n=n\left(n^2-1+6\right)=n\left(n^2+5\right)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,404
    Thanks
    1293

    Re: Induction - Divisibility

    Quote Originally Posted by MarkFL2 View Post
    In a method very similar to that of Also sprach Zarathustra, we know:

    (n-1)n(n+1) is divisible by 6, and so must:

    (n-1)n(n+1)+6n be divisible by 6.

    (n-1)n(n+1)+6n=n\left(n^2-1\right)+6n=n\left(n^2-1+6\right)=n\left(n^2+5\right)
    I like this one best, it's so clear and simple
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility by 6 Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2011, 03:40 PM
  2. Induction divisibility P1
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2010, 10:20 AM
  3. Induction divisibility P2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2010, 09:22 AM
  4. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 11:12 AM
  5. Induction with divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 28th 2008, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum