Results 1 to 9 of 9

Thread: 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
    10
    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
    4
    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 02: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 09:10 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    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 02: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: Nov 21st 2011, 03:45 PM
  2. Help me with my grade 11 maths [easy maths]
    Posted in the Pre-Calculus Forum
    Replies: 11
    Last Post: Dec 27th 2009, 03:09 PM
  3. Maths Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Dec 6th 2009, 04:11 AM
  4. Replies: 0
    Last Post: Sep 5th 2007, 02:50 AM
  5. Replies: 1
    Last Post: Oct 3rd 2006, 08:59 AM

Search Tags


/mathhelpforum @mathhelpforum