Enrichment Practice: Mathematical Induction — Answers

Outside current Core 9758

These worked proofs are enrichment and are not part of the current required exam route.

Questions: Mathematical Induction Drills.

Question 1

For $n=1$, both sides equal $1$, so the result is true initially.

Assume that, for some positive integer $k$,

$$\sum _{r=1}^k{r}^2=\frac{k(k+1)(2k+1)}{6}.$$

Then

$$\begin{array}{rl}\sum _{r=1}^{k+1}{r}^2& =\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2\\ & =\frac{(k+1)(k+2)(2k+3)}{6}.\end{array}$$

This is the stated formula with $n=k+1$. Therefore, if the result is true for $n=k$, it is true for $n=k+1$. Since the base case holds, the result follows for every positive integer $n$ by mathematical induction.

Question 2

For $n=1$,

$$7-2=5,$$

which is divisible by $5$.

Assume that $7^k-2^k$ is divisible by $5$ for some positive integer $k$. Then

$$7^{k+1}-2^{k+1}=7(7^k-2^k)+5\cdot 2^k.$$

The first term is divisible by $5$ by the induction hypothesis, and the second term is visibly divisible by $5$. Hence $7^{k+1}-2^{k+1}$ is divisible by $5$. The result follows for every positive integer $n$ by mathematical induction.

Question 3

For $n=1$, $2^1=2=1+1$.

Assume that $2^k\ge k+1$ for some integer $k\ge 1$. Then

$$2^{k+1}=2\cdot 2^k\ge 2(k+1).$$

Since $k\ge 1$,

$$2(k+1)\ge k+2.$$

Thus $2^{k+1}\ge (k+1)+1$. The result follows for every integer $n\ge 1$ by mathematical induction.

Question 4

For $n=1$,

$$2^{1+1}-1=3=u_1.$$

Assume that $u_k=2^{k+1}-1$ for some integer $k\ge 1$. Using the recurrence,

$$u_{k+1}=2u_k+1=2(2^{k+1}-1)+1=2^{k+2}-1.$$

This is the required formula with $n=k+1$. Therefore the result holds for every integer $n\ge 1$ by mathematical induction.