Results 1 to 5 of 5

Math Help - Proof by induction: 7^n + 2 is divisible by 3

  1. #1
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    433
    Thanks
    12

    Proof by induction: 7^n + 2 is divisible by 3

    Use Proof by Mathematical induction to prove that 7^n + 2 is divisible by 3 for all n in the Natural Numbers.
    First thing I guess is to label the equation;

    p(n) = 7^n + 2

    And then Show that it holds for n=1:

    p(1) = 7^1 + 2
    p(1) = 9

    So it works for 1; 9 is divisible by 3.

    Now for p(n+1)...

    p(n+1) = 7^{n+1} + 2

    p(n+1) = 7 \cdot 7^{n} + 2

    Now how do I go about showing that that's divisible by 3?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jul 2012
    From
    INDIA
    Posts
    831
    Thanks
    209

    Re: Proof by induction: 7^n + 2 is divisible by 3

    we can do it my mathematical Induction: the steps as you pkow are
    prove that the statement P(n) is true for n=1.
    assume that P(k) is true.
    finally establish that when P(k) is true it implies P(k+1) is true.
    You have established that P(1) is true.
    Now we assume P(k) is true that means 7^k + 2 = 3 m for some m in N. That gives 7^k = 3m -2------ [1]
    For :P(k+1)
    7^(k+1) + 2 = 7^k * 7 + 2 = 7 ( 3m - 2) + 2 Using (1)
    = 21m -14 + 2
    I am sure you can take it further
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member agentmulder's Avatar
    Joined
    Aug 2011
    From
    42nd parallel, North America
    Posts
    105
    Thanks
    33

    Re: Proof by induction: 7^n + 2 is divisible by 3

    Or another way

     7 \cdot 7^n + 2 = (6 + 1)7^n + 2

     \underbrace {6 \cdot 7^n}_{divisible \ by \ 3} + \underbrace{7^n + 2}_{divisible \ by \ 3}

    So the whole thing is divisible by 3.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    433
    Thanks
    12

    Re: Proof by induction: 7^n + 2 is divisible by 3

    Quote Originally Posted by ibdutt View Post
    we can do it my mathematical Induction: the steps as you pkow are
    prove that the statement P(n) is true for n=1.
    assume that P(k) is true.
    finally establish that when P(k) is true it implies P(k+1) is true.
    You have established that P(1) is true.
    Now we assume P(k) is true that means 7^k + 2 = 3 m for some m in N. That gives 7^k = 3m -2------ [1]
    For :P(k+1)
    7^(k+1) + 2 = 7^k * 7 + 2 = 7 ( 3m - 2) + 2 Using (1)
    = 21m -14 + 2
    I am sure you can take it further
    Ah I get it, so you have to set the equation to 3m where m is a natural number.

    And then at the end:
    = 21m -14 + 2
    = 21m - 12
    = 3 (7m - 4)

    Which is a multiple of 3 and so the solution will always be divisible by 3.

    Quote Originally Posted by agentmulder View Post
     \underbrace {6 \cdot 7^n}_{divisible \ by \ 3} + \underbrace{7^n + 2}_{divisible \ by \ 3}
    How do you know that:

    \underbrace{7^n + 2}_{divisible \ by \ 3}

    That that's divisible by 3? I thought that's why I'm trying to prove, so I can't assume it's divisible by 3...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member agentmulder's Avatar
    Joined
    Aug 2011
    From
    42nd parallel, North America
    Posts
    105
    Thanks
    33

    Re: Proof by induction: 7^n + 2 is divisible by 3

    Quote Originally Posted by Educated View Post
    Ah I get it, so you have to set the equation to 3m where m is a natural number.

    And then at the end:
    = 21m -14 + 2
    = 21m - 12
    = 3 (7m - 4)

    Which is a multiple of 3 and so the solution will always be divisible by 3.



    How do you know that:

    \underbrace{7^n + 2}_{divisible \ by \ 3}

    That that's divisible by 3? I thought that's why I'm trying to prove, so I can't assume it's divisible by 3...
    That is the inductive step, you assume it holds for k = n and then you use that assumption to prove that it MUST hold when k = n + 1

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by induction 5^n-1 is divisible by 4
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2011, 09:54 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 03:55 PM
  3. Proof by induction: 4^n + 6n + 8 is divisible by 9.
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 19th 2011, 04:24 PM
  4. Replies: 5
    Last Post: November 14th 2009, 03:20 AM
  5. divisible by 11 proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2008, 08:49 AM

Search Tags


/mathhelpforum @mathhelpforum