Proof by mathematical induction

Use the principle of mathematical induction to prove statements about sums, divisibility, and inequalities for all integers; communicate the base case, inductive hypothesis, and inductive step with rigour.

Proof · ME-12-01

Sub-topics

Mathematical induction

Apply the principle of mathematical induction: prove summation formulas and divisibility results by establishing a base case, assuming the result for

n = k

, and proving it for

n = k + 1

Applications and harder induction

Extend mathematical induction to inequalities, geometric series and recursive sequences; recognise when induction is the appropriate proof technique for harder problems.

Open Math

Proof by mathematical induction

Proof · ME-12-01

Name:

Date:

Mathematical induction

Q1Straightforward

Prove by mathematical induction that for all integers

n \geq 1

\sum_{k=1}^{n} k = \frac{n(n+1)}{2}

Q2Straightforward

Prove by mathematical induction that for all integers

n \geq 1

, the sum of the first

n

odd numbers equals

n^2

1 + 3 + 5 + \cdots + (2n-1) = n^2

Q3Straightforward

Prove by mathematical induction that

6^n - 1

is divisible by 5 for all integers

n \geq 1

Q4Moderate

Prove by mathematical induction that

4^n - 1

is divisible by 3 for all integers

n \geq 1

Q5Moderate

Prove by mathematical induction that for all integers

n \geq 1

\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}

Q6Moderate

Prove by mathematical induction that

n^3 + 2n

is divisible by 3 for all integers

n \geq 1

Q7Moderate

Prove by mathematical induction that for all integers

n \geq 1

\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

Q8Challenging

Prove by mathematical induction that

2^n > n

for all integers

n \geq 1

Q9Challenging

Prove by mathematical induction that

n(n+1)(n+2)

is divisible by 6 for all integers

n \geq 1

Q10Challenging

Prove by mathematical induction that

3^n > 2n

for all integers

n \geq 1

Applications and harder induction

Q11Straightforward

Prove by mathematical induction that for all integers

n \geq 1

1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1

Q12Straightforward

A sequence is defined by

a_1 = 1

and

a_{n+1} = \dfrac{a_n + 2}{2}

for

n \geq 1

. Prove by mathematical induction that

a_n = 2 - \dfrac{1}{2^{n-1}}

for all integers

n \geq 1

Q13Straightforward

Prove by mathematical induction that

n! \geq 2^{n-1}

for all integers

n \geq 1

Q14Straightforward

Prove by mathematical induction that

7 \mid (8^n - 1)

for all integers

n \geq 1

Q15Moderate

Prove by mathematical induction that for all integers

n \geq 1

\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2

Q16Moderate

Prove by mathematical induction that

2^n \geq n^2

for all integers

n \geq 4

Q17Moderate

Prove by mathematical induction that

9 \mid (4^n - 3n - 1)

for all integers

n \geq 1

Q18Moderate

Prove by mathematical induction that for all integers

n \geq 1

\sum_{k=1}^{n} \frac{1}{(2k-1)(2k+1)} = \frac{n}{2n+1}

Q19Moderate

A sequence is defined by

a_1 = 1

and

a_{n+1} = 3a_n + 4

for

n \geq 1

. Prove by mathematical induction that

a_n = 3^n - 2

for all integers

n \geq 1

Q20Challenging

Prove by mathematical induction that

(1 + x)^n \geq 1 + nx

for all integers

n \geq 1

and all real numbers

x > -1

. (This is known as Bernoulli's inequality.)

Q21Challenging

Prove by mathematical induction that

n! > 2^n

for all integers

n \geq 4

Q22Challenging

Prove by mathematical induction that for all integers

n \geq 1

\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} \geq \sqrt{n}

Worked solutions and answers at openmath.au/year-12/extension-1/proof-by-mathematical-induction