Induction

Induction

A method for proving a proposition that is valid for infinitely many different values of a variable. For example, it can be used to prove the formula 1 + 2 + 3 + 4 + . . . + n = The formula n(n+1)/2, representing the sum of integers from 1 to n. .

Proof by Induction: 1. Initial Step: demonstrate truth for initial variable value. 2. Inductive Step: if true for one value,...

Proof by induction that 1+2+3+…+n=n(n+1)/2, showing base case n=1 and inductive step assuming n=k, proving n=k+1.

See also

QED

Key Formula

\text{Base case: } P(1) \text{ is true.}

\text{Inductive step: } P(k) \implies P(k+1) \text{ for all } k \geq 1.

\text{Conclusion: } P(n) \text{ is true for all } n \geq 1.

Where:

$P(n)$ = The proposition or statement you want to prove for every natural number n
$k$ = An arbitrary natural number; you assume P(k) is true (the inductive hypothesis)
$k+1$ = The next natural number after k; you must show P(k+1) follows from P(k)

Worked Example

Problem: Prove by induction that 1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n ≥ 1.

Step 1 — State the proposition: Let P(n) be the statement that the sum of the first n positive integers equals n(n+1)/2.

P(n): \quad 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

Step 2 — Base case (n = 1): Check whether P(1) is true. The left side is just 1. The right side is 1(1+1)/2 = 1. Both sides match, so P(1) holds.

\text{LHS} = 1, \quad \text{RHS} = \frac{1 \cdot 2}{2} = 1 \quad \checkmark

Step 3 — Inductive hypothesis: Assume P(k) is true for some arbitrary natural number k. This assumption is called the inductive hypothesis.

1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}

Step 4 — Inductive step (prove P(k+1)): Add (k+1) to both sides of the assumed equation and simplify the right side to match the form of P(k+1).

\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}

Step 5 — Conclusion: The right side is exactly n(n+1)/2 evaluated at n = k+1. Since P(1) is true and P(k) implies P(k+1), by induction, P(n) is true for all n ≥ 1.

P(k+1): \quad 1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2} \quad \blacksquare

Answer: By mathematical induction, 1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n ≥ 1.

Another Example

This example proves an inequality rather than an equation, showing that induction applies to more than just summation formulas. The inductive step requires an algebraic estimation rather than direct substitution.

Problem: Prove by induction that 2^n > n for all natural numbers n ≥ 1.

Step 1 — State the proposition: Let P(n) be the statement that 2 raised to the power n is strictly greater than n.

P(n): \quad 2^n > n

Step 2 — Base case (n = 1): Check P(1): 2^1 = 2, and 2 > 1. The base case holds.

2^1 = 2 > 1 \quad \checkmark

Step 3 — Inductive hypothesis: Assume P(k) is true for some natural number k ≥ 1.

2^k > k

Step 4 — Inductive step (prove P(k+1)): Multiply both sides of the hypothesis by 2. Since k ≥ 1, we know k + 1 ≤ 2k, so the chain of inequalities closes.

2^{k+1} = 2 \cdot 2^k > 2k = k + k \geq k + 1

Step 5 — Conclusion: We have shown 2^(k+1) > k+1, which is P(k+1). By induction, 2^n > n for all n ≥ 1.

2^{k+1} > k + 1 \quad \blacksquare

Answer: By mathematical induction, 2^n > n for all natural numbers n ≥ 1.

Frequently Asked Questions

Why do you need the base case in mathematical induction?

The base case anchors the entire proof. Without it, the inductive step only says 'if one domino falls, the next one falls too,' but you never confirm that any domino actually falls. A proof missing the base case can appear to prove false statements, so always verify the starting value.

What is the difference between induction and deduction?

Mathematical induction is a specific formal proof technique for statements indexed by natural numbers. Deduction is the broader logical process of deriving conclusions from premises. Despite the name, mathematical induction is actually a form of deductive reasoning — it yields certain, not probable, conclusions.

When do you use strong induction instead of regular induction?

Use strong induction when proving P(k+1) requires assuming not just P(k) but potentially P(1), P(2), …, P(k) all at once. A classic example is proving every integer greater than 1 has a prime factorization. Strong induction and ordinary induction are logically equivalent — anything provable with one can be proved with the other — but strong induction is sometimes more convenient.

Weak (ordinary) induction vs. Strong induction

	Weak (ordinary) induction	Strong induction
Inductive hypothesis	Assume P(k) is true for one value k	Assume P(1), P(2), …, P(k) are all true
When to use	P(k+1) depends only on the immediately preceding case P(k)	P(k+1) depends on multiple or all earlier cases
Logical strength	Equivalent to strong induction	Equivalent to weak induction
Typical examples	Sum formulas, simple inequalities	Prime factorization, Fibonacci identities

Why It Matters

Mathematical induction appears throughout algebra, number theory, combinatorics, and computer science. You will encounter it when proving summation formulas, divisibility rules, inequalities, and properties of recursively defined sequences. Many standardized exams and proof-based courses treat induction as a foundational skill, making it one of the first formal proof techniques most students learn.

Common Mistakes

Mistake: Forgetting or skipping the base case

Correction: Without verifying the base case, the inductive step alone proves nothing. Always start by checking the statement for your initial value (usually n = 1 or n = 0). Skipping this step can lead to 'proofs' of false statements.

Mistake: Assuming P(k+1) is true instead of proving it

Correction: In the inductive step, you assume P(k) and must derive P(k+1) as a consequence. A common error is to write the P(k+1) formula on both sides and work toward showing they are equal — this is circular reasoning. Instead, start from one side (using the hypothesis) and algebraically arrive at the other.

Related Terms

Infinite — Induction proves statements for infinitely many values
Variable — The index n in induction is a variable
Formula — Induction commonly proves algebraic formulas
QED — Symbol used to mark the end of a proof
Sigma Notation — Summation formulas often proved by induction
Natural Numbers — Induction applies to statements over natural numbers
Recursion — Recursive definitions pair naturally with inductive proofs