Google Answers Logo
View Question
 
Q: Induction Question ( Answered,   3 Comments )
Question  
Subject: Induction Question
Category: Science > Math
Asked by: seyin-ga
List Price: $10.50
Posted: 30 Sep 2002 03:11 PDT
Expires: 30 Oct 2002 02:11 PST
Question ID: 70702
Please help me with detail instruction on how to solve this question.

Prove by induction: 
(1+x)^n >> 1 + nx 
for n a positive integer and any real number x

thank you,
SeYin
Answer  
Subject: Re: Induction Question
Answered By: mork-ga on 30 Sep 2002 04:54 PDT
 
Given that I have no knowledge of your experience in mathematics, the
following explanation may be sufficient.  If not, please ask for
clarification where you need it.  Furthermore, it is difficult to read
mathematics when confined to only using text and working strictly
top-to-bottom, so I am willing to produce a nicely written and scanned
solution if you would like.

I need to first point out that the case can not be proven as it is
incorrect!  Let's look at this example;
n = 1, this is valid as n is a positive integer.  This results in:
=> (1+x)^1 >> 1 + (1)(x)
=> 1 + x >> 1 + x

given any value for x, real or not, the two sides of this inequality
will always evaluate to be equal.  But, let's assume n must be an
integer greater than 1 and continue the inductive proof.

As can be seen at the following URL, there are 5 basic steps to a
proof by induction.
http://www.cc.gatech.edu/people/home/idris/AlgorithmsProject/ProofMethods/Induction/ProofByInduction.html

Let's examine your step-by-step.

1. State the proposition
(1+x)^n >> 1 + nx     [1]

2. Verify the base case(s)
n=0 is not valid (n must be a positive integer) and n=1 has already
been shown to fail.  Let's use n=2;
(1+x)^2 >> 1 + 2x     [2]

   expand the left side:
1 + 2x + x^2 >> 1 + 2x     [3]

   subtract (1 + 2x) from each side:
x^2 >> 0     [4]
This result is certainly true for any real x.

3. Formulate the Inductive Hypothesis
(1+x)^k >> 1 + kx     [5]
for k > 1 (integer)

4. Prove the Inductive Step
a) State the proposition of the inductive step
here we substitute k+1
(1+x)^(k+1) >> 1 + (k+1)x     [6]

b) Recheck the base case of the inductive step.
with k = 2 the above becomes:
(1+x)^(2+1) >> 1 + (2+1)x     [7]
(1+x)^3 >> 1 + 3x     [8]

   expanding the left side:
x^3 + 3x^2 + 3x  + 1 >> 1 + 3x      [8]

   subtract (3x + 1) from both sides:
x^3 + 3x^2 >> 0     [9]

This result is certainly true for any real x.

c) Restate the proposition f(k+1) in terms of a function of f(k) and
k+1

   here's our f(k+1) proposition:
(1+x)^(k+1) >> 1 + (k+1)x     [10]

   multiplying bases adds exponents:
(1+x)^1 (1+x)^k >> 1 + (k+1)x     [11]

   simplify the exponent of 1:
(1+x)(1+x)^k >> 1 + (k+1)x     [12]

   expand our right hand side:
(1+x)(1+x)^k >> 1 + (k+1)x     [13]

   now things can get a little tricky here showing that this is always
true.
   multiply both sides of [5] by (1+x) to give:
(1+x)(1+x)^k >> (1 + kx)(1+x)     [14]

   multiply the right hand side of [14] of the above:
(1+x)(1+x)^k >> 1 + kx + x + kx^2     [15]

   manipulate [15] a bit:
(1+x)(1+x)^k >> 1 + (k+1)x + kx^2     [16]

   now we divert for a moment:
1 + (k+1)x + kx^2 >> 1 + (k+1)x     [17]

   subtracting (1 + (k+1)x) from [17] yields;
kx^2 >> 0     [18]

   clearly [18] is true, and thus [17] is true.

now, using this logic:
  if   A > B   and   B > C
  then   A > C
we combine [16] and [17]:
(1+x)(1+x)^k >> 1 + (k+1)x + kx^2 >> 1 + (k+1)x     [19]

to arrive at being TRUE:
(1+x)(1+x)^k >> 1 + (k+1)x     [20]

simplify [20]:
(1+x)^(1+k) >> 1 + (k+1)x     [21]

And voila..  we now know our inductive proposition is true! (note [21]
is equivilent to [10] which is what we are trying to prove here). 
Look carefully through what just happened, we only relied on one fact
- the fact stated in [5] which we know works for our base case (some
value for k).  Since it works for that value of k (n=k=2) and we now
know it works for n=k+1, we have thus shown that it works for all k
(greater than 2 of course) - induction is beautiful!

5. State the Conclusion of the Proof
(1+x)^n >> 1 + nx 
is true for n > 2 and integer and any real number x


It's tricky, but it IS valid!  If I lost you somewhere, please ask for
clarification.  Things look messy doing all of this algebra inline and
in text only, so I am willing to produce a worked solution to scan and
place on the web for you if you would like (just ask me) which would
be much easier to read.

Good luck to you, and thanks for the question!

P.S.  Here is a course assignment with a solution to a problem very
similar to that you are seeking (see problem #17).  It skips a lot
more steps, but is the same proof (if you alter your inequality a
bit):
http://www.cs.wm.edu/~nikos/cs243/Notes/HWSol8a

Google search used:
"proof by induction"

Request for Answer Clarification by seyin-ga on 01 Oct 2002 15:14 PDT
Hi Mork-ga,

Thank You for answering my question.

But 

Will You produce a nicely written and scanned the correct solution ?

coz there're a statement saying that You made a wrong move in [9] and
[14], but I don't seem to understand of what's wrong in there. so If
You can explain a bit more and do it thoughly which I will be gladly
appreciate :)).

Thank You and just for You to know that I have really little
understanding about Math.

Thank You very much and will be waiting for Your respond,

Yenna Monica
Ps: If it's possible to give me Your email address coz I've tried to
find Your email address but couldn't find one.

Request for Answer Clarification by seyin-ga on 01 Oct 2002 19:13 PDT
Hi Mork-ga,

After looking through the answer that You gave me.

I am confuse with some of the steps.

like:
------------------------------------------------------------------------
line [13] to [14]
(1+x)(1+x)^k >> 1 + (k+1)x     [13] 
 
now things can get a little tricky here showing that this is always
true. multiply both sides of [5] by (1+x) to give: 
(1+x)(1+x)^k >> (1 + kx)(1+x)     [14] 

isn't it when we simplify this, it should becomes:
(1+x)(1+x)^k >> 1 + (xk+x)
then 
(1+x)(1+x)^k >> 1 + xk + 1 <-- here is what my opinion differ from
You.
--------------------------------------------------------------------------

another thing is line [16] to [17]
(1+x)(1+x)^k >> 1 + (k+1)x + kx^2     [16] 
 
now we divert for a moment: 
1 + (k+1)x + kx^2 >> 1 + (k+1)x     [17] 

how can this happen ??
i see that the right side come to the left side. But if that's true
which means the left side should go to the right side, but i did not
see that happening.
(1+x)(1+x)^k --> 1 + (k+1)x <-- I don't understand this.

Please explain more detailed on the step.
--------------------------------------------------------------------------------

another is:
I don't see the correct solution in here ? since steve-ga telling
about [9] and [14] there is wrong .. it is a really vague answer.

Please comment with a complete correct answer, because Your second
comments there was not helping at all.

Thank You,

seyin@hotmail.com

Clarification of Answer by mork-ga on 17 Mar 2004 14:18 PST
--- the following is rehash of old, but posted as clarification as
opposed to the comment it was posted as.

steveg is correct.  My math was quite careless there.  I got ahead of
myself in the proof and I apologize.  Rushing made me oversee the
error in [9] and carelessness the error in [14].

seyin-ga,
Sometimes proving something is difficult, but disproving it is simple.
 In order to disprove something one needs only show a case where it
fails.

The problem, as stated, fails for the case of n=1 as I had stated, 
and for many other cases as steveg points out with the example of
n=3,x=5.
Comments  
Subject: Re: Induction Question
From: steveg-ga on 30 Sep 2002 12:57 PDT
 
Ummm.  I'm have an issue with [9] above:

  x^3 + 3x^2 >> 0     [9] 
 
  This result is certainly true for any real x. 

This is true for x > -3, but not for other values of x.

Again, you get in trouble with:
  multiply both sides of [5] by (1+x) to give: 
  (1+x)(1+x)^k >> (1 + kx)(1+x)     [14] 

This isn't true when x < -1.  Multiplying and dividing by a negative number 
changes the sign of the inequalities.

Just to anchor this is simple reality,
  check (1+x)^n >> 1 + nx  
  when n=3, x=-5: 
    (1-5)^3 = -64 << 1+ 3*(-5) = -14
Subject: Re: Induction Question
From: mork-ga on 30 Sep 2002 14:56 PDT
 
steveg is correct.  My math was quite careless there.  I got ahead of
myself in the proof and I apologize.  Rushing made me oversee the
error in [9] and carelessness the error in [14].

seyin-ga,
Sometimes proving something is difficult, but disproving it is simple.
 In order to disprove something one needs only show a case where it
fails.

The problem, as stated, fails for the case of n=1 as I had stated, 
and for many other cases as steveg points out with the example of
n=3,x=5.
Subject: Re: Induction Question
From: ia-ga on 08 Oct 2002 08:21 PDT
 
"prove (1+x)^n >> 1 + nx  for n a positive integer and any real number x"

For negative x, this simply is not true (take odd n>1 and large x).
Take n=3 and x=-10, for example. Oops.

The question must be corrected to be meaningful. Probably "for 
positive real x" is what was meant.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy