 View Question 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``` 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  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  expand the left side: 1 + 2x + x^2 >> 1 + 2x  subtract (1 + 2x) from each side: x^2 >> 0  This result is certainly true for any real x. 3. Formulate the Inductive Hypothesis (1+x)^k >> 1 + kx  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  b) Recheck the base case of the inductive step. with k = 2 the above becomes: (1+x)^(2+1) >> 1 + (2+1)x  (1+x)^3 >> 1 + 3x  expanding the left side: x^3 + 3x^2 + 3x + 1 >> 1 + 3x  subtract (3x + 1) from both sides: x^3 + 3x^2 >> 0  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  multiplying bases adds exponents: (1+x)^1 (1+x)^k >> 1 + (k+1)x  simplify the exponent of 1: (1+x)(1+x)^k >> 1 + (k+1)x  expand our right hand side: (1+x)(1+x)^k >> 1 + (k+1)x  now things can get a little tricky here showing that this is always true. multiply both sides of  by (1+x) to give: (1+x)(1+x)^k >> (1 + kx)(1+x)  multiply the right hand side of  of the above: (1+x)(1+x)^k >> 1 + kx + x + kx^2  manipulate  a bit: (1+x)(1+x)^k >> 1 + (k+1)x + kx^2  now we divert for a moment: 1 + (k+1)x + kx^2 >> 1 + (k+1)x  subtracting (1 + (k+1)x) from  yields; kx^2 >> 0  clearly  is true, and thus  is true. now, using this logic: if A > B and B > C then A > C we combine  and : (1+x)(1+x)^k >> 1 + (k+1)x + kx^2 >> 1 + (k+1)x  to arrive at being TRUE: (1+x)(1+x)^k >> 1 + (k+1)x  simplify : (1+x)^(1+k) >> 1 + (k+1)x  And voila.. we now know our inductive proposition is true! (note  is equivilent to  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  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  and , 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  to  (1+x)(1+x)^k >> 1 + (k+1)x  now things can get a little tricky here showing that this is always true. multiply both sides of  by (1+x) to give: (1+x)(1+x)^k >> (1 + kx)(1+x)  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  to  (1+x)(1+x)^k >> 1 + (k+1)x + kx^2  now we divert for a moment: 1 + (k+1)x + kx^2 >> 1 + (k+1)x  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  and  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  and carelessness the error in . 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.``` ```Ummm. I'm have an issue with  above: x^3 + 3x^2 >> 0  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  by (1+x) to give: (1+x)(1+x)^k >> (1 + kx)(1+x)  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```
 ```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  and carelessness the error in . 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.```
 ```"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.``` 