Mathematical Induction
Prove a statement for all n by a base case and an inductive step.
About this topic
Mathematical induction proves that a statement holds for every positive integer. First show the base case (usually n = 1). Then assume it holds for some arbitrary k, the induction hypothesis, and prove it for k + 1.
Like toppling dominoes, the base case knocks over the first and the inductive step guarantees each one topples the next. Induction proves formulas for sums, divisibility results and inequalities, where checking individual cases could never cover infinitely many numbers.
Worked example: prove 1 + 2 + ... + n = n(n + 1)/2. Base case: n = 1 gives 1 = 1·2/2, true. Assume it holds for k. Then for k + 1, the sum is k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2, which is the formula with n = k + 1. So the statement holds for all positive integers.
Induction is used in computer science to prove that loops and recursive algorithms work. Students sometimes think the assumption step assumes what is to be proved; it only assumes the statement for one value k and then proves the next. Both steps are needed: a true inductive step with no base case proves nothing, since the dominoes never start. Write the target statement for k + 1 before simplifying so you know where you are heading.
Key ideas
- Prove it for n = 1
- Assume true for n = k
- Show it then holds for k + 1
Quick check
Use cases: where Mathematical Induction helps
- Homework: review the key idea behind Mathematical Induction before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Mathematical Induction without notes.
- Visual learning: play with the interactive lab to see how Mathematical Induction changes when you adjust its inputs.
- Teaching a friend: explain Mathematical Induction in your own words, then compare your version with the key ideas.
Number and algebra skills are used in science, engineering, budgeting and computing.
Frequently asked questions
What is Mathematical Induction?
Prove a statement for all n by a base case and an inductive step.
What will I learn in Mathematical Induction?
Prove it for n = 1. Assume true for n = k. Show it then holds for k + 1.
Is Mathematical Induction part of Mathematics?
Yes. It is one of 200 Mathematics topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Mathematical Induction lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Mathematical Induction?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.