Results 1 to 8 of 8

Math Help - Proof by induction.

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    21

    Proof by induction.

    I have a question:
    Prove that n^{5}-n is divisible by 10 for all n\ge2 .

    Since my current chapter is on induction, I figure it has something to do with induction, I don't really know. But all the induction I've learned in this chapter looks something like
    2,6,12...n(n+1) = \frac{n(n+1)(n+2)}{3} etc..

    Any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,621
    Thanks
    426
    Quote Originally Posted by spycrab View Post
    I have a question:
    Prove that n^{5}-n is divisible by 10 for all n\ge2 .

    Since my current chapter is on induction, I figure it has something to do with induction, I don't really know. But all the induction I've learned in this chapter looks something like
    2,6,12...n(n+1) = \frac{n(n+1)(n+2)}{3} etc..

    Any help?
    follow the procedure for proof by induction.

    1. show the statement is true for n = 2

    2. assuming the statement is true for n, show that the statement is true for n+1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    Posts
    21
    Yes, I know that, but what I'm trying to say is how do you show that it is divisible by 10
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,621
    Thanks
    426
    someone may offer a shorter solution, but here's the way I did it ...


    2^5 - 2 = 30 = 3 \cdot 10 ... true for n = 2

    (n+1)^5 - (n+1) =

    n^5 + 5n^4 + 10n^3 + 10n^2  + 5n + 1 - n - 1 =

    n^5 - n + 5n^4 + 10n^3 + 10n^2  + 5n =

    (n^5 - n) + 10(n^3 + n^2) + 5n(n^3 + 1)

    since the statement is true for n, then n^5 - n can be written in the form 10k, where k is an integral value ...

    10k + 10(n^3 + n^2) + 5n(n^3 + 1)

    the first term is a multiple of 10, as is the second term.

    for the 3rd term, 5n(n^3 + 1) ...

    if n is even, then 5n is a multiple of 10.

    if n is odd, then n^3 + 1 is even, making the 3rd term also a multiple of 10.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2010
    Posts
    21
    thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Yes, skeeter's method is exactly how I did it also.
    I would word it slightly differently, but that is just my way!

    P(k)

    k^5-k is divisible by 10 ?


    P(k+1)

    k^5-k being divisible by 10 causes (k+1)^5-(k+1) to also be divisible by 10 ?

    If we can show that (k+1)^5-(k+1) must be divisible by 10 if k^5-k is,

    then we've shown that if P(k) is true for k=2, this causes P(k) to be true for k=3,
    which causes P(k) to be true for k=4....
    a never-ending chain of cause and effect.

    Then P(k) being true for k=2, causes P(k) to be true for all k above 2
    in the natural number system.

    We never know that the original statement is true until after we have
    validated P(k+1) and checked the formula for k=2.

    K and k+1 are used instead in the notation instead of n and n+1 merely to focus in on
    all pairs of adjacent terms.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,347
    Thanks
    30
    I might add that

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

    and

    10| n^5-n and 10|5n(n+1).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Jun 2009
    Posts
    660
    Thanks
    133
    We can also get to the result without induction.

    N = n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)

    The RHS contains the product of three consecutive integers, so one of them must be even, so N is divisible by 2.

    If one of these three is divisible by 5 also then we are done, so assume that this isn't the case, in which case either  n + 1 is 1 less than a multiple of 5 or  n - 1 is 1 more than a multiple of 5.

    Taking the first of these possibilities,

    let n+1 = 5p-1, say, then n=5p-2,

    so n^2+1=(5p-2)^2+1=25p^2-20p+5 which is divisible by 5, and in which case so is N and so N is divisible by 10. Similarly for the other possibility.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 15th 2010, 07:45 PM
  2. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 06:01 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum