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
  1. Notes
  2. /Strong Induction, Inequalities and Recursion: Quick Revision
Mathematics

Strong Induction, Inequalities and Recursion: Quick Revision

A brief note on inequalities by induction, Bernoulli's inequality, strong induction, the well-ordering principle and recursive sequences, with a worked example, practice, a program and questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Strong Induction, Inequalities and Recursion. Read it before a test. Try each question at the end before you open its answer.

Inequalities

  • Base case where it starts: 2n>n22^n > n^22n>n2 only from n=5n = 5n=5; n!>2nn! > 2^nn!>2n from n=4n = 4n=4.
  • Step: compare the next terms, then prove the extra fact, such as 2k2≥(k+1)22k^2 \ge (k + 1)^22k2≥(k+1)2 for k≥3k \ge 3k≥3.
  • Bernoulli: (1+x)n≥1+nx(1 + x)^n \ge 1 + nx(1+x)n≥1+nx for x≥−1x \ge -1x≥−1 and n≥1n \ge 1n≥1.
  • Stuck step: prove a stronger statement that carries itself forward.

Strong induction and well-ordering

  • Strong induction: assume every case up to kkk, prove k+1k + 1k+1.
  • Base cases: a step that goes back rrr places needs rrr of them in a row.
  • Two stamp values aaa, bbb with no common factor: the largest amount that cannot be paid is ab−a−bab - a - bab−a−b.
  • Well-ordering: every non-empty set of positive integers has a least element. Use it with a smallest counterexample.

Recursive sequences

  • Method: list terms, guess a formula, prove it.
  • Linear rule: an+1=ran+ca_{n + 1} = ra_n + can+1​=ran​+c gives an=rn−1(a1+L)−La_n = r^{n - 1}(a_1 + L) - Lan​=rn−1(a1​+L)−L with L=cr−1L = \dfrac{c}{r - 1}L=r−1c​.
  • Fibonacci: F1+⋯+Fn=Fn+2−1F_1 + \dots + F_n = F_{n + 2} - 1F1​+⋯+Fn​=Fn+2​−1, and Fn+1Fn−1−Fn2=(−1)nF_{n + 1}F_{n - 1} - F_n^2 = (-1)^nFn+1​Fn−1​−Fn2​=(−1)n.
  • Bounded and increasing: prove each by induction, then find the limit from L=f(L)L = f(L)L=f(L).

A worked example

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

  1. Base. 4!=24>164! = 24 > 164!=24>16.
  2. Step. If k!>2kk! > 2^kk!>2k with k≥4k \ge 4k≥4, then (k+1)!=(k+1)k!>2×2k=2k+1(k + 1)! = (k + 1)k! > 2 \times 2^k = 2^{k + 1}(k+1)!=(k+1)k!>2×2k=2k+1.
  3. Conclusion. By induction, n!>2nn! > 2^nn!>2n for every n≥4n \ge 4n≥4.

Practice with new numbers

A program to try

The program tests three results of this note for many values of nnn.

Read it first. Then run it. Do all three lines say True?

1. Change the range of the first test to start at n=2n = 2n=2. What happens, and why?

Mistakes to avoid

  • Base case at 111 when the result starts later.
  • One base case for a step that goes back two or more places.
  • Multiplying an inequality by a number that may be negative.
  • Assuming a limit before showing the sequence is bounded and increasing.

Check yourself

  1. Find the smallest nnn with 2n>n22^n > n^22n>n2 for every later nnn as well.
  1. Give the Bernoulli lower bound for 1.0581.05^{8}1.058.
  1. Stamps come in 333 and 777 units. What is the largest amount that cannot be paid?
  1. Find a6a_6a6​ for a1=1a_1 = 1a1​=1 and an+1=2an+1a_{n + 1} = 2a_n + 1an+1​=2an​+1.

Sources

  • Arthur Engel, Problem-Solving Strategies, Chapter 8.
  • Richard Hammack, Book of Proof, Chapter 10.
← All Notes
← Induction for Sums and Divisibility: Quick RevisionInduction in Algebra, Calculus and Olympiad Problems: Quick Revision →
More onMathematical Induction

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. Inequalities
  2. Strong induction and well-ordering
  3. Recursive sequences
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. Sequences defined by recursionStrong Induction, Inequalities and Recursion

More notes on this topic

  1. Induction in Algebra, Calculus and Olympiad Problems: Quick Revision
  2. Induction for Sums and Divisibility: Quick Revision
All notes on this topic →