Results 1 to 8 of 8

Math Help - Induction

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    Induction

    Is the the correct approach to work through this problem

    23n 1 is divisible by 7 for all n>=1
    n(1)
    23(1) 1 = (2*2*2) 1
    = 7

    23n 1 = 7m
    n(k+1)
    23(k+1) 1 = 2.23k-1
    = 2 * (7m+1) 1
    = 14m + 2 -1
    = 14m-1
    =7(2m-1)
    Where (2m-1) is an int.
    So 23n 1 is divisible by 7.
    Therefore, by P.M.I 23n 1 is divisible by 7 for n>=1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,406
    Thanks
    1294
    First, this is extremely difficult to read. Please learn some LaTeX.

    You are trying to prove 2^{3n} - 1 is divisible by 7 for all n \geq 1 (I assume n is also an integer)...


    Base Step: n = 1.

    Then 2^{3\cdot 1} - 1 = 8 - 1

     =7 which is divisible by 7.


    Inductive Step: Assume this statement is true for n = k.

    Then 2^{3k} - 1 = 7m where m is an integer.

    Now let n = k + 1 we have

    2^{3(k + 1)} - 1 = 2^{3k + 3} - 1

     = 2^{3k}\cdot 2^3 - 1

     = 8\cdot 2^{3k} + 8 - 7

     = 8(2^{3k} + 1) - 7

     = 8\cdot 7m - 7

     = 7(8m - 1)

    which is divisible by 7.


    Therefore 2^{3n}- 1 is divisible by 7 for all integer n \geq 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Thanks ProveIt, I completely forgot about Latex for a minute and just pasted in the equation I was working on in word, so sorry!

    How does the negative 1 in this line = 2^{3k}\cdot 2^3 - 1

    change to negative 7?

    =8\cdot 2^{3k} + 8 - 7
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,406
    Thanks
    1294
    Sorry, that should actually read

    8\cdot 2^{3k} - 8 + 7

     = 8(2^{3k} - 1) + 7.

    The rest follows.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    ok, thanks
    But how/where does the seven come from?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,406
    Thanks
    1294
    -8 + 7 = -1.

    It just takes a bit of practice, I knew I needed to create a 7 in order to have this value be divisible by 7.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Please excuse my ignorance, as mathematical Induction and I just aren't getting along.
    But did you just place the "7" in the equation because you needed it. It didn't come from any other part of the equation?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,406
    Thanks
    1294
    That's correct. And I also realised I'd need to take out a common factor of 8.

    Like I said, it just comes from experience.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum