Results 1 to 5 of 5

Math Help - induction

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    12

    induction

    show that

    37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

    thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by sabrina87 View Post
    show that

    37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

    thank you
    I assume you're having trouble with step 3.

    Then note:

    37^{k+3} + 16^{k+2} + 23^{k+1} = 37 \cdot 37^{k+2} + 16 \cdot 16^{k+1} + 23 \cdot 23^{k}


    = 37 \left( 37^{k+2} + 16^{k+1} + 23^{k} \right) - 21 \cdot 16^{k+1} - 14 \cdot 23^k


    = 37 \left( 37^{k+2} + 16^{k+1} + 23^{k} \right) - 7 \left(3 \cdot 16^{k+1} + 2 \cdot 23^k\right)


    which is divisible by 7 due to step 2 ........
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by sabrina87 View Post
    show that

    37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

    thank you
    Here is a non-induction proof.
    Let A_n = 37^{n+2}+16^{n+1}+23^n.

    Note 37^{n+2}\equiv 2^{n+2} (\bmod 7), 16^{n+1}\equiv 2^{n+1}(\bmod 7), 23^n\equiv 2^n(\bmod 7).

    Thus, A_n \equiv 2^{n+2}+2^{n+1}+2^n = 2^n(1+2+2^2) \equiv 0 (\bmod 7).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Quote Originally Posted by ThePerfectHacker View Post
    Here is a non-induction proof.
    Let A_n = 37^{n+2}+16^{n+1}+23^n.

    Note 37^{n+2}\equiv 2^{n+2} (\bmod 7), 16^{n+1}\equiv 2^{n+1}(\bmod 7), 23^n\equiv 2^n(\bmod 7).

    Thus, A_n \equiv 2^{n+2}+2^{n+1}+2^n = 2^n(1+2+2^2) \equiv 0 (\bmod 7).
    Hello,
    could you explain the second solution, please?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by drthea View Post
    Hello,
    could you explain the second solution, please?
    The result you need to know here is that if a\equiv b(\bmod c) \implies a^k \equiv b^k (\bmod c).
    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. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 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. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum