Results 1 to 9 of 9

Math Help - Maths Induction

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    26

    Maths Induction

    Hi Everyone,

    Still trying to grasp doing inductions, saw this question today but i got it completely wrong.

    Any assistance would be most appreciative.


    Using induction to pove that for all n≥4 the inequalities 2ⁿ ≥ n and 2ⁿ < n! hold.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by extatic View Post
    Hi Everyone,

    Still trying to grasp doing inductions, saw this question today but i got it completely wrong.

    Any assistance would be most appreciative.


    Using induction to pove that for all n≥4 the inequalities 2ⁿ ≥ n and 2ⁿ < n! hold.
    Show p(4) is true, then assume p(k) is true, and then show p(k+1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    26
    Hows this going?

    n=4

    2^4 ≥ n and 2^4 < 4!
    = 16 ≥ 16 and 16<24.

    So this is correct.

    now n = k.

    2^k > k^2 and 2^k < k!

    p(k+1)

    2^k+1 > (k+1) and 2^k+1 < (k+1)!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by extatic View Post
    Hows this going?

    n=4

    2^4 ≥ n and 2^4 < 4!
    = 16 ≥ 16 and 16<24.

    So this is correct.

    now n = k.

    2^k > k^2 and 2^k < k!

    p(k+1)

    2^k+1 > (k+1) \wedge 2^k+1 < (k+1)!
    Now, you have to prove it! For example, suppose k\geq 4 and P(k) is true. So

    2^k \geq k^2 \wedge 2^k < k!

    Now consider P(k+1)

    LHS= 2^{k+1} \geq (k+1)^2

    By inductive hypothesis

    2^k.2  \geq 2^k +2k+1

    \geq (k+1)^2

    =RHS
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by extatic View Post
    Hows this going?

    n=4

    2^4 ≥ n and 2^4 < 4!
    = 16 ≥ 16 and 16<24.

    So this is correct.

    now n = k.

    2^k > k^2 and 2^k < k!

    p(k+1)

    2^k+1 > (k+1) and 2^k+1 < (k+1)!
    P(k)

    2^k\ \ge\ k^2\ ?...... k\ \ge\ 4

    P(k+1)

    2^{k+1}\ \ge\ (k+1)^2\ ?....... k\ \ge\ 4

    Proof

    2^12^k\ \ge\ k^2+2k+1\ ?...... k\ \ge\ 4

    by multiplying out (k+1)^2

    We are showing whether or not P(k) being true causes P(k+1) to be true.
    This is how induction works.
    The comments in the next post "correcting" this are incorrect


    2^k+2^k\ \ge\ k^2+2k+1\ ?....... k\ \ge\ 4

    If P(k) is true, then 2^k\ \ge\ k^2

    therefore is 2^k\ \ge\ 2k+1\ for\ k\ \ge\ 4\ ?

    2^4\ \ge\ 2(4)+1

    Therefore if 2^k\ \ge\ k^2

    then 2^{k+1}\ \ge\ (k+1)^2 also.


    P(k)

    2^k\ <\ k!\ ?

    P(k+1)

    2^{k+1}\ <\ (k+1)!\ ?

    Proof

    2^12^k\ < (k+1)k!\ ?

    2^k+2^k\ < (k)k!+k!

    We are showing that P(k) being true causes P(k+1) to be true


    If\ 2^k\ <\ k!\ and\ if\ k\ >\ 1

    2^k\ <\ (k)k!
    Last edited by Archie Meade; May 8th 2010 at 03:21 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Archie Meade View Post
    P(k)

    2^k\ \ge\ k^2\ ?...... k\ \ge\ 4

    P(k+1)

    2^{k+1}\ \ge\ (k+1)^2\ ?....... k\ \ge\ 4

    Proof

    2^12^k\ \ge\ k^2+2k+1\ ?...... k\ \ge\ 4<--You musn't do that. You must begin with 2\cdot 2^k\ \ge\ 2\cdot k^2

    2^k+2^k\ \ge\ k^2+2k+1\ ?....... k\ \ge\ 4

    If P(k) is true, then 2^k\ \ge\ k^2

    therefore is 2^k\ \ge\ 2k+1\ for\ k\ \ge\ 4\ ?

    2^4\ \ge\ 2(4)+1

    Therefore if 2^k\ \ge\ k^2

    then 2^{k+1}\ \ge\ (k+1)^2 also.


    P(k)

    2^k\ <\ k!\ ?

    P(k+1)

    2^{k+1}\ <\ (k+1)!\ ?

    Proof

    2^12^k\ < (k+1)k!\ ?

    2^k+2^k\ < (k)k!+k!<--You must not do that either. You must begin with 2\cdot 2^k\ < 2\cdot k!

    If\ 2^k\ <\ k!\ and\ if\ k\ >\ 1

    2^k\ <\ (k)k!
    You started your proof incorrectly where I marked in red. You are not to begin with the final results.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by extatic View Post
    Hi Everyone,

    Still trying to grasp doing inductions, saw this question today but i got it completely wrong.

    Any assistance would be most appreciative.


    Using induction to pove that for all n≥4 the inequalities 2ⁿ ≥ n and 2ⁿ < n! hold.
    The whole thing about basic mathematical induction is tedious algebra expansion and simplification. If you can expand one small step at a time, you should be able to do any form of induction in your first course of math in college. I am going to show you how to take the small steps. If you observe the example, you should not have trouble with simple induction.

    Remark: You can break down you proof into two parts: One for 2^n\geq n^2, and the other one, 2^n<n!

    You are to prove for all n\geq 4, P \wedge Q, where

    P: 2^n\geq n^2 and Q:2^n<n!

    Note: Keep this in mind that n\geq 4 (Let's call it the precondition.) We will return to this later.

    Here we prove statement
    P:

    Basis step:


    For n=4, P: 2^4\geq 4^2. Since this is true, we move on.

    Inductive Step:

    Suppose for a positive integer k> 4 that 2^k\geq k^2 is true. Then multiplying through by 2, we obtain

    2 \cdot k \geq 2\cdot k^2\\. Observe each step:
    2 \cdot k \geq k^2+ k^2\\
    2 \cdot k \geq k\cdot k+ k^2\\ Next, we substitute the precondition for one of the k's
    2 \cdot k \geq 4\cdot k+ k^2\\
    2 \cdot k \geq k^2 +2 k+2k \\ Next, we substitute the precondition for the k in the last term.
    2 \cdot k \geq k^2 +2 k+2\cdot 4 >(k^2 +2 k+1) Therefore,
    2 \cdot k \geq (k+1)^2

    Now, we will prove the statement Q:

    Basis Step:

    For all positive integer n> 4, 16=2^4<4!=24. This one checked.

    Inductive Step:

    Suppose for all positive integer k\geq4, 2^k < k!. Then multiplying through by 2, we obtain

     2^k < 2k!
     2^k < (1+1)k!<(k+1)\cdot k! since the smallest k in the parenthesis is greater than 4. Therefore,
     2^k <<(k+1)!

    Consequently, for all positive integer n \geq 4, P \wedge Q.
    Last edited by novice; May 7th 2010 at 10:10 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by novice View Post
    You started your proof incorrectly where I marked in red. You are not to begin with the final results.
    Novice,

    there was nothing wrong with the method.
    Please read the original post.
    I did not start with the final answer.
    Last edited by Archie Meade; May 8th 2010 at 03:16 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Archie Meade View Post
    Novice,

    there was nothing wrong with the method.
    Please read the original post.
    I did not start with the final answer.
    Yes, Sir.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Should I buy maths books to teach myself maths.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 21st 2011, 04:45 PM
  2. Help me with my grade 11 maths [easy maths]
    Posted in the Pre-Calculus Forum
    Replies: 11
    Last Post: December 27th 2009, 04:09 PM
  3. Maths Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 6th 2009, 05:11 AM
  4. Replies: 0
    Last Post: September 5th 2007, 03:50 AM
  5. Replies: 1
    Last Post: October 3rd 2006, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum