Results 1 to 7 of 7

Math Help - Could someone check this induction?

  1. #1
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1

    Could someone check this induction?

    Could someone please check this induction proof, unsure if this is the correct way to go about it.

    Prove by induction that 9 \times 4^n + 5 \times 11^n is divisible by 7 for all non negative integers n.

    Initial step, n=0

    9 \times 4^0 + 5 \times 11^0 = 14, therefore true for n=0.

    Induction step. Assume for n=k, therefore 9 \times 4^k + 5 \times 11^k = 7a for some a.

    Therefore for n=k+1 we have:

    9 \times 4^{k+1} + 5 \times 11^{k+1}

    9(4^k) + 9(4) + 5(11^k) + 5(9)

    9(4^k) + 5(11^k) + 9(4) + 5(9)

    7a + 91

    7(a + 13).

    Therefore true for all n.
    Last edited by Jameson; November 29th 2009 at 03:26 PM. Reason: latex
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by craig View Post
    Could someone please check this induction proof, unsure if this is the correct way to go about it.

    Prove by induction that 9 \times 4^n + 5 \times 11^n is divisible by 7 for all non negative integers n.

    Initial step, n=0

    9 \times 4^0 + 5 \times 11^0 = 14, therefore true for n=0.

    Induction step. Assume for n=k, therefore 9 \times 4^k + 5 \times 11^k = 7a for some a.

    Therefore for n=k+1 we have:

    9 \times 4^{k+1} + 5 \times 11^{k+1}

    9(4^k) + 9(4) + 5(11^k) + 5(9)


    What, in the holy name of the Great Pumpkin, did you do here??!:

    9\cdot 4^{k+1}=9\cdot 4^k\cdot 4=36\cdot 4^k, and the same with the other term, so you need to correct this QUICKLY and think over your proof again.

    Tonio


    9(4^k) + 5(11^k) + 9(4) + 5(9)

    7a + 91

    7(a + 13).

    Therefore true for all n.
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    From
    Dagupan City
    Posts
    37

    Post

    Quote Originally Posted by tonio View Post
    .
    According to my teacher the steps should be as follows:
    1. Show that it is true for n=1.
    2. Assume that it is true for n=k.
    3. Show that the truth of n=k implies the truth of n=k+1

    then your equation is true for all natural numbers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Assume  9\cdot4^n+5\cdot11^n = 7k .

    Then  9\cdot3\cdot4^n+5\cdot10\cdot11^n+9\cdot4^n+5\cdot  11^n = 9\cdot3\cdot4^n+5\cdot10\cdot11^n +7k = 21k+5\cdot7\cdot11^n+7k.

    Therefore  9\cdot4^{n+1}+5\cdot11^{n+1} = 7(5\cdot11^n+4k) .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by chiph588@ View Post
    Assume  9\cdot4^n+5\cdot11^n = 7k .

    Then  9\cdot3\cdot4^n+5\cdot10\cdot11^n+9\cdot4^n+5\cdot  11^n = 9\cdot3\cdot4^n+5\cdot10\cdot11^n +7k = 21k+5\cdot7\cdot11^n+7k.

    Therefore  9\cdot4^{n+1}+5\cdot11^{n+1} = 7(5\cdot11^n+4k) .

    That was a weird, and not so natural imo, way to reach the result:

    9\cdot 4^{k+1}+5\cdot 11^{k+1}=36\cdot 4^k+55\cdot 11^k=<br />
4\left(9\cdot 4^k+5\cdot 11^k\right)+35\cdot 11^k

    And the first term is divisible by 7 because of the ind. hyp., and the second one is obviously divisible by 7, so we're done.
    Tonio
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Ahh thankyou for the replies. Not quite sure what I managed to do there, that's what you get for doing proofs at 11 at night!

    Thanks for all the replies, very helpful.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by craig View Post
    Ahh thankyou for the replies. Not quite sure what I managed to do there, that's what you get for doing proofs at 11 at night!

    Thanks for all the replies, very helpful.
    Induction proofs can be tricky once you get to the implication step. Remember that you are going to use the assumption that P(k) is true when showing P(k+1) follows. If you ever find yourself ending up like you did with P(k+1) seeming to be true regardless of P(k), you should back up.

    Also, just like integrals, induction proofs have different forms and call for different techniques. Once you practice all of the techniques and know what type of problem they go with, it all becomes easier.

    I myself have not become familiar with many induction situations and can only notice the divisibility situation or the summation one. I actually couldn't figure this one out last night because I couldn't see the way needed to split up the terms such that the condition is satisfied. This is advice to myself as well as you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] need to check strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 4th 2011, 02:38 AM
  2. Replies: 4
    Last Post: March 12th 2011, 04:05 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Induction check
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 20th 2010, 11:46 AM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM

Search Tags


/mathhelpforum @mathhelpforum