Results 1 to 7 of 7

Math Help - Induction question

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    9

    Induction question

    A brief induction question if no-one minds.

    "Prove by induction, 7n - 1 is divisible by 6 for all n >= 1."

    n = 1 -> 7 - 1 /6 = 1 so the first condition of induction is satisfied, but I honestly can't work out where to go next...
    Follow Math Help Forum on Facebook and Google+

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

    It is not true.

    n=10
    7*10-1=69!=k*6 when k is natural.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    9
    sorry - accidental double post.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Not true... hmm, I'll include what the book says.

    "In the case n = 1, 7n - 1 is divisible by 6 so P(1) is true.

    Assume now the 7k - 1 is divisible by 6 for some k >= 1.
    Then,

    7k + 1 = 7(7k) - 1
    = 7(7k - 1) + 7 -1
    = 7)7k - 1) + 6

    Since 7k - 1 is divisible by 6 it follows that 7(7k - 1) + 6 is also divisible by 6."
    Follow Math Help Forum on Facebook and Google+

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

    but if...

    you need to prove:

    6|7^n - 1 for n>=1

    so

    we suppose that its true for some n and we prove for n+1.


    7^(n+1) - 1 = 7^n*7 - 1 = 7^n(6+1) - 1 = 7^n*6 +7^n - 1

    7^n-1 divides by 6 by the step of induction, 6*7^6 divides also by 6.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Skeith View Post
    Not true... hmm, I'll include what the book says.

    "In the case n = 1, 7n - 1 is divisible by 6 so P(1) is true.

    Assume now the 7k - 1 is divisible by 6 for some k >= 1.
    Then,

    7k + 1 = 7(7k) - 1
    = 7(7k - 1) + 7 -1
    = 7)7k - 1) + 6

    Since 7k - 1 is divisible by 6 it follows that 7(7k - 1) + 6 is also divisible by 6."
    Make your post clearer next time and you will get a proper answer. As you can see, from your first post it looks like you are trying to prove that 6 | (7\cdot n - 1) which is obviously wrong (take n=2, for example).

    However I guess you are trying to prove that 6|(7^n-1), which is correct. If this is the case, you have shown P(1) holds. Assume P(k), and now we need to prove that P(k+1) follows.

    Note that:

    7^{k+1}-1 = 7\cdot 7^k - 1 = (6+1)7^k - 1 = 6 \cdot 7^k + (7^k-1)

    Now, by the induction hypothesis (that is, 6|7^k -1), we get:

    6 \cdot 7^k + (7^k-1) = 6\cdot 7^k + 6m for some m \in \mathbb{N}.

    But 6\cdot 7^k + 6m = 6(7^k + m) which is divisible by 6, therefore P(k+1) holds and we are done.


    If you want to follow your book's way:

    7^{k+1}-1 = 7\cdot 7^k-1

    But, 7\cdot 7^k -1 = 7\cdot 7^k -7 +7 -1 =7 \cdot 7^k + 7\cdot (-1) + 7 -1=  7 \cdot (7^k-1) + 7 - 1 = 7 \cdot (7^k -1)+6

    Now, by the induction hypothesis, 6|(7^k-1) and therefore  7^k-1 = 6m for some m \in \mathbb{N}. Substitute and get:

    7 \cdot (7^k-1)+6 = 7 \cdot 6m + 6 = 6(7m + 1) and obviously 6 | 6(7m+1) therefore P(k+1) holds and we are done.
    Last edited by Defunkt; December 7th 2009 at 01:03 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2009
    Posts
    9
    I'll be sure to do that in future Def. Thankyou all once again for your help, I understand the problem now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. question about induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 19th 2009, 02:32 PM
  2. Induction question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 2nd 2009, 01:32 AM
  3. a question about induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 04:25 AM
  4. Induction question..
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 2nd 2007, 05:00 PM
  5. Induction Question!!!
    Posted in the Algebra Forum
    Replies: 11
    Last Post: June 15th 2007, 09:51 PM

Search Tags


/mathhelpforum @mathhelpforum