Results 1 to 5 of 5

Math Help - [SOLVED] induction proof

  1. #1
    Newbie jimboruss's Avatar
    Joined
    Feb 2008
    Posts
    2

    [SOLVED] induction proof

    This is my first post. I found this site when I was trying to find something online to get some help on some discrete math homework. Hopefully somebody can help me out.

    I have four proofs that are the same basic type, that I just can't quite figure out. Here is an example:
    (5^(n+1) + 2*3^n + 1) | 8 for all n >= {0,1,2,3,...}

    here's what I have so far:
    basis:
    n=0 5^1 + 2*3^0 + 1 = 5 + 2 + 1 = 8 | 8 = 1
    n=1 5^2 + 2*3^1 + 1 = 25 + 6 + 1 = 32 |8 = 4
    so I believe the proposition is true

    hypothesis: (5^(n+1) + 2*3^n + 1) | 8
    going to: (5^(n+2) + 2*3^(n+1) + 1) | 8

    (5^(n+2) + 2*3^(n+1) +1)
    = (5*5^(n+1) + 2*3*3^n +1)
    = (4*5^(n+1) + 5^(n+1) + 2*2*3^n + 2*3^n +1)
    = 4(5^(n+1) + 3^n) + (5^(n + 1) +2*3^n + 1)

    and this is as far as I've been able to get on all three of them.
    I know that the last part (5^(n+1) + 2*3^n + 1) is divisible by 8 from the inductive hypothesis, but I can't figure out how to get the first part.

    On another problem I factor out 5 from the first part but I'm trying to get it divisible by 10, and a third problem I factored out 4 trying to get it divisible by 16.

    Any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2007
    Posts
    127
    Welcome to the forums, mate.

    Ok, so you've proved the base case. Now we assume that n=k is true, that is,

     5^{k+1} + 2(3^k) + 1 = 8a where a is an integer.
    This can be rewritten as
    5^{k+1} = 8a - 2(3^k) -1

    Now consider n=k+1

     5^{k+2} + 2(3^{k+1}) +1
     = 5(8a - 2(3^k) -1) + 2(3^{k+1}) +1 (by induction hypothesis)
     = 40a -10(3^k) -5 + 6(3^k) +1
     = 40a - 4(3^k) -4
     = 4(10a -3^k -1)
     = 4(10a - (3^k +1))
    But you know that  10a - (3^k +1) is always even. So you can say that  10a - (3^k+1) = 2l where l is an integer.

    so you're left with  4(2l) =8l. Thus it is divisible by 8.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by jimboruss View Post
    This is my first post. I found this site when I was trying to find something online to get some help on some discrete math homework. Hopefully somebody can help me out.

    I have four proofs that are the same basic type, that I just can't quite figure out. Here is an example:
    (5^(n+1) + 2*3^n + 1) | 8 for all n >= {0,1,2,3,...}

    here's what I have so far:
    basis:
    n=0 5^1 + 2*3^0 + 1 = 5 + 2 + 1 = 8 | 8 = 1
    n=1 5^2 + 2*3^1 + 1 = 25 + 6 + 1 = 32 |8 = 4
    so I believe the proposition is true

    hypothesis: (5^(n+1) + 2*3^n + 1) | 8
    going to: (5^(n+2) + 2*3^(n+1) + 1) | 8

    (5^(n+2) + 2*3^(n+1) +1)
    = (5*5^(n+1) + 2*3*3^n +1)
    = (4*5^(n+1) + 5^(n+1) + 2*2*3^n + 2*3^n +1)
    = 4(5^(n+1) + 3^n) + (5^(n + 1) +2*3^n + 1)

    and this is as far as I've been able to get on all three of them.
    I know that the last part (5^(n+1) + 2*3^n + 1) is divisible by 8 from the inductive hypothesis, but I can't figure out how to get the first part.

    On another problem I factor out 5 from the first part but I'm trying to get it divisible by 10, and a third problem I factored out 4 trying to get it divisible by 16.

    Any help would be greatly appreciated.
    As you no doubt realise, you need a cunning manipulation:

    5^{k+2} + 2 \times 3^{k+1} + 1 = 5\left( 5^{k+1} + 2 \times 3^k + 1 \right) - (4 \times 3^k + 4).

    The first term is clearly divisible by 8 by the inductive hypothesis.

    As for the second term, note that 4 \times 3^k + 4 = 4 (3^k + 1). Can you prove (by induction, perhaps) that 3^k + 1 is always divisible by 2 when k is a positive integer. It then follows that the second term is divisible by 8 .....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie jimboruss's Avatar
    Joined
    Feb 2008
    Posts
    2

    Thank you

    Thank you WWTL@WHL and mr fantastic. You two are both my heroes. I never even thought of using induction a second time.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by jimboruss View Post
    [snip] I never even thought of using induction a second time.
    Yeah well, I fiddled around for a few moments but couldn't see a simple way of re-arranging 3^k + 1 so that 2 was obviously a factor (someone will come along now and make me look a complete chump).

    But intuitively you know that 3^k + 1 is even and therefore MUST be divisible by 2.

    But intuition is not a proof ..... Proof by induction can sometimes be an excellent tool for proving something true when you know intuitively that it is true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 10th 2010, 03:11 AM
  2. [SOLVED] Need some help with an induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 25th 2010, 08:28 AM
  3. [SOLVED] induction proof of summation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 30th 2009, 03:29 AM
  4. [SOLVED] Proof of divisibility by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 14th 2007, 09:15 PM
  5. [SOLVED] [SOLVED] proof by induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2006, 12:28 AM

Search Tags


/mathhelpforum @mathhelpforum