HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion
  1. Mathematics
  2. /Strong Induction, Inequalities and Recursion
  3. /Inequalities by induction

Course 26.2·Lesson 1 of 3

Inequalities by induction

Induction proves inequalities too. Often the result holds only from some n0n_0n0​ on, so the base case is n0n_0n0​

Lesson 1 of 3Show all lessonsHide
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion

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 2n2^n2n bigger than n2n^2n2? Try a few values. At n=1n = 1n=1: 2>12 > 12>1. At n=2n = 2n=2: 4=44 = 44=4. At n=3n = 3n=3: 8<98 < 98<9. At n=4n = 4n=4: 16=1616 = 1616=16. At n=5n = 5n=5: 32>2532 > 2532>25. From then on 2n2^n2n wins, and it wins by more and more. Induction proves the last part.

A proof that starts at n = 5

Claim. 2n>n22^n > n^22n>n2 for every n≥5n \ge 5n≥5.

  1. Base case. 25=32>25=522^5 = 32 > 25 = 5^225=32>25=52.
  2. Hypothesis. Assume 2k>k22^k > k^22k>k2 for some k≥5k \ge 5k≥5.
  3. Step. 2k+1=2×2k>2k22^{k + 1} = 2 \times 2^k > 2k^22k+1=2×2k>2k2. We still need 2k2≥(k+1)22k^2 \ge (k + 1)^22k2≥(k+1)2.
  4. The extra fact. 2k2−(k+1)2=k2−2k−1=(k−1)2−22k^2 - (k + 1)^2 = k^2 - 2k - 1 = (k - 1)^2 - 22k2−(k+1)2=k2−2k−1=(k−1)2−2. For k≥3k \ge 3k≥3 this is at least 222, so it is positive. Our kkk is at least 555, so it holds.
  5. Conclusion. 2k+1>2k2>(k+1)22^{k + 1} > 2k^2 > (k + 1)^22k+1>2k2>(k+1)2. By induction, 2n>n22^n > n^22n>n2 for every n≥5n \ge 5n≥5.

Notice two things. The step used k≥5k \ge 5k≥5, so the base case and the step must fit together. And the step needed an extra fact about kkk, which is typical of inequalities.

Factorials beat powers

Claim. n!>2nn! > 2^nn!>2n for every n≥4n \ge 4n≥4.

  1. Base case. 4!=24>16=244! = 24 > 16 = 2^44!=24>16=24.
  2. Step. Assume k!>2kk! > 2^kk!>2k with k≥4k \ge 4k≥4. Then (k+1)!=(k+1)×k!>(k+1)×2k>2×2k=2k+1(k + 1)! = (k + 1) \times k! > (k + 1) \times 2^k > 2 \times 2^k = 2^{k + 1}(k+1)!=(k+1)×k!>(k+1)×2k>2×2k=2k+1, because k+1>2k + 1 > 2k+1>2.

Bernoulli's inequality

Claim. For every real x≥−1x \ge -1x≥−1 and every whole number n≥1n \ge 1n≥1,

(1+x)n≥1+nx.\displaystyle (1 + x)^n \ge 1 + nx.(1+x)n≥1+nx.
  1. Base case. For n=1n = 1n=1 both sides are 1+x1 + x1+x.
  2. Step. Assume (1+x)k≥1+kx(1 + x)^k \ge 1 + kx(1+x)k≥1+kx. Since 1+x≥01 + x \ge 01+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.\displaystyle (1 + x)^{k + 1} \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x.(1+x)k+1≥(1+kx)(1+x)=1+(k+1)x+kx2≥1+(k+1)x.
  1. The last step drops kx2kx^2kx2, which is never negative.

Where was x≥−1x \ge -1x≥−1 used? In multiplying by 1+x1 + x1+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(1.01)^{100} \ge 1 + 100 \times 0.01 = 2(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+122+132+⋯+1n2<2.\displaystyle 1 + \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dots + \dfrac{1}{n^2} < 2.1+221​+321​+⋯+n21​<2.

Assume the sum up to kkk is less than 222 and add 1(k+1)2\dfrac{1}{(k + 1)^2}(k+1)21​. Now we only know that the new sum is less than 2+1(k+1)22 + \dfrac{1}{(k + 1)^2}2+(k+1)21​. The step fails.

Prove instead the stronger claim: the sum up to nnn is at most 2−1n2 - \dfrac{1}{n}2−n1​. Then the step needs

2−1k+1(k+1)2≤2−1k+1,\displaystyle 2 - \dfrac{1}{k} + \dfrac{1}{(k + 1)^2} \le 2 - \dfrac{1}{k + 1},2−k1​+(k+1)21​≤2−k+11​,

which is 1(k+1)2≤1k−1k+1=1k(k+1)\dfrac{1}{(k + 1)^2} \le \dfrac{1}{k} - \dfrac{1}{k + 1} = \dfrac{1}{k(k + 1)}(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 2n2^n2n, n2n^2n2 and n!n!n! side by side. Then it finds where 3n3^n3n overtakes n4n^4n4 for good.

Read it first. Then run it. Where does 2n2^n2n pass n2n^2n2 for good? Where does n!n!n! pass 2n2^n2n?

1. Change the last line to compare 2 ** n with n ** 3. From which nnn does 2n2^n2n stay ahead?

2. Why does the function start_of reset start to None when the inequality fails? What would go wrong without it?

Common mistakes

  • Starting at n=1n = 1n=1 blindly. Many inequalities are false for small nnn. Find the right base case.
  • A step that needs more than you have. If the step needs k≥3k \ge 3k≥3, the base case must be 333 or later.
  • Multiplying by a negative number. In Bernoulli's inequality, 1+x≥01 + x \ge 01+x≥0 is what allows the multiplication.
  • Giving up when the step fails. Try a stronger statement.

Remember these

  • Base case at n0n_0n0​, step for every k≥n0k \ge n_0k≥n0​, and the step may use k≥n0k \ge n_0k≥n0​.
  • 2n>n22^n > n^22n>n2 for n≥5n \ge 5n≥5, and n!>2nn! > 2^nn!>2n for n≥4n \ge 4n≥4.
  • Bernoulli: (1+x)n≥1+nx(1 + x)^n \ge 1 + nx(1+x)n≥1+nx for x≥−1x \ge -1x≥−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.

  1. Check the base case of 3n>2n+13^n > 2n + 13n>2n+1 for n≥2n \ge 2n≥2, and prove the step.
  1. Why does the proof of 2n>n22^n > n^22n>n2 fail if you start at n=1n = 1n=1?
  1. Use Bernoulli's inequality to show that (0.95)10≥0.5(0.95)^{10} \ge 0.5(0.95)10≥0.5.
  1. Prove the step of n!>3nn! > 3^nn!>3n for large nnn. Which kkk does it need?
  1. In the stronger claim for ∑1r2\sum \dfrac{1}{r^2}∑r21​, check the case n=1n = 1n=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.
No payment. You can leave at any time.

Problems (4)

Two quantities grow with a whole number n: 3ⁿ and n³…Hard · High School (11–12) · by StemPy Lab
For a whole number n ≥ 1 let S(n) = 1/(n + 1) + 1/(n + 2) + … + 1/2n,; the sum of n fractions…Advanced · High School (11–12) · by StemPy Lab
A puzzle asks when the factorial n! = 1 × 2 × … × n overtakes the power 3ⁿ for good…Hard · High School (11–12) · by StemPy Lab
Next: lesson 2Strong induction and the well-ordering principle
← Strong Induction, Inequalities and Recursion
← PreviousStrong induction and the well-ordering principle →

Discussion (0)

Log in to join the discussion.

Loading…

and the step may use
k≥n0k \ge n_0k≥n0​
. The step compares the next quantities, for example
2k+1=2×2k>2k22^{k + 1} = 2 \times 2^k > 2k^22k+1=2×2k>2k2
, and then needs
2k2≥(k+1)22k^2 \ge (k + 1)^22k2≥(k+1)2
. Bernoulli's inequality
(1+x)n≥1+nx(1 + x)^n \ge 1 + nx(1+x)n≥1+nx
and the trick of proving a stronger statement are the main tools.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

A student wants to prove that 1 + 1/2³ + 1/3³ + … + 1/n³ < 3/2; for every n ≥ 1…Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Where an inequality starts to holdPython Lab · by StemPy Lab