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.

Worked examples

Inequality proof (Bernoulli's inequality)

Straightforward

Problem

Prove that

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

for all integers

n \geq 1

and all

x > -1

Recursive sequence

Moderate

Problem

A sequence is defined by

a_1 = 2

and

a_{n+1} = 2a_n + 1

. Prove that

a_n = 3 \cdot 2^{n-1} - 1

for all

n \geq 1

Inequality with a non-standard base case

Challenging

Problem

Prove that

n! > 2^n

for all integers

n \geq 4

Practise

Q1·Straightforward

Prove by mathematical induction that for all integers

n \geq 1

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

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

Q2·Straightforward

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

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

Q3·Straightforward

Prove by mathematical induction that

n! \geq 2^{n-1}

for all integers

n \geq 1

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

Q4·Straightforward

Prove by mathematical induction that

7 \mid (8^n - 1)

for all integers

n \geq 1

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

Q5·Moderate

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

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

Q6·Moderate

Prove by mathematical induction that

2^n \geq n^2

for all integers

n \geq 4

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

Q7·Moderate

Prove by mathematical induction that

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

for all integers

n \geq 1

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

Q8·Moderate

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}

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

Q9·Moderate

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

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

Q10·Challenging

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.)

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

Q11·Challenging

Prove by mathematical induction that

n! > 2^n

for all integers

n \geq 4

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

Q12·Challenging

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}

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

Open Math

Applications and harder induction

Proof · ME-12-01

Name:

Date:

Q1Straightforward

Prove by mathematical induction that for all integers

n \geq 1

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

Q2Straightforward

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

Q3Straightforward

Prove by mathematical induction that

n! \geq 2^{n-1}

for all integers

n \geq 1

Q4Straightforward

Prove by mathematical induction that

7 \mid (8^n - 1)

for all integers

n \geq 1

Q5Moderate

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

Q6Moderate

Prove by mathematical induction that

2^n \geq n^2

for all integers

n \geq 4

Q7Moderate

Prove by mathematical induction that

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

for all integers

n \geq 1

Q8Moderate

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}

Q9Moderate

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

Q10Challenging

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.)

Q11Challenging

Prove by mathematical induction that

n! > 2^n

for all integers

n \geq 4

Q12Challenging

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/applications-and-harder-induction