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 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.
|
