Turn on thread page Beta

proof by induction watch

Announcements
    • Thread Starter
    Offline

    9
    ReputationRep:
    how would you prove that for all integers > 0, and given that x>=-1:

    (1+x)^n >= 1 + nx

    i tried doing this by induction....it's true for n=1

    so suppose (1+x)^k >= 1 + kx
    then:

    (1+x)^(k+1) = (1+x)((1+x)^k)

    so: (1+x)^(k+1) >= (1+x)(1+kx)
    >= 1 + (k+1)x + kx^2

    but how do you lose the kx^2?
    Offline

    1
    ReputationRep:
    Simple, x^2 >= 0, so
    1 + (k+1)x + kx^2 >= 1 + (k+1)x
    • Thread Starter
    Offline

    9
    ReputationRep:
    doh yeah of course!
    • Thread Starter
    Offline

    9
    ReputationRep:
    so hold on....is the condition x>=-1 actually required?
    Offline

    0
    ReputationRep:
    this is correct but should really use whole binomial expansion and then use x^n is always greater than or equal to zero if x>0 (this is easily shown inductively:

    x^k > 0
    x^(k+1) = x (x^k)

    Since x is positive or equal to zero . this must also be greater than or equal to zero.

    p.s. this is only strictly true if n and x are integers
    • Thread Starter
    Offline

    9
    ReputationRep:
    bionomial exapnsion not allowed to be used in answer i'm afraid!
    • Thread Starter
    Offline

    9
    ReputationRep:
    no see i havent involved the x>=-1 condition, so the proof isnt complete yet! how do I involve that part!?
    Offline

    14
    ReputationRep:
    (1+x)^n >= 1 + nx

    (1+x)^0 = 1
    1 + 0x = 1

    so it ss true for n=0

    assume tru for all n>0
    (1+x)^n >= 1 + nx

    (1+x)^(n+1) = (1+x)(1+x)^n

    1 + (n+1)x = 1 + nx + x

    so is this true?:
    (1+x)(1+x)^n >= 1 + nx + x

    from our assumption we know that (1+x)^n >= 1 + nx.
    however the modification is we multiply the LHS by x+1 and add x to the RHS. as x>0, and for n>0 (1+x)^n > 1, the LHS will always be larger than the LHS.

    so it is true for all n.

    I think that should work?
    I just did the induction on n rather than x.
    Offline

    2
    ReputationRep:
    Let P(n) be the statement that (1+x)^n >= 1 + nx

    Base Step

    Check that P(n) is true for n = 1:

    (1 + x)^1 >= 1 + x (which is true)

    Inductive Step

    Assume P(n) is true for all n > 0. Then P(n+1) is:

    (1 + x)^(n+1) = [(1 + x)^n].(1 + x)

    But you've assumed P(n) is true, so

    (1 + x)^(n+1) >= (1 + nx).(1 + x)
    >= 1 + x(n+1) + n.x^2

    As x >= -1 and n > 0 (this is where the condition of x plays the part in your proof), the expression n.x^2 will always be equal or greater than 0.

    so original statement >= 1 + x(n+1)

    Showing that P(n) true => P(n+1) true and we are done QED

    Euclid.

    Edit: (Sorry if I have repeated any thing from above, as I went straight into this reply and didn't read the previous posts)
    Offline

    1
    ReputationRep:
    (Original post by Euclid)

    As x >= -1 and n > 0 (this is where the condition of x plays the part in your proof), the expression n.x^2 will always be equal or greater than 0.
    i dont think the fact x>-1 implies n.x^2>0 for any n>0 this will always be true.
    the x>=-1 ensures 1+x>=0
    so if we assume (1+x)^k>1+kx then if we multiply by (1+x) for the induction step the inequality changes since (1+x)<0.
    Offline

    2
    ReputationRep:
    (Original post by evariste)
    i dont think the fact x>-1 implies n.x^2>0 for any n>0 this will always be true.
    the x>=-1 ensures 1+x>=0
    so if we assume (1+x)^k>1+kx then if we multiply by (1+x) for the induction step the inequality changes since (1+x)<0.
    Hmm yes, I'm starting to become really sloppy in my work. I should really think before saying anything .
 
 
 
Turn on thread page Beta
Updated: January 16, 2005

University open days

  • University of Derby
    Postgraduate and Professional Open Evening - Derby Campus Postgraduate
    Tue, 22 Jan '19
  • University of the West of England, Bristol
    Undergraduate Open Afternoon - Frenchay Campus Undergraduate
    Wed, 23 Jan '19
  • University of East London
    Postgraduate Open Evening Postgraduate
    Wed, 23 Jan '19
Poll
Brexit: Given the chance now, would you vote leave or remain?
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

Equations

Best calculators for A level Maths

Tips on which model to get

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.