Mathematical induction
Mathematical induction is a proof method to show a property holds for every integer in a range (usually all natural numbers) by proving a base case and an inductive step; it is used in engineering for proving correctness of algorithms, recurrences, and formulas for sums and combinatorial counts.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Mathematical induction is a standard way engineers prove statements that depend on an integer parameter n (for example, correctness of an algorithm for inputs of all sizes, closed forms of sums, or properties of recurrence solutions). You will use it when reasoning about loops, recursive functions, and combinatorial formulas in Computer Engineering.
Key ideas
Principle of Mathematical Induction (PMI) (exact statement used in exams): If n0 is an integer and P(n) is a proposition for integers n ≥ n0, and
- P(n0) is true (this is called the base case), and
- For every integer k ≥ n0, whenever P(k) is true then P(k+1) is true (this is the inductive step), then P(n) is true for all integers n ≥ n0.
Write this in logical form (plain Unicode):
If P(n0) ∧ (∀k ≥ n0, P(k) ⇒ P(k+1)) then ∀n ≥ n0, P(n).Why it works (sketch with well-ordering principle): The well-ordering principle says every non-empty subset of N has a least element. Suppose the set S = {n ≥ n0 | P(n) is false} is non-empty; take its least element m. By base case m ≠ n0. Then m-1 ≥ n0 and P(m-1) true (because m is least counterexample), so by the inductive step P(m) true, contradiction. So S must be empty.
Inductive hypothesis: the assumption
P(k)in the inductive step. Use it exactly as allowed: from assuming P(k) (for some fixed but arbitrary k ≥ n0) prove P(k+1).Strong induction (complete induction) (exact statement): If P(n) is a proposition for n ≥ n0 and
- P(n0) is true (sometimes several initial base cases are needed), and
- For every integer k ≥ n0, if P(n0), P(n0+1), ..., P(k) are all true then P(k+1) is true, then P(n) is true for all n ≥ n0.
In logical form:
If P(n0) ∧ (∀k ≥ n0, (∀j with n0 ≤ j ≤ k, P(j)) ⇒ P(k+1)) then ∀n ≥ n0, P(n).When to use which: use ordinary PMI when P(k) ⇒ P(k+1) is natural. Use strong induction when P(k+1) depends on several earlier values (common with recurrence relations, e.g., Fibonacci, primality factorization, tiling problems).
Common variants and reminders:
- Sometimes induction starts at n0 = 1 rather than 0. Always state the starting n0 in your answer.
- You may need more than one base case (for example, when step goes from k and k+1 to k+2 you need two bases or show both base and first step).
- Draw the domino picture in answers: draw a row of labelled dominoes n0, n0+1, n0+2,... and an arrow from each n to n+1 showing the knock-on effect. Label the knocked-first domino as base case.
Formulas
P(n0) ∧ (∀k ≥ n0, P(k) ⇒ P(k+1)) ⇒ ∀n ≥ n0, P(n) — P(n) is defined for integers n ≥ n0; no units.
P(n0) ∧ (∀k ≥ n0, (∀j with n0 ≤ j ≤ k, P(j)) ⇒ P(k+1)) ⇒ ∀n ≥ n0, P(n) — strong induction; no units.
If S ⊆ N, S ≠ ∅ ⇒ S has a least element — well-ordering principle used in proofs. Here N denotes {0, 1, 2, ...}; for domains starting at an arbitrary integer n0, apply well-ordering to the shifted set S' = {n - n0 | n ∈ S} ⊆ N.
(These are logical formulas; SI units do not apply.)
Worked examples
Example 1 — Sum of first n positive integers (standard exam question). Problem: Prove for all n ≥ 1, 1 + 2 + ... + n = n(n+1)/2.
Solution (step-by-step):
- Statement: Let P(n) be ``1 + 2 + ... + n = n(n+1)/2'' for n ≥ 1.
- Base case: n = 1. Left side = 1. Right side = 1·2/2 = 1. So P(1) true.
- Inductive hypothesis: Assume P(k) true for some k ≥ 1; that is 1 + 2 + ... + k = k(k+1)/2.
- Inductive step: Consider 1 + 2 + ... + k + (k+1). Using IH, = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2. This equals (k+1)((k+1)+1)/2, so P(k+1) true.
- Conclusion: By PMI, P(n) holds for all integers n ≥ 1.
Final answer (boxed in exam): 1 + 2 + ... + n = n(n+1)/2 for all n ≥ 1.
Example 2 — Exponential lower bound. Problem: Prove 2^n ≥ n + 1 for all integers n ≥ 0.
Solution:
- Let P(n) be
2^n ≥ n + 1for n ≥ 0. - Base case n = 0: 2^0 = 1 ≥ 0 + 1 = 1, true.
- IH: assume 2^k ≥ k + 1 for some k ≥ 0.
- Then 2^{k+1} = 2·2^k ≥ 2(k + 1) = k + 1 + (k + 1) ≥ k + 2 (since k + 1 ≥ 1). Thus 2^{k+1} ≥ k + 2 and P(k+1) true.
- Conclusion: By PMI, 2^n ≥ n + 1 for all n ≥ 0.
Example 3 — Strong induction: prime factorization existence (model answer). Problem: Prove every integer n ≥ 2 can be written as a product of primes.
Solution:
- Let P(n) be: "n is a product of primes" for n ≥ 2.
- Base case n = 2: 2 is prime, so P(2) true.
- Strong inductive hypothesis: assume for some k ≥ 2 that P(j) is true for all integers j with 2 ≤ j ≤ k.
- Consider k+1 ≥ 3. If k+1 is prime, it is trivially a product of primes (itself). If composite, k+1 = a·b with integers a, b satisfying 2 ≤ a ≤ b ≤ k. By the strong IH both a and b are products of primes, so their product is a product of primes. Thus P(k+1) holds.
- Conclusion: By strong induction, every integer n ≥ 2 is a product of primes.
Notes: This is the standard existence part of the Fundamental Theorem of Arithmetic. Uniqueness requires a separate argument.
Common mistakes
- Starting the induction at the wrong n0 (e.g., using P(0) when the statement only makes sense for n ≥ 1).
- Algebra mistakes during the inductive step (simplify carefully and show each algebraic manipulation).
- Not checking extra base cases when the inductive step requires more than one previous value (e.g., recurrence T(n) defined using T(n-1) and T(n-2)).
- Confusing proof by induction with proof by contradiction — either is allowed, but show the logical structure clearly.
For your exam
Typical question forms:
- State and prove the Principle of Mathematical Induction (short theory answer).
- Prove a formula or inequality for all n ≥ n0 (explicit base case, IH, inductive step, conclusion).
- Use strong induction to prove existence statements (prime factorization, coin problem, tiling problems).
- Trace a simple induction-like algorithm or prove loop invariants (relates to Programming/Algorithms).
What full-marks answers include:
- Clear statement of P(n) and the starting index n0.
- Correct and checked base case(s) with numerical verification.
- Clear inductive hypothesis and explanation it holds for an arbitrary k ≥ n0.
- Correct step-by-step derivation of P(k+1) from P(k) (or from earlier values in strong induction), with no hidden leaps.
- A final sentence applying PMI or strong induction to conclude P(n) holds for all n ≥ n0.
- If asked, a short proof of equivalence with well-ordering principle or explanation of when to use strong induction.
Diagrams to draw in an exam when helpful:
- A row of dominoes labelled n0, n0+1, n0+2... with the first domino knocked (base case) and arrows from each n to n+1 (inductive step). Label IH on the k-th domino when proving the step.
Quick check
- State the two parts you must prove in ordinary mathematical induction.
- Why might you prefer strong induction to ordinary induction for the statement "every integer ≥ 2 can be written as a product of primes"?
- Prove or disprove: For all n ≥ 1, n! ≥ 2^n.
Answers: 1) Base case P(n0) and inductive step: for all k ≥ n0, P(k) ⇒ P(k+1). 2) Because the step uses factorizations a·b with both factors smaller than k+1, so you need the property for all smaller integers (strong IH). 3) Disprove: counterexample n = 1 (1! = 1 < 2). The claim as stated for all n ≥ 1 is false; it becomes true for all n ≥ 4. A valid universally true variant is n! ≥ 2^{n-1} for n ≥ 1.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?