Results 1 to 4 of 4

Math Help - Proof by induction help??

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    69

    Post Proof by induction help??

    k
    Last edited by Intsecxtanx; November 5th 2009 at 03:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    It would help if you showed what you've done so far and where you're stuck!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    69

    Smile

    k
    Last edited by Intsecxtanx; November 5th 2009 at 03:34 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Intsecxtanx View Post
    Prove by induction that if n > 1, then 2^n < 1 + n 2^{n-1}

    Basis step: I must first verify that the given propositions P(n) are true for n = 0.
    However, if n > 1, then the smallest possible value of n = 2.
    I must first prove that P(2) is true for n = 2.

    2^2 < 1 + 2 ( 2^{2-1})
    4 < 1 + 2(2)
    4 < 5 which is true

    Inductive Hypothesis: Assume P(k) is true for some k.
    2^k < 1 + k 2^{k-1}
    2^{k+1} < 2 ( 1 + k 2^{k-1})
    2 (2^k) < 2 + k( 2^k)


    Inductive step: Prove that P(k+1) is true

    ****(THIS IS WHERE I'M STUCK)****



    Once the three steps have been completed, P(n) is true for all n
    If P(n) isnít true for all n, there exists a least counterexample, say k. By the Basis Step, this k is not 0, so k > = 1. but then k-1 > 0 and for k-l the proposition is true



    Thank you for your help and time!
    Your basic step is correct. That is, you assume P(k) is true. Assuming P(k) is true means we assume that 2^k < 1+k2^{k-1} for some arbitrary positive integer k.

    Now, we want to prove that P(k+1) is true. This means we want to prove that the following inequality: 2^{k+1} <  1 + (k+1)2^{k-1+1} holds. We shall prove it by using our assumption:

    2^{k+1} = 2 \cdot 2^k. Now, we shall use the fact that a\cdot 2^k < b\cdot 2^k for any positive a,b such that a<b. How will we use this? -- We know that the minimal value of k is 2, and therefore the minimal value of k+1 is 3. Therefore, 2\cdot 2^k < (k+1)\cdot 2^k.

    --> 2^{k+1} < (k+1)2^k < 1+ (k+1)2^k, and this is exactly what we were looking to prove: 2^{k+1}<1+(k+1)2^k. Therefore P(k+1) is true and we are done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induction proof
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 5th 2010, 10:04 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  3. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 29th 2008, 08:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. Proof By Induction help!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 29th 2008, 10:49 AM

Search Tags


/mathhelpforum @mathhelpforum