Turn on thread page Beta
    • Thread Starter
    Offline

    1
    ReputationRep:
    Given that n is a postive integer greater than two, use the method of mathematical induction to prove that 2^n > 2n.

    Thanks guys
    Offline

    15
    ReputationRep:
    (Original post by SUKBarracuda)
    Given that n is a postive integer greater than two, use the method of mathematical induction to prove that 2^n > 2n.

    Thanks guys
    For n=3,
    2^3 > 2*3
    8 > 6

    For n=(k+1)
    2^(k+1) > 2(k+1)
    2^k > k+1

    I think that's enough to prove it, though it's the first induction I've ever tried so don't take my word for it.
    Offline

    2
    ReputationRep:
    Im a little rusty at the old induction, but here goes:

    Initial Step

    Let n=3

    Then 2^3 > 2 * 3

    Which is TRUE

    Induction Step

    Assume truth of case when n = k

    ie 2^k > 2k

    Then we wish to prove the truth of case when n= (k+1)

    ie 2^(k+1) > 2(k+1)

    2^(k+1) = (2^k)*(2) *Law of Indices: x^a * x^b = x^(a+b)*

    2(k+1) = 2k + 2
    when k > 2 , 2* (2^k) > 2k + 2

    So assertion is true for n = k + 1, and so by Mathematical Induction is proved for all positive integers n, with n > 2.


    Note: Induction step slightly messy.
    Offline

    2
    ReputationRep:
    Let n be a positive integer. Suppose that 2^n > 2n. Then

    2^(n + 1)
    = 2 * 2^n
    > 2 * 2n . . . by the inductive hypothesis
    = 4n
    = 2(n + 1) + 2(n - 1)
    >= 2(n + 1) . . . because n >= 1.

    So 2^(n + 1) > 2(n + 1).
    Offline

    2
    ReputationRep:
    I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

    2^k > k^10.
    Offline

    2
    ReputationRep:
    (Original post by Jonny W)
    Let n be a positive integer. Suppose that 2^n > 2n. Then

    2^(n + 1)
    = 2 * 2^n
    > 2 * 2n . . . by the inductive hypothesis
    = 4n
    = 2(n + 1) + 2(n - 1)
    >= 2(n + 1) . . . because n >= 1.

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

    I don't doubt your solution, infact it looks quite cushy, but how did we get from

    2^(n+1) = 2 * (2^n) (which I'm fine with) > 2* 2n
    Offline

    0
    ReputationRep:
    [Initial Step]

    Let n > limiting value (2)

    2^3 > 2(3) ? yes

    Let n = k and assume true

    2^k > 2k is true [A]

    [Induction]

    k --> k+1

    2^(k+1) > 2(k+1)

    2(2^k) > 2(k+1)

    2^k > k+1 [B]

    now if n = k is true, [2^k > 2k is true] then we have

    "2^k > 2k and k+1"

    and as A is true, we know that B is true, and if it holds for k+1 it holds for all values of k, and thus all values of n.

    Personally i'm never sure how far to go with them, whether you're meant to continue on to prove that 2k is actually greater than (k+1) or not, i don't know..

    Stubbsy
    Offline

    2
    ReputationRep:
    (Original post by Expression)
    I don't doubt your solution, infact it looks quite cushy, but how did we get from

    2^(n+1) = 2 * (2^n) (which I'm fine with) > 2* 2n
    We have assumed that 2^n > 2n. Multiplying both sides by 2,

    2 * (2^n) > 2 * (2n).
    Offline

    2
    ReputationRep:
    (Original post by Jonny W)
    We have assumed that 2^n > 2n. Multiplying both sides by 2,

    2 * (2^n) > 2 * (2n).

    LOL. Nice little manipulation !

    And:

    (Original post by Jonny W)

    = 4n = 2(n+1) + 2(n-1)
    Is something that clearly works, but not something that (certainly I) would have thought of doing straight away !

    Nice job.
    Offline

    14
    ReputationRep:
    (Original post by Jonny W)
    I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

    2^k > k^10.
    2^k > k^10

    Just some exploration:

    Obviously when 1<k<10 at least, the expression is untrue:

    2^2 > 2^10 ? no
    2^10 > 10^10 ? no

    For k < 1

    2^(1/2) > (1/2)^10? yes
    2^(1/3) > (1/3)^10? yes

    But these are not integers. For negative values of k: -1 > k

    2^(-2) > (-2)^10?

    Because of the even index on the right hand side, the right hand side will always be positive. So will the left hand side, because negative index numbers do not give negative numbers. So we may simplify this, is the special case for negative integers, to:

    1/(2^|k|) > |k|^10

    But as k gets very large and negative, the LHS will tend to zero, and the RHS will tend to infinity. So the best hope we have of satisfying this is when k is the smallest negative number possible, and try k = -1, k = -2:

    1/(2^|-1|) > |-1|^10
    1/2 > 1 ? no.

    1/(2^|-2|) > |-2|^10
    1/4 > 1024? no

    As we can see they will never meet in the middle, and the inequality will not be satisfied so long as k increases.

    What about: 0 < k < -1? Well, they aren't integers, although from a short look there are some values which satisfy the inequality (I think).

    So back to positive integers:

    2^k > k^10

    Taking logs,

    k ln 2 > 10 ln k
    k/(ln k) > 10/(ln 2)
    k/(ln k) > 14.427 (5s.f.)

    Try some values for k:

    k = 10

    10/(ln 10) > 14.427? no
    20/(ln 20) > 14.427? no
    50/(ln 50) > 14.427? no
    80/(ln 80) > 14.427? yes... aha
    65/(ln 65) > 14.427? yes
    60/(ln 60) > 14.427? yes
    55/(ln 55) > 14.427? no
    56/(ln 56) > 14.427? no
    57/(ln 57) > 14.427? no
    58/(ln 58) > 14.427? no
    59/(ln 59) > 14.427? yes

    so the first integer value of k which satisfies the inequality is 59:

    2^k > k^10
    2^58 > 58^10 ? no
    2^59 > 59^10 ? yes

    So we have found K.

    Now to prove that for all k >_ K, the inequality is satisfied, by induction:

    We know it works with 59.

    Now suppose it works for all values of k above 59:

    2^(k+1) > (k+1)^10
    2*2^k > k^10 + 10k^9 + 45k^8 + 120k^7 + 210k^6 + 252k^5 + 210k^4 + 120k^3 + 45k^2 + 10k + 1

    Wait... wrong way (what a waste of time)

    (k+1) ln 2 > 10 ln (k+1)
    (k+1)/(ln (k+1)) > 10/(ln 2)

    What now? I know it works for 59 and above, but can't prove this becuase I don't know how to use the fact it works for 59 and not below to finish...

    Argh. Oh well.
    Offline

    2
    ReputationRep:
    (Original post by Jonny W)
    I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

    2^k > k^10.
    Q. For which positive integers is it true that 2^k > k^10 ?

    We have that for k=59, then 2^59 > 59^10 (thanks to mik1a)

    Let P(k) be the statement that 2^k > k^10.

    Having seen that P(59) is true, then the basis for induction is established.
    The induction hypothesis is,

    2^k > k^10, where k >59.

    We now have to show that

    2^(k+1) > (k+1)^10

    Now 2^(k+1) = 2.2^k and so the induction hypothesis gives

    2^(k+1) > 2.k^10

    Therefore it suffices to show that for any k >=59,

    2.k^10 >= (k+1)^10,

    or rearranging,

    (1+1/k)^10 <= 2

    Consider the following argument. As k>1 the largest value of (1+1/k)^10 comes from the largest value of (1+1/k). This is turn comes from the smalles value of k, namely k=59. However (1+1/59)^10=1.183, which is less than 2. This completes the induction step.
    Hence, by the Generalised Principle of Mathematical Induction, the proposition is true.

    This is, more or less, a modification I took from my course notes (Number Theory) for a proof for 2^k > k³. And, as you can see, will apply to all powers of 2^k.
    Now, this may make the giving of rep a bit dubious, since it wasn't actually me who did the proving. In consequence of which I must claim that I had already proved the proposition, albeit by a somewhat more tedious method!

    I include the method from my notes as it's shorter and neater, But to claim my rep I submit my own proof

    I'm going to give the proof for k=3 only, as a method from which proofs for higher powers can be generated. I's also easier to follow the arguments when the (k+1)^3 bracket is expanded than if it were (k+1)^10.
    We have
    2^k > k^3, k=10 (induction hypothesis)

    Required to prove
    2^(k+1) > (k+1)^3, k >= 10
    or
    2.2^k > (k+1)^3

    now

    2.2^k > 2.k^3 = k^3 + k^3, from the induction hypothesis

    k³ > 10k², k>10
    k³ > 6k²
    k³ > 3k² + 3k²
    =========

    k² > 10k, k>10
    3k² > 30k
    => k³ > 3k² + 30k
    k³ > 3k² + 3k + 27k
    =============

    k > 10
    27k > 270 > 1
    => k³ > 3k² + 3k + 1
    => 2k³ > k³ + 3k² + 3k + 1
    => 2k³ > (k+1)³
    ===========

    which completes the inducion step.
    Hence, by the Generalised Principle of Mathematical Induction, the proposition is true.
    Offline

    1
    ReputationRep:
    what board is this? its very similar to OCR p4 :confused:
    Offline

    0
    ReputationRep:
    (Original post by jonas123)
    what board is this? its very similar to OCR p4 :confused:
    Edexcel - straight from the most useless official textbook in the world
 
 
 
Turn on thread page Beta
Updated: June 25, 2004
Poll
Do you think parents should charge rent?
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.