Results 1 to 5 of 5

Math Help - Proof by induction that 4| 5^n - 1

  1. #1
    iva
    iva is offline
    Member iva's Avatar
    Joined
    Nov 2009
    From
    South Africa
    Posts
    81

    Proof by induction that 4| 5^n - 1

    I have this problem that I know ( by just knowing ) that its true, but I have to prove by induction, and I am stuck on the induction step.
    The question asks:

    Use induction to show that 5^n - 1 (5 to the power of n ) is divisible by 4 for all n element of Natural numbers , n >= 1.

    So I have come this far:

    Basic Step:

    Let P(n) be the predicate 4 | 5^n - 1

    Then P(1) is 4|5^1 - 1 = 4 which is a tautology

    Induction Step:

    We must show that for k>=1 if P(k) is true, then P(k+1) must also be true.
    We assume for some k >=1 that

    4| 5^n - 1

    We now want to show that P(k+1) is true:

    4 |5^(k+1) - 1


    The right hand side of this statement is

    5^(k+1) - 1 = 5^k.5 - 1

    Now I know that it will work for all exponents of 5 because every exponential of 5 ends in 25 ( 125, 625, 3125, 15625) and minusing 1 gives 24 which is divisble by 4 ( and any multiple of 100 is also divisble by 4)
    So how can i put this in induction language?

    I have also tried it this way:

    Let's say
    5k - 1 = 4r where r is a natural number. We can rewrite this as :
    5^k = 4r + 1

    Basic step:
    So for n=1 P(1) = 5-1=4(1) = 4,this is true.

    Induction step:
    Then for k+1:

    5k+1 - 1 = 4r

    5.5k = 4r + 1

    This is the same as above (in bold) showing that for k+1 5k-1 is always divisible by 4.

    Many thanks
    Last edited by iva; May 17th 2010 at 10:18 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    5^{k+1}-1=5^{k+1}-5+5-1=5(5^k-1)+(4)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by iva View Post
    I have this problem that I know ( by just knowing ) that its true, but I have to prove by induction, and I am stuck on the induction step.
    The question asks:

    Use induction to show that 5^n - 1 (5 to the power of n ) is divisible by 4 for all n element of Natural numbers , n >= 1.

    So I have come this far:

    Basic Step:

    Let P(n) be the predicate 4 | 5^n - 1

    Then P(1) is 4|5^1 - 1 = 4 which is a tautology

    Induction Step:

    We must show that for k>=1 if P(k) is true, then P(k+1) must also be true.
    We assume for some k >=1 that

    4| 5^n - 1

    We now want to show that P(k+1) is true:

    4 |5^(k+1) - 1


    The right hand side of this statement is

    5^(k+1) - 1 = 5^k.5 - 1 \color{red}=(4)5^k+5^k-1

    Now I know that it will work for all exponents of 5 because every exponential of 5 ends in 25 ( 125, 625, 3125, 15625) and minusing 1 gives 24 which is divisble by 4 ( and any multiple of 100 is also divisble by 4)
    So how can i put this in induction language?

    Many thanks
    If 5^k-1 is divisible by 4, then (4)5^k + \left(5^k-1\right) will definately be divisible by 4.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,686
    Thanks
    617
    Hello, iva!

    Use induction to show that: .  5^n - 1 is divisible by 4 . for all n \in N,\;n \geq 1

    You proved the basic statement: . S(1) is true.


    We assume that S(k) is true:

    . . 5^k - 1 \:=\:4a\;\text{ for some integer }a


    Add 4\cdot5^k to both sides:

    . . . 5^k + {\color{blue}4\cdot5^k} -1 \;=\;4a + {\color{blue}4\cdot5^k}

    . . (1+4)\cdot5^k -1\;=\;4a + 4\cdot5^k

    . . . . . 5\cdot5^k - 1 \;=\; 4a + 4\cdot5^k


    And we have:

    . . 5^{k+1} -1\;=\;\underbrace{4(a + 5^k)}_{\text{multiple of 4}}


    We have proved S(k+1)
    . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    iva
    iva is offline
    Member iva's Avatar
    Joined
    Nov 2009
    From
    South Africa
    Posts
    81
    Thanks a mill guys
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by induction help??
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 5th 2009, 01:19 PM
  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 with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Proof by induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 5th 2008, 04:11 AM

Search Tags


/mathhelpforum @mathhelpforum