Induction proves inequalities too. Often the result holds only from some n0 on, so the base case is n0
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
prove an inequality by induction from the right base case;
prove and use Bernoulli's inequality;
make a statement stronger so that the step works.
Which grows faster?
Is 2n bigger than n2? Try a few values. At n=1: 2>1. At n=2: 4=4. At n=3: 8<9. At n=4: 16=16. At n=5: 32>25. From then on 2n wins, and it wins by more and more. Induction proves the last part.
A proof that starts at n = 5
Claim.2n>n2 for every n≥5.
Base case.25=32>25=52.
Hypothesis. Assume 2k>k2 for some k≥5.
Step.2k+1=2×2k>2k2. We still need 2k2≥(k+1)2.
The extra fact.2k2−(k+1)2=k2−2k−1=(k−1)2−2. For k≥3 this is at least 2, so it is positive. Our k is at least 5, so it holds.
Conclusion.2k+1>2k2>(k+1)2. By induction, 2n>n2 for every n≥5.
Notice two things. The step used k≥5, so the base case and the step must fit together. And the step needed an extra fact about k, which is typical of inequalities.
Factorials beat powers
Claim.n!>2n for every n≥4.
Base case.4!=24>16=24.
Step. Assume k!>2k with k≥4. Then (k+1)!=(k+1)×k!>(k+1)×2k>2×2k=2k+1, because k+1>2.
Bernoulli's inequality
Claim. For every real x≥−1 and every whole number n≥1,
(1+x)n≥1+nx.
Base case. For n=1 both sides are 1+x.
Step. Assume (1+x)k≥1+kx. Since 1+x≥0, we may multiply both sides by it without turning the inequality round:
(1+x)k+1≥(1+kx)(1+x)=1+(k+1)x+kx2≥1+(k+1)x.
The last step drops kx2, which is never negative.
Where was x≥−1 used? In multiplying by 1+x. With a negative factor the inequality would turn round. This is the trap in many exam questions.
A use.(1.01)100≥1+100×0.01=2. A one-line lower bound for a power that is hard to work out by hand.
Make it stronger
Sometimes a true statement cannot be proved directly by induction, but a stronger one can. Take
1+221+321+⋯+n21<2.
Assume the sum up to k is less than 2 and add (k+1)21. Now we only know that the new sum is less than 2+(k+1)21. The step fails.
Prove instead the stronger claim: the sum up to n is at most 2−n1. Then the step needs
2−k1+(k+1)21≤2−k+11,
which is (k+1)21≤k1−k+11=k(k+1)1. That is true. The stronger claim carries itself forward, and it gives the original one.
Practise with new numbers
Try it in Python
The program prints 2n, n2 and n! side by side. Then it finds where 3n overtakes n4 for good.
Common mistakes
Starting at n=1 blindly. Many inequalities are false for small n. Find the right base case.
A step that needs more than you have. If the step needs k≥3, the base case must be 3 or later.
Multiplying by a negative number. In Bernoulli's inequality, 1+x≥0 is what allows the multiplication.
Giving up when the step fails. Try a stronger statement.
Remember these
Base case at n0, step for every k≥n0, and the step may use k≥n0.
2n>n2 for n≥5, and n!>2n for n≥4.
Bernoulli: (1+x)n≥1+nx for x≥−1.
If the step fails, prove something stronger.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Check the base case of 3n>2n+1 for n≥2, and prove the step.
Why does the proof of 2n>n2 fail if you start at n=1?
Use Bernoulli's inequality to show that (0.95)10≥0.5.
Prove the step of n!>3n for large n. Which k does it need?
In the stronger claim for ∑r21, check the case n=1.
References
Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle, and Chapter 7, Inequalities.
Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical Induction.
Enroll free in Strong Induction, Inequalities and Recursion
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.