Last week we looked at examples of induction proofs: some sums of series and a couple divisibility proofs. This time, I want to do a couple inequality proofs, and a couple more series, in part to show more of the variety of ways the details of an inductive proof can be handled.
(1 + x)^n ≥ (1 + nx)
Our first question is from 2001:
Induction Proof with Inequalities 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.
Jay is right: inequality proofs are definitely trickier than others, particularly than series proofs, which tend to be fairly routine apart from the big algebraic step.
As written, the problem appears to mean what one of our problems last time meant: that the inequality is true for all real numbers x, for any non-negative integer n. If we check one case, n = 2, that looks right (the red curve is \(y=(1+x)^2\), and the blue line is \(y=1+2x\)):
But if we try n = 3, something is wrong; the red curve isn’t always above the blue line:
So we’ll have to clarify the problem.
Exploring the problem
Doctor Ian answered, demonstrating how one might think through such a problem from the start:
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 x 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).
Note that he didn’t yet check the base case; and that he isn’t yet proving anything, but rather experimenting with the goal, by stating it (a hoped-for inequality) and thinking about what has to happen for it to be true, by rewriting each side to extract from it the expression found in the n = k case.
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.
(Actually, the base case should be n = 0, as it only has to be non-negative, not positive; and the “alphas” on the two sides may not actually be equal, just in a known order.)
All of this is still informal – the sort of thing mathematicians do when they are thinking about a problem, sketching ideas for the actual work; they sweep this away when they clean up their proof for publication. Textbooks generally don’t show you this mess, and therefore can give you the impression that proofs are supposed to pop into your mind full-grown, and that if they don’t, you aren’t fit for math. Never believe that!
But he’s left the details for Jay to do, and only hinted at that issue I pointed out at the start, by saying, “show that (or explain the conditions under which) …”: As happens in real life, we will have to refine our claim before we can prove it!
He closed with a summary of how induction works:
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.
Doing the induction
Doctor Rob (having written simultaneously) joined in 9 minutes later, bringing up the details Doctor Ian omitted:
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.
How could this be determined? Our graphs above suggest it might be true for \(x \ge -3\); I made graphs for higher values of n and it looked as if \(x \ge -2\) might work. We could just make a guess like that and see what happens as we proceed with the proof.
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.
The base case is $$(1+x)^0\ge 1+0x\\1\ge 1$$
Now, assuming the induction hypothesis, that $$(1+x)^k\ge 1+kx$$ we want to prove the goal, $$(1+x)^{k+1}\ge 1+(k+1)x$$ as Doctor Ian said. Again, we can rewrite this goal (still unproved) as $$(1+x)^k\cdot(1+x)\ge 1+x+kx$$
So let’s try to derive this from the hypothesis. As noted, we can multiply both sides of an inequality by the same number as long as that number is positive. So we’d like to assume that \(1+x>0\), which we can do as long as \(x>-1\). (I think we’ve found where Doctor Rob’s restriction came from! We don’t know that this restriction can’t be loosened so that somewhat smaller x can be allowed; but we aren’t claiming to have found the “sharpest” condition for our theorem.)
So now we can say that if $$(1+x)^k\ge 1+kx$$ then $$(1+x)^{k+1}\ge (1+kx)(1+x)=1+x+kx+kx^2$$ But \(kx^2\ge 0\) for any x, so we can subtract it: $$\cdots \ge 1+x+kx$$ which was our goal.
n! ≥ n(2^n)
Next, consider this question from 2003, involving an exponential inequality:
Proof by Induction Use induction to prove: If n >= 6 then n! >= n(2^n) This is unlike all other induction problems. I get lost when I do the induction step. Base case: 6! >= 6(2^6) 720 >= 384 Induction Step: (n + 1)! >= (n + 1) (2^(n + 1)) if n! >= n*2^n
Let’s graph this one, too, just to check that \(n\ge 6\) is the appropriate condition; again, the LHS is in red (discrete dots because the factorial is only defined for integers), and the RHS is in blue:
(The dotted line is a curve that passes through all the factorial points.)
We can see that the factorials don’t start exceeding the blue curve until after n = 6.
Doctor Luis answered:
Hi Sarah, Good work establishing the base case and the induction step. I'll start you up by showing you writing down my thoughts on how I would solve this problem. If at any point while reading this, you see the solution, stop and work it out on your own, and then come back and keep reading. Given n! >= n(2^n), we have to figure out a way to make that look like (n + 1)! >= (n + 1)(2^(n + 1)).
Again, we have a hypothesis and a goal. What is changing on each side? We can start with a basic fact about factorials:
The first thing we see is that (n + 1)! = (n + 1) * n!, and this is >= n * n!, which gives us the n! for which we made the assumption. This suggests the following:
n! >= n * (2^n) (start from assumption)
n * n! >= n * n * (2^n) (multiply by n)
(n + 1)! >= n^2 * 2^n
This is a lot like the first inequality problem, isn’t it? We multiply by something positive on both sides, in order to make one side look like our goal; but in this case, he chose to multiply by n, and then increase it to n + 1 on the left, which increases the expression and maintains the inequality. (This is not the only way to approach it!)
Now he plays with the condition \(n\ge 6\), trying to change \(n^22^n\) to \((n+1)2^{n+1}\):
Now we're getting somewhere, but there's an extra n on the right side. Maybe we can do something with the inequality n >= 6.
n >= 6
n^2 >= 6n = 2 * (3n) = 2 * (n + n + n)
Hmm. That 2 may come in useful in getting us from 2^n to 2^(n + 1). Now, how does n + 1 compare with n + n + n? Eureka! n + n + n >= n + 1. You can see this from n >= 6, 2n >= 12 + 1, 3n > 1 + n.
Combining all these inequalities, you can prove the induction step.
Here is his proof, starting with the induction hypothesis:
$$n! \ge n\cdot 2^n\\(n+1)n! \ge n\cdot n! \ge n^2\cdot 2^n\ge 6n\cdot 2^n\ge 3n\cdot 2\cdot 2^n\ge (n+1)2^{n+1}$$
I see a simpler way to get the desired result, based on the common occurrence of \((n+1)\), and the fact that if \(n\ge 6\), then \(n\ge 2\):
$$n! \ge n\cdot 2^n\\(n+1)n! \ge (n+1)n\cdot 2^n\\(n+1)! \ge (n+1)n\cdot 2^n\ge (n+1)2\cdot 2^n=(n+1)2^{n+1}$$ Interestingly, this step works for values less than 6; but because the base case would fail in such cases, we can’t start there.
Let’s not forget that base case: $$6! \ge 6\cdot 2^6\\720\ge 384$$
Sum of cubes = square of sum
Turning to series, this question is from 1997:
Triangular Numbers in a Proof I am trying to prove 1^3 = 1^2 1^3 + 2^3 = (1+2)^2 1^3 + 2^3 + 3^3 = (1+2+3)^2 1^3 + 2^3 + 3^3 + ... + n^3 = (1+2+3+...+n)^2. I have tried to find a proof by induction, but didn't get very far. I also tried working with triangular numbers since the right side is the triangular numbers, but I could not show that the left and right sides were equal. I need some hints, or maybe the trick that is needed to verify the general case. I also found some patterns which turned out to lead to a dead end.
The first three lines are particular cases (the first being the base case), and can be proved by calculation. The last line is what is to be proved in general, and looks tricky, considering that there is a summation on both sides!
The triangular numbers are the sums \(1+2+3+…+n = \frac{n(n+1)}{2}\), and that formula (which we proved last week) can be useful.
Doctor Steven answered, starting with that formula and expanding it:
The right hand side is equal to [(n*(n+1))/2]^2 so you are trying to prove that the sums of the cubes of numbers is equal to (n^4 + 2n^3 + n^2)/4. Induction should work fairly well for this proof.
We’ll consider later whether that expansion was necessary; but it was easy: $$\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2(n+1)^2}{2^2}=\frac{n^2(n^2+2n+1)}{4}=\frac{n^4+2n^3+n^2)}{4}$$
So now we want to prove by induction that, for any positive integer n, $$1^3+2^3+3^3+\cdots +n^3=\frac{n^4+2n^3+n^2}{4}$$
Start with your base case of 1: (1^4 + 2*1^3 + 1^2)/4 = 1^3 = 1. Assume it's true for k: (k^4 + 2k^3 + k^2)/4 = 1^3 + 2^3 + .... + k^3. Look at k + 1: ((k+1)^4 + 2*(k+1)^3 + (k+1)^2)/4 = (k^4 + 4k^3 + 6k^2 + 4k + 1 + 2k^3 + 6k^2 + 6k + 2 + k^2 + 2k + 1)/4= (k^4 + 6k^3 + 13k^2 + 12k + 4)/4 = (k^4 + 2k^3 + k^2)/4 + (4k^3 + 12k^2 + 12k + 4)/4 = (1^3 + 2^3 + 3^3 + . . . + k^3) + (k^3 + 3k^2 + 3k + 1) = (1^3 + 2^3 + 3^3 + . . . + k^3) + (k + 1)^3 = 1^3 + 2^3 + 3^3 + . . . + k^3 + (k+1)^3. We win!
This is slightly odd, in putting the series on the right and starting on the other side; clearly this requires keeping the goal (looking like a series) in mind; but all he’s done (if I can describe expanding fourth powers as if it were easy) is to expand and simplify the formula for the next case, then split it into the formula for the assumed case plus some extras – much like Doctor Ian’s suggestion in our first example.
But I like the conclusion: “We win!” Proof is like a game, and we can celebrate at the end. That’s essentially what the traditional closing of “Q.E.D” means.
Another way
In 2001, we got another request for the same problem; Doctor Floor’s answer was added to the same page:
Hi, Madison, It is easy to check that this is correct for n = 1. Suppose that we have proven it is correct that 1^3+2^3+3^3+...+n^3 = (1+2+3+...+n)^2, which we will use as induction hypothesis. We will use the well-known identity for triangular numbers 1+2+3+...+n = n(n+1)/2
You may have noticed that some of us use a separate variable, such as k, in the induction hypothesis, while others stick with the same n used in the statement of the problem. This is a matter of taste, and also of how comfortable you are with reusing a variable within a restricted part of a proof. For beginners, it is probably better to use the k.
Then we can derive the following:
1^3+2^3+3^3+...+n^3+(n+1)^3
= (1+2+3+...+n)^2 + (n+1)^3
= (1+2+3+...+n)^2 + n(n+1)^2 +(n+1)^2
= (1+2+3+...+n)^2 + n(n+1)*(n+1) + (n+1)^2
= (1+2+3+...+n)^2 + 2(1+2+3+...+n)*(n+1) + (n+1)^2
= (1+2+3+...+n + n+1)^2
And the proof by induction is complete.
Here he never actually used the formula for the triangular numbers, much less expanded it. But he did some impressive juggling of expressions, keeping his eye, as always, on the goal. I wouldn’t be surprised if he had worked backward from the goal a little bit, in order to see better what to aim for, something like this: $$(1+2+3+…+n + (n+1))^2=((1+2+3+…+n) + (n+1))^2\\=(1+2+3+…+n)^2+2(1+2+3+…+n)(n+1)+(n+1)^2$$ using the fact that \((a+b)^2 = a^2+2ab+b^2\). Seeing the repeated \((n+1)\)’s would suggest how to pull them apart when going forward.
Sum of 2^r
We’ll close with another series problem, this time not a polynomial:
Proof by Induction What is the expression for: n ----- \ / 2 to the power of r ----- r=0 How can we prove it?
We haven’t seen this “sigma notation” for series yet; this means “the sum, for r taking integer values from 0 through n, of \(2^r\)”. In print, it looks like $$\sum_{r=0}^n 2^r=2^0+2^1+2^2+\cdots+2^n$$
Doctor Jeremiah answered, first suggesting that we can find a (hopeful) formula by looking for a pattern:
Hi Tony, Write out the sum: 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... 1 + 2 + 4 + 8 + 16 + ... The sum of the first 2 terms equals 3 and the 3rd term is 4 The sum of the first 3 terms equals 7 and the 4th term is 8 The sum of the first 4 terms equals 15 and the 5th term is 16 See the pattern? If you want to prove it I think induction is the best way.
We see that $$2^0 = 1=2^1-1\\2^0+2^1=1+2 = 3 = 2^2-1\\2^0+2^1+2^2=1+2+4 = 7 = 2^3-1\\2^0+2^1+2^2+2^3=1+2+4+8 = 15 = 2^4-1$$ So it looks like the formula may be $$\sum_{r=0}^n 2^r=2^{n+1}-1$$
After referring to one of the answers we looked at last week as an example of induction, he continued:
What we want to prove is that the sum of the first n terms is the n+1 term's value minus one. Written mathematically we are trying to prove:
n
-----
\
/ 2^r = 2^(n+1)-1
-----
r=0
Induction has three steps:
1) Prove it's true for one value.
2) Prove it's true for the next value.
The way we do step 2 is assume it's true for some arbitrary value (in this case k). We know it's true for one arbitrary value of k because of the base case. So if we can prove it's true for k+1, then we have proven it for all arbitrary values.
Three steps, or two? It’s all the same thing; what he wrote as step 2 is commonly thought of as what he will call (below) steps 2 (stating the induction hypothesis) and 3 (proving it for the next case).
Step 1: Base case n=0
n
-----
\
/ 2^r = 2^0 = 1 = 2^1 - 1 TRUE
-----
r=0
Step 2: Assume it's true for n=k
k
-----
\
/ 2^r = 2^(k+1)-1 ASSUMED
-----
r=0
Step 3: Try to prove for n=k+1
k+1
-----
\
/ 2^r = 2^((k+1)+1)-1
-----
r=0
k
-----
\
/ 2^r + 2^(k+1) = 2^(k+2)-1
-----
r=0
Here, as we’ve seen before, he is stating the goal; we need to show that these two sides are equal, using the hypothesis.
At this point we can substitute our assumption. If we prove this is true, that validates the assumption and all is fine.
2^(k+1)-1 + 2^(k+1) = 2^(k+2)-1
2*2^(k+1)-1 = 2^(k+2)-1
2^((k+1)+1)-1 = 2^(k+2)-1
2^(k+2)-1 = 2^(k+2)-1 TRUE
The assumption is true and the proof therefore is true.
He changed the LHS while rewriting the RHS each time. Let’s write it out as one chain of equalities:
We assume $$\sum_{r=0}^k 2^r=2^{k+1}-1$$ and want to show that $$\sum_{r=0}^{k+1} 2^r=2^{k+2}-1$$ And here is the proof: $$\sum_{r=0}^{k+1} 2^r=\sum_{r=0}^{k} 2^r+2^{k+1}=(2^{k+1}-1)+2^{k+1}=2\cdot 2^{k+1}-1=2^{k+2}-1$$
Next week, we’ll move on to the subject of the Fibonacci series, which is a playground for inductive proofs!
Pingback: Introducing the Fibonacci Sequence – The Math Doctors