Induction Proof with Inequalities
Date: 07/03/2001 at 10:37:21 From: Jay Krueger Subject: Math Induction Hello, I've been trying to solve a problem and just really don't know if my solution is correct. I have a really hard time doing these induction problems when inequalities are involved. I was hoping you could help me solve this. The question is this: Prove by induction that (1 + x)^n >= (1 + nx), where n is a non-negative integer. Thank you for your time.
Date: 07/03/2001 at 15:59:30 From: Doctor Ian Subject: Re: Math Induction Hi Jay, Let's _assume_ that it holds for n = k. That is, for some k, it's true that (1+x)^k >= (1 + kx) What happens for the next value of n, i.e., n = (k+1)? (1+x)^(k+1) >= (1 + (k+1)x) >= (1 + kx + x) >= (1 + kx) + x So increasing the value of n by 1 adds s to the right side of the inequality. What does it do to the left side? (1+x)^(k+1) >= (1 + kx) + x (1+x)^k * (1+x) >= So increasing the value of n by 1 multiplies the left side of the equation by (1+x). Now there are two things left to do. The first is to show that (or explain the conditions under which) something multiplied by (1+x) is greater than the same thing plus x: alpha * (1+x) >= alpha + x Once you've done that, you need to show that the inequality holds for the smallest value of n (in this case, n = 1), (1+x)^1 >= (1 + 1x) which should be pretty easy to do. The general idea is to show that if it works for n = k, then it also works for n = k+1; and then to show that it works for n = 1. (Since it works for n = 1, it must also work for n = 2; and since it works for n = 2, it must also work for n = 3; and so on.) And usually it works just the way it did here: You substitute k+1 for k in both sides, and then try to figure out what _change_ occurs as a result of the substitution, which you do by trying to recover the original form for k, with some extra stuff hanging off it: k k+1 --------- --------------- (1+x)^k -> (1+x)^k * (1+x) (1+kx) -> (1+kx) + x ^ ^ | | original extra form stuff Then you can forget about comparing the original forms, and concentrate on comparing the extra stuff, which is usually easier. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 07/03/2001 at 16:08:14 From: Doctor Rob Subject: Re: Math Induction Thanks for writing to Ask Dr. Math, Jay. You will need a condition on x for this to work. It is false for x = -11 and n = 3, for example. One condition under which this is true for all nonnegative integers n is x >= -1. The basis of the induction is n = 0, which you can verify directly is true. Now assume it is true for some value of n. Now if (1+x) is nonnegative, you can multiply both sides by (1+x) to get the left side in the correct form. Expand the right-hand side, and rearrange it into the form (1+x)^(n+1) >= 1 + (n+1)*x + n*x^2. Observe that if you leave out the n*x^2 term, you get something equal or smaller, because n >= 0 and x^2 >= 0 for all real x. I leave the rest to you. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.