Mathematical Induction

Introduction

Mathematical induction is a rigorous method for proving that a statement is true for every integer from a chosen starting value onward. It is especially useful when a statement depends on a natural-number index such as $n$ . In Grades 11–13, induction connects algebra, number theory, sequences, inequalities, recursion, and formal proof.

The central idea is not to check infinitely many cases one by one. Instead, you prove a starting case and then prove that every valid case forces the next one to be valid. When both parts are established for all relevant indices, the result follows for the entire sequence of integers.

A domino-effect visualization: the first successful step and a reliable next-step rule create an unbroken logical chain.

The MIT OpenCourseWare lecture above places mathematical induction in the wider context of sets, logic, and proof writing.

Learning Objectives

By the end of this aiMOOC, you should be able to explain why mathematical induction is a deductive proof method, identify the base case and inductive step, write complete induction proofs, detect common logical errors, use strong induction when several earlier cases are needed, and apply induction to sums, divisibility, inequalities, recurrences, and recursively defined structures.

The Core Principle

Suppose $P (n)$ is a statement defined for every integer $n \geq n_{0}$ . The principle of mathematical induction says that $P (n)$ is true for every $n \geq n_{0}$ if you establish both of the following facts:

Base case: Prove $P (n_{0})$ .
Inductive step: Prove that for every integer $k \geq n_{0}$ , if $P (k)$ is true, then $P (k + 1)$ is true.

The temporary assumption that $P (k)$ is true is called the induction hypothesis. You may use it only inside the inductive step and only under the condition that the index $k$ is an arbitrary admissible integer.

This induction diagram emphasizes the starting case, the induction hypothesis, and the transition to the successor case.

The logical structure can be written as $P (n_{0}) \land (\forall k \geq n_{0}, P (k) \Rightarrow P (k + 1)) \Rightarrow \forall n \geq n_{0}, P (n) .$

Why Induction Works

The domino analogy is useful, but the mathematical reason is logical rather than physical. Imagine that the conclusion were false even though the base case and inductive step were both correct. Then there would be at least one counterexample. Because the relevant indices are integers bounded below by $n_{0}$ , the well-ordering principle gives a least counterexample $m$ .

The least counterexample cannot be $n_{0}$ , because the base case has already been proved. Therefore $m - 1$ is an allowed earlier index and cannot be a counterexample. So $P (m - 1)$ is true. The inductive step then forces $P (m)$ to be true, contradicting the choice of $m$ . This shows the close relationship between induction and the well-ordering principle.

Important distinction: mathematical induction is not the same as informal inductive reasoning. Observing many examples may suggest a conjecture, but it does not prove a universal statement. Mathematical induction is a deductive argument: once its premises are proved, the conclusion follows necessarily.

Writing an Induction Proof

A clear proof normally follows a disciplined structure:

State the proposition: Write exactly what $P (n)$ means and specify the starting index.
Base case: Substitute the starting value and verify the claim.
Induction hypothesis: Let $k$ be an arbitrary allowed integer and assume $P (k)$ .
Inductive step: Starting from the expression or statement for $k + 1$ , use valid algebra, definitions, and the induction hypothesis to prove $P (k + 1)$ .
Conclusion: State that the claim follows for all integers in the specified domain by mathematical induction.

A good inductive step makes the dependence on the hypothesis visible. If your argument never uses the hypothesis, check whether induction is actually needed or whether you have silently assumed the result you are trying to prove.

Worked Example: Sum of the First Natural Numbers

Claim: For every integer $n \geq 1$ , $1 + 2 + \dots + n = \frac{n (n + 1)}{2} .$

Base case: For $n = 1$ , the left side is $1$ and the right side is $\frac{1 \cdot 2}{2} = 1$ . So the claim is true at the starting value.

Induction hypothesis: Assume that for some arbitrary integer $k \geq 1$ , $1 + 2 + \dots + k = \frac{k (k + 1)}{2} .$

Inductive step: Add the next term: $1 + 2 + \dots + k + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = (k + 1) (\frac{k}{2} + 1) = \frac{(k + 1) (k + 2)}{2} .$ This is exactly the claimed formula with $n = k + 1$ .

Conclusion: The formula holds for every integer $n \geq 1$ .

The practice video above develops several induction examples and can be used after you have written the proof yourself.

Worked Example: Divisibility

Claim: For every integer $n \geq 1$ , the number $7^{n} - 1$ is divisible by $6$ .

Base case: For $n = 1$ , $7^{1} - 1 = 6$ , which is divisible by $6$ .

Induction hypothesis: Assume $7^{k} - 1$ is divisible by $6$ . Then there is an integer $m$ such that $7^{k} - 1 = 6 m$ .

Inductive step: $7^{k + 1} - 1 = 7 \cdot 7^{k} - 1 = 7 (7^{k} - 1) + 6 = 7 (6 m) + 6 = 6 (7 m + 1) .$ Because $7 m + 1$ is an integer, $7^{k + 1} - 1$ is divisible by $6$ .

Conclusion: The divisibility statement holds for every integer $n \geq 1$ .

Worked Example: Inequality

Claim: For every integer $n \geq 0$ , $2^{n} \geq n + 1.$

Base case: At $n = 0$ , $2^{0} = 1$ and $0 + 1 = 1$ .

Induction hypothesis: Assume $2^{k} \geq k + 1$ for an arbitrary integer $k \geq 0$ .

Inductive step: $2^{k + 1} = 2 \cdot 2^{k} \geq 2 (k + 1) = 2 k + 2.$ Since $k \geq 0$ , we have $2 k + 2 \geq k + 2$ . Therefore $2^{k + 1} \geq k + 2$ , which is the desired statement for the successor index.

The Khan Academy lesson above focuses specifically on proving inequalities by mathematical induction.

Strong Induction

In strong induction, the induction hypothesis assumes that all cases from the starting value through $k$ are true, and you use those assumptions to prove the case $k + 1$ . The method is logically equivalent in strength to ordinary induction, but it is often more natural when the next case depends on several earlier cases.

A standard example is prime factorization. To prove that every integer $n \geq 2$ is a product of primes, begin with $2$ , which is prime. Assume every integer from $2$ through $k$ is a product of primes. For $k + 1$ , either it is prime, or it is composite. In the composite case, write $k + 1 = a b$ with $2 \leq a, b \leq k$ . By the strong induction hypothesis, both $a$ and $b$ are products of primes, so $k + 1$ is also a product of primes.

Strong induction is especially useful for recurrence relations, factorization arguments, tiling problems, and algorithms that reduce a problem to several smaller subproblems.

Induction and Recursively Defined Objects

Induction is not limited to statements indexed by a single integer. In computer science and discrete mathematics, recursively defined strings, expressions, trees, and formulas can be handled by structural induction. You prove the property for the basic objects, then prove that each construction rule preserves the property.

An inductive proof on strings illustrates how the same base-and-construction logic extends beyond simple numerical formulas.

For example, if a set of expressions is built from basic symbols and a rule for combining expressions, a structural induction proof first checks each basic symbol and then shows that combining expressions that already have the desired property produces a new expression with the same property.

The discrete mathematics video above connects induction with proof techniques used in number theory and set-based arguments.

Deeper Connections

Mathematical induction is closely related to recursive definitions. The natural numbers themselves can be described using a starting element and a successor operation. Many algebraic properties of addition and multiplication can then be developed by induction from recursive definitions.

This exercise-oriented diagram links recursive definitions of addition and multiplication with inductive proofs of familiar algebraic properties.

Induction also appears in combinatorics, graph theory, algorithm correctness, complexity estimates, identities involving sequences, and proofs about finite structures. Learning induction therefore strengthens both algebraic technique and general proof design.

Common Errors and How to Avoid Them

Missing the base case: An inductive step by itself does not start the chain. A statement could satisfy a next-step implication without ever being true at the required starting value.

Using a non-arbitrary index: The induction variable $k$ must represent an arbitrary allowed integer. Checking the step only for a few selected values does not prove the universal implication.

Assuming the successor case: The induction hypothesis gives you $P (k)$ , not $P (k + 1)$ . If you assume what you are supposed to prove, the argument is circular.

Proving the wrong direction: Showing $P (k + 1) \Rightarrow P (k)$ does not replace the required forward implication.

Changing the statement midway: Sometimes the original claim is too weak to support the inductive step. In that situation, strengthen the proposition deliberately and prove the stronger statement rather than silently adding an extra assumption.

Ignoring the domain: A proof that starts at $n = 5$ proves a claim only from $5$ onward unless smaller cases are handled separately.

Strategy Guide

Before beginning an induction proof, ask yourself four questions. What is the exact proposition? What is the first allowed index? What information will the successor case need from earlier cases? What algebraic or structural transformation exposes the induction hypothesis?

For sums, separate the final term. For products or powers, factor the successor expression so that the hypothesis appears. For divisibility, rewrite the hypothesis as an integer multiple. For inequalities, preserve the direction of inequalities and justify every comparison. For recurrences, consider whether strong or simultaneous induction is more natural.

A useful habit is to write the successor target before doing algebra. If the goal is a formula $F (n)$ , write down $F (k + 1)$ explicitly. This reduces index errors and makes the intended destination of the inductive step clear.

Interactive Tasks

Quiz: Test Your Knowledge

What must be proved first in a standard induction argument? (The statement is true at the starting value) (!The statement is true for one large value) (!The statement is false for no tested examples) (!The successor case is assumed without proof)

What is the role of the induction hypothesis? (It temporarily assumes the claim for an arbitrary current index) (!It proves every case before the base case) (!It replaces the need for an inductive step) (!It allows the successor case to be assumed directly)

Which implication is required in ordinary mathematical induction? (The current case implies the next case) (!The next case implies the current case) (!One selected case implies every earlier case) (!The base case implies only one chosen distant case)

Why is checking many numerical examples not a proof of a universal claim? (A later untested value could still be a counterexample) (!Numerical examples can never support a conjecture) (!Universal claims are always false) (!Only geometric arguments count as proofs)

When is strong induction especially useful? (When the next case depends on several earlier cases) (!When no base case can be identified) (!When the claim concerns only one isolated number) (!When the induction hypothesis must be avoided)

In a divisibility proof, what is a useful way to express the induction hypothesis? (Write the relevant expression as an integer multiple of the divisor) (!Replace the divisor with a decimal approximation) (!Assume the successor expression is already divisible) (!Test only prime values of the index)

What does a valid inductive conclusion establish? (The proposition holds for every integer in the stated domain) (!The proposition holds only for the base case) (!The proposition is probably true for large values) (!The proposition holds for real numbers automatically)

What is wrong with proving only that the next case implies the current case? (It is the reverse of the forward implication required for induction) (!It automatically proves strong induction instead) (!It makes the base case unnecessary) (!It proves every integer less than zero)

What should you do if the original statement is too weak to support the inductive step? (Formulate and prove a deliberately stronger proposition) (!Assume an extra fact without stating it) (!Skip the inductive step) (!Check more examples and stop)

What is structural induction designed to prove properties about? (Objects generated by recursive construction rules) (!Only decimal expansions) (!Only continuous real functions) (!Only experimentally measured data)

Memory Game

Base case	Verification of the first value in the stated domain
Induction hypothesis	Temporary assumption that the current arbitrary case is true
Inductive step	Argument that carries truth from an allowed case to its successor
Successor	The next integer after the current index
Strong induction	Method that may use all earlier established cases
Counterexample	One valid input for which a universal claim fails
Recurrence	Definition in which later terms depend on earlier terms

Drag and Drop

Match the correct terms.	Topic
Verify the starting value	Base case
Assume the arbitrary current case	Induction hypothesis
Transform the successor expression	Inductive step
Use all established smaller cases	Strong induction
Search for a failing input	Counterexample

...

Crossword Puzzle

Induction	Which proof method links a starting case to successive cases?
Successor	What is the next integer after a given index called?
Hypothesis	What temporary assumption is used in the inductive step?
Divisibility	Which number-theory property asks whether one integer divides another exactly?
Recurrence	What rule defines later sequence terms from earlier terms?
Counterexample	What single failing case disproves a universal statement?

LearningApps

Cloze Text

Mathematical induction begins by proving a

. The temporary assumption for an arbitrary current index is the

. The main transition proves that the current case implies the

. A universal claim can be disproved by one

. When the next case depends on several earlier cases,

is often convenient. The well-ordering principle guarantees that a nonempty set of natural-number counterexamples would have a

. In a divisibility proof, it is useful to rewrite an expression as an integer

. Structural induction applies to objects created by

.

Open-Ended Tasks

Easy

Domino effect: Create a one-page visual explanation showing how the base case and inductive step correspond to a chain of dominoes, and add one sentence explaining where the analogy stops being literal.
Arithmetic series: Derive and prove by induction a formula for the sum of the first n odd positive integers, then verify your formula with three small values.
Proof writing: Rewrite a short informal induction argument into a formal proof with proposition, base case, induction hypothesis, inductive step, and conclusion.
Mathematical communication: Record a two-minute video in which you explain to a classmate why testing many examples is different from proving a universal statement.

Standard

Divisibility: Choose a divisibility pattern involving powers, formulate it precisely, test examples to create a conjecture, and then prove or disprove the conjecture by induction.
Geometric series: Prove the finite geometric-series formula by induction and annotate each algebraic transformation with the reason it is valid.
Inequality: Find an exponential-versus-linear inequality that becomes true from some starting index, identify the correct base case, and prove it by induction.
Interview: Interview a mathematics teacher, programmer, engineer, or university student about where recursive thinking or proof by induction appears in their work, then summarize the connection.

Advanced

Strong induction: Develop a proof that every integer greater than one can be written as a product of primes, and explain why the strong hypothesis is natural for the composite case.
Recurrence relation: Choose a recurrence such as a Fibonacci-type sequence, conjecture a bound or divisibility property, and prove it using strong or simultaneous induction.
False proof: Construct or research a flawed induction proof, pinpoint the exact invalid step, and produce a corrected explanation that would prevent the error.
Well-ordering principle: Write a proof that derives mathematical induction from the least-counterexample idea, then compare its logic with the domino analogy.

Learning Assessment

Proof design: Given a new summation identity, identify the proposition, choose the starting index, and produce a complete induction proof in which every use of the hypothesis is explicitly marked.
Error analysis: Analyze a flawed induction argument, classify the error as a base-case, domain, implication, algebra, or circularity problem, and repair the proof.
Method selection: Compare ordinary induction, strong induction, and direct proof for three statements, then justify which method is most efficient for each.
Transfer to algorithms: Explain how an induction proof can establish the correctness of a recursive algorithm by connecting smaller inputs to the next larger input.
Conjecture evaluation: Use numerical evidence to form a conjecture, then decide whether induction can prove it and explain what additional structure is required.
Conceptual reasoning: Use the least-counterexample argument to explain why a correct base case together with a correct inductive step leaves no first place where the proposition can fail.

Evidence of Learning

Knowledge: You can state the principle of mathematical induction, distinguish ordinary and strong induction, and explain the relationship to well-ordering and recursion.
Skills: You can choose a valid starting index, formulate an induction hypothesis, execute a successor step, control algebraic transformations, and detect circular reasoning.
Products: You can produce complete written proofs, annotated examples, explanatory diagrams, short videos, interviews, and error analyses.
Reasoning: You can justify why each part of an induction proof is necessary and explain why finite testing cannot replace universal proof.
Transfer: You can apply induction to unfamiliar sums, inequalities, divisibility claims, recurrences, algorithms, and recursively defined structures.

OERs on the Topic

The English Wikipedia article below provides an open reference on the definition, examples, variants, formalization, and history of mathematical induction.

Linked Learning Areas

Mathematical induction combines logical implication, algebraic manipulation, natural-number structure, recursive definitions, and proof communication. It connects school algebra with more advanced topics in number theory, discrete mathematics, computer science, combinatorics, and analysis.

Mathematical induction

aiMOOC Projects

Diesen aiMOOC als Battle spielen: Mathematik, Klasse 11-13, G-Niveau

Inhalte werden geladen ...

Mediathek wird aus dem Wiki geladen ...

Frag mich zum aktuellen Lerninhalt oder wähle eine kurze Hilfe.

Textmodus bereit

Sprache

English:Mathematical Induction