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
    10
    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
    10
    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, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum