Results 1 to 5 of 5

Math Help - Induction Proof Problem

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    3

    Induction Proof Problem

    I'm trying to prove using induction that 5^n-2^n is divisible by 3 for all values of n. I'm used to using induction to get k+1 within an expression that verifies a given formula, and have never used it to try and get to an answer divisible by 3.

    So far I have 1 in the truth set because 5^1-2^1=5-2=3
    And with a value k in the truth set
    5^(k+1)-2^(k+1)=5(5^k)-2(2^k)
    but don't know how i can further manipulate this or if i'm even on the right track.

    If anyone could show me where to go from here i would be very grateful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by uconn711 View Post
    I'm trying to prove using induction that 5^n-2^n is divisible by 3 for all values of n. I'm used to using induction to get k+1 within an expression that verifies a given formula, and have never used it to try and get to an answer divisible by 3.

    So far I have 1 in the truth set because 5^1-2^1=5-2=3
    And with a value k in the truth set
    5^(k+1)-2^(k+1)=5(5^k)-2(2^k)
    but don't know how i can further manipulate this or if i'm even on the right track.
    Start by writing down what it means to say that k is in the truth set: 5^k-2^k is a multiple of 3, or in other words 5^k-2^k=3p, for some integer p.

    Now you can write that as 5^k = 2^k +3p. Substitute that expression for 5^k into the right-hand side of the equation 5^(k+1)-2^(k+1)=5(5^k)-2(2^k), and see where that leads you.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    645
    Hello, uconn711!

    Use induction to prove: . 5^n-2^n is divisible by 3 for all values of n.

    Verify S(1)\!:\;\;5^1 - 2^1 \:=\:3 . . . True!

    Assume S(k) is true: . 5^k - 2^k \:=\:3a .for some integer a.


    Add 4\!\cdot\!5^k - 2^k to both sides;

    . . \underbrace{5^k + 4\!\cdot\!5^k} - \underbrace{2^k - 2^k} \:=\:3a + 4\!\cdot\!5^k - 2^k
    . . (1 + 4)\!\cdot\!5^k - 2\!\cdot\!2^k \;=\;3a + \overbrace{3\!\cdot\!5^k + 5^k} - 2^k

    . . 5\!\cdot\!5^k - 2^{k+1} \;=\;3\left[a + 5^k\right] + \underbrace{5^k - 2^k}_{\text{This is }3a}

    Hence: . 5^{k+1} - 2^{k+1} \;=\;3\left[a + 5^k\right] + 3a \;=\;3\left[2a + 5^k\right] . . . a multiple of 3

    Therefore: . S(k+1) is true.
    . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2007
    Posts
    3
    Ah, I had to think through that a couple times, but that method actually makes alot of sense; thanks alot!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    I like this approach.
    If 5^N  - 2^N  = 3m then take a look at
    \begin{array}{rcl}<br />
 5^{N + 1}  - 2^{N + 1} & = & 5^{N + 1}  - 5\left( {2^N } \right) + 5\left( {2^N } \right) - 2^{N + 1}  \\ <br />
 & = & 5\left( {\underbrace {5^N  - 2^N }_{3m}} \right) + 2^N \left( {\underbrace {5 - 2}_3} \right) \\ <br />
 \end{array}<br /> <br />
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Problem with proof by mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 5th 2011, 12:56 AM
  2. Induction Proof Problem (for set union)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 9th 2010, 08:29 AM
  3. Extremely difficult induction proof problem
    Posted in the Calculus Forum
    Replies: 8
    Last Post: February 1st 2010, 10:28 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Confused by Induction Proof Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2009, 11:16 AM

Search Tags


/mathhelpforum @mathhelpforum