MathematicsChapter 7: Mathematical Induction and Binomial Theorem

Principle of Mathematical Induction

To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true.

Learning objectives

State the main ideas and notation used in principle of mathematical induction.
Apply the rules of principle of mathematical induction in a clear, step-by-step solution.
Check signs, conditions, and the final answer for mathematical accuracy.

Definition

To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.

Formula

sum = k² add next odd 2k+1

Where / symbols

PRINCIPLE OF MATHEMATICAL INDUCTION: To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.
1. BASE: Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.
2. STEP: Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

Overview

Two doors, both needed:

Base

Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

Examples n=1 arithmetic · Both sides numbers · Do not skip

Step

Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

Examples Add the next term · Or multiply the next factor · End at the P(k+1) formula

WHAT — PRINCIPLE OF MATHEMATICAL INDUCTION

RULE — 1. BASE

Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

METHOD — 2. STEP

Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

WORKED EXAMPLE

Worked skeleton: sum of first n odds is n^2. P(n): 1+3+...+(2n-1)=n^2 base n=1: 1=1 assume up to k: sum = k^2 add next odd 2k+1: k^2+2k+1=(k+1)^2

How to answer a principle of mathematical induction question

Identify the given quantities, notation, and required result.
Choose the matching rule and write it before substitution.
Work one algebraic step at a time, keeping brackets and signs clear.
Check restrictions, simplify the result, and verify it where possible.

Worked example

Worked skeleton: sum of first n odds is n^2.
P(n): 1+3+...+(2n-1)=n^2
base n=1: 1=1
assume up to k: sum = k²
add next odd 2k+1: k²+2k+1=(k+1)^2

In simple words

You must do both base and step. The step alone does not start the chain.

Key points

base then step
assume P(k), prove P(k+1)
check the first n
IH = P(k)

Exam preparation

Exam Focus

Quick revision

Revision Zone

Review the key facts, formulas and checks before you move on.