Turn on thread page Beta
    • Thread Starter
    Offline

    15
    ReputationRep:
    So I have to prove this
    n!>2^n for n\geq4

    so the base case
    4!=24>2^4=16

    then inductive hypothesis n=k
    k!>2^k

    to show that it implies n=k+1
    k!>2^k
    =>
    (k!)(k+1)>2^{k}(k+1)
    =>
    (k+1)! = k!(k+1)> 2^{k}(k+1)> 2 \times 2^k=2^{k+1}
    by (k+1)>2 since k>4.
    So by induction, n!>2^n for n\geq4.

    Is this correct?
    Offline

    0
    ReputationRep:
    Looks good to me.
    Offline

    4
    ReputationRep:
    I'd advise being a bit clearer when presenting. Your statements are written like this: a = b > c = d, which is confusing to say the least, if not plain wrong.
    Offline

    0
    ReputationRep:
    (k!)(k+1)>2^{k}(k+1)
    this seems dodgy to me but what do i know
    (k!)(k+1)>2^{k+1} ?
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by spex)
    I'd advise being a bit clearer when presenting. Your statements are written like this: a = b > c = d, which is confusing to say the least, if not plain wrong.
    What's wrong with it? It might look a bit ugly, but I don't think it's wrong.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by Intergrate this u F##*...)
    (k!)(k+1)>2^{k}(k+1)
    this seems dodgy to me but what do i know
    (k!)(k+1)>2^{k+1} ?
    Nope. What's dodgy about it?
    Offline

    4
    ReputationRep:
    (Original post by generalebriety)
    What's wrong with it? It might look a bit ugly, but I don't think it's wrong.
    Well you should be able to to read a statement on either side of an equals sign and it make sense.

    The second line suggests that 4! =... = 16.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by spex)
    Well you should be able to to read a statement on either side of an equals sign and it make sense.

    The second line suggests that 4! =... = 16.
    Well, yes, if it's a chain of equality, but the "<" sign breaks that chain. If you read it from left to right it says "4! equals 24, which is less than 2^4, which equals 16".
    • Thread Starter
    Offline

    15
    ReputationRep:
    Thanks. Its just in some cases its hard to know how much to write.

    A good example is Bernoulli's inequality.
    (1+x)^n \geq 1+nx
    for all non-negative integer values of n and real number x>-1.

    So base step, therefore n=0.
    (1+x)^0=1=1+0x
    which is trivially true.

    Inductive step let n=k.
    (1+x)^k \geq 1+kx

    so to show that this implies n=k+1

    (1+x)^{k}(1+x) \geq (1+kx)(1+x) (no sign change since ((1+x)>0)
    =>
    (1+x)^{k+1} \geq 1+kx+x+kx^{2}=1+(k+1)x +kx^{2} \geq 1+(k+1)x
    Since (k\geq0 and x^{2}\geq0) =>kx^{2}\geq0.

    So by induction, proven.

    But I don't know about that last bit. Its sort of obvious, but would I need to go into more detail.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    That's fine. (It's not really that obvious.)
    Offline

    2
    ReputationRep:
    I don't understand what comes after the = sign on this line:

    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by mcp2)
    I don't understand what comes after the = sign on this line:

    Well, kx + x = (k+1)x. Look at the number of "x" on the left hand side; you have k of them, plus one of them. That's k+1 of them.
    Offline

    2
    ReputationRep:
    Understood that but where did 1+(k+1)x come from after the second > sign?
    Offline

    0
    ReputationRep:
    (Original post by mcp2)
    Understood that but where did 1+(k+1)x come from after the second > sign?
    Recall three fundamental properties of inequalities:
    - squares are non-negative
    - multiplying both sides by a positive number preserves the inequality
    - adding the same number to both sides preserves the inequality

    x^2 ≥ 0 => kx^2 ≥ 0 when k ≥ 0 [multiplying by a positive number]
    => kx^2 + (k+1)*x + 1 ≥ 1 + (k+1)*x [adding 1 + (k+1)x...]

    We did this because 1 + (k+1)*x was our goal by induction.
    Offline

    2
    ReputationRep:
    (Original post by AsakuraMinamiFan)
    => kx^2 + (k+1)*x + 1 ≥ 1 + (k+1)*x [adding 1 + (k+1)x...]

    We did this because 1 + (k+1)*x was our goal by induction.
    Thanks! That's what was the bit that was troubling me! This should help when I actually do induction!
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: July 18, 2009

3,588

students online now

800,000+

Exam discussions

Find your exam discussion here

Poll
Should universities take a stronger line on drugs?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.