Hey there! Sign in to join this conversationNew here? Join for free
    • 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!
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Brussels sprouts
    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
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • 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

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