Results 1 to 7 of 7

Math Help - Inductive Proof, is this way valid?

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    20

    Inductive Proof, is this way valid?

    Have to prove 2^n >= n^2 for n>=4

    I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

    Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

    So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

    ...2(n+1)^2 >= (n+2)^2

    2n^2 + 4n + 2 >= n^2 + 2n + 4
    n^2 + 4n + 2 >= 2n + 4
    n^2 + 2n + 2 >= 4

    Since we know n must be >= 4 ...16 + 8 + 2 >= 4

    So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

    Is this valid? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by HeadOnAPike View Post
    Have to prove 2^n >= n^2 for n>=4

    I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

    Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

    So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

    ...2(n+1)^2 >= (n+2)^2

    2n^2 + 4n + 2 >= n^2 + 2n + 4
    n^2 + 4n + 2 >= 2n + 4
    n^2 + 2n + 2 >= 4

    Since we know n must be >= 4 ...16 + 8 + 2 >= 4

    So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

    Is this valid? Thanks.


    Suppose n\geq4 and 2^n \geq n^2 is true.

    Let n=k+3 where 1 \leq k \leq N

    For  k=1, 2^n=16 \geq n^2=16

    Now,

    If  n=k+3 , where 2 \leq k \leq N, and 2^n \geq  n^2 is true.

    Then when n=3+(k+1)

    2^{k+1} \geq (k+1)^2 \rightarrow

    2^{k+1} \geq k^2+2k+1 \rightarrow

    2\cdot 2^{k} \geq k^2+2k+1 \rightarrow

    Since ( 2\cdot 2^{k}) \geq 2k^2 \geq k^2+2k+1 , then

    ( 2\cdot 2^{k}) \geq k^2 \geq 2k+1


    2^{k+1} \geq (k+1)^2 is true

    Consequently, 2^n\geq n^2 is true for all n \geq 4
    Last edited by novice; October 9th 2009 at 11:05 AM. Reason: final fix
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by HeadOnAPike View Post
    Have to prove 2^n >= n^2 for n>=4

    I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

    Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

    So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

    ...2(n+1)^2 >= (n+2)^2

    2n^2 + 4n + 2 >= n^2 + 2n + 4
    n^2 + 4n + 2 >= 2n + 4
    n^2 + 2n + 2 >= 4

    Since we know n must be >= 4 ...16 + 8 + 2 >= 4

    So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

    Is this valid? Thanks.


    This part of your argument makes no sense:

    So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

    ...2(n+1)^2 >= (n+2)^2

    2n^2 + 4n + 2 >= n^2 + 2n + 4
    n^2 + 4n + 2 >= 2n + 4
    n^2 + 2n + 2 >= 4

    Since we know n must be >= 4 ...16 + 8 + 2 >= 4

    ----------
    In prove by induction, you cannot simply plug in numbers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by novice View Post
    This part of your argument makes no sense:

    So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

    ...2(n+1)^2 >= (n+2)^2

    2n^2 + 4n + 2 >= n^2 + 2n + 4
    n^2 + 4n + 2 >= 2n + 4
    n^2 + 2n + 2 >= 4

    Since we know n must be >= 4 ...16 + 8 + 2 >= 4

    ----------
    In prove by induction, you cannot simply plug in numbers.

    I think he meant: 2(n+1)^2 >= (n+2)^2 <==> ...etc., until he arrived to
    ...<==> n^2 + 2n + 2 >= 4, and since this last inequality is obviously true whenever n >= 4 then we can go backwards and get what we wanted.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by tonio View Post
    I think he meant: 2(n+1)^2 >= (n+2)^2 <==> ...etc., until he arrived to
    ...<==> n^2 + 2n + 2 >= 4, and since this last inequality is obviously true whenever n >= 4 then we can go backwards and get what we wanted.

    Tonio
    Thank you, Tonio.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2009
    Posts
    20
    Sorry for the ambiguity there. So I am assuming this is good?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by HeadOnAPike View Post
    Sorry for the ambiguity there. So I am assuming this is good?
    Yes, it is a valid argument. It will be superb if you could make your arguments flow.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 01:09 PM
  2. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 09:38 AM
  3. Ugh, another inductive proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 02:56 PM
  4. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 06:24 PM
  5. help...inductive proof???
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 03:11 PM

Search Tags


/mathhelpforum @mathhelpforum