Open MathNSWGitHub ↗

Mathematical induction

Apply the principle of mathematical induction: prove summation formulas and divisibility results by establishing a base case, assuming the result for n=kn = k, and proving it for n=k+1n = k + 1.

Worked examples

Summation formula

Straightforward

Problem

Prove that ∑k=1nk=n(n+1)2\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2} for all integers n≥1n \geq 1.

Divisibility proof

Moderate

Problem

Prove that 5n−15^n - 1 is divisible by 4 for all integers n≥1n \geq 1.

Inequality proof

Challenging

Problem

Prove that 2n≥n+12^n \geq n + 1 for all integers n≥1n \geq 1.

Practise

Q1·Straightforward
Prove by mathematical induction that for all integers n≥1n \geq 1:
∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2}

✎ Work this one through on paper — proofs are self-assessed.

Q2·Straightforward
Prove by mathematical induction that for all integers n≥1n \geq 1, the sum of the first nn odd numbers equals n2n^2:
1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \cdots + (2n-1) = n^2

✎ Work this one through on paper — proofs are self-assessed.

Q3·Straightforward
Prove by mathematical induction that 6n−16^n - 1 is divisible by 5 for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.

Q4·Moderate
Prove by mathematical induction that 4n−14^n - 1 is divisible by 3 for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.

Q5·Moderate
Prove by mathematical induction that for all integers n≥1n \geq 1:
∑k=1n1k(k+1)=nn+1\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}

✎ Work this one through on paper — proofs are self-assessed.

Q6·Moderate
Prove by mathematical induction that n3+2nn^3 + 2n is divisible by 3 for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.

Q7·Moderate
Prove by mathematical induction that for all integers n≥1n \geq 1:
∑k=1nk2=n(n+1)(2n+1)6\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

✎ Work this one through on paper — proofs are self-assessed.

Q8·Challenging
Prove by mathematical induction that 2n>n2^n > n for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.

Q9·Challenging
Prove by mathematical induction that n(n+1)(n+2)n(n+1)(n+2) is divisible by 6 for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.

Q10·Challenging
Prove by mathematical induction that 3n>2n3^n > 2n for all integers n≥1n \geq 1.

✎ Work this one through on paper — proofs are self-assessed.