Question 2 of 12

Question 2

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two closed-form claims to prove by mathematical induction on the positive integer $n$.

Find. A complete induction proof of each identity/divisibility claim.

Approach. Standard weak induction: verify the base case $n=1$, assume the statement for $n=k$ (inductive hypothesis), and derive it for $n=k+1$ using only algebra.

1. a) Base case ($n=1$). LHS $=1^3=1$. RHS $=\dfrac{1^2\cdot 2^2}{4}=\dfrac{4}{4}=1$. Equal, so the base case holds.
2. a) Inductive step. Assume $\displaystyle\sum_{i=1}^{k} i^3=\frac{k^2(k+1)^2}{4}$ for some $k\geq1$. Add $(k+1)^3$ to both sides: $$\sum_{i=1}^{k+1} i^3 = \frac{k^2(k+1)^2}{4}+(k+1)^3 = \frac{(k+1)^2\big[k^2+4(k+1)\big]}{4} = \frac{(k+1)^2(k^2+4k+4)}{4} = \frac{(k+1)^2(k+2)^2}{4}$$ which is exactly the claimed formula with $n=k+1$. $\boxed{\sum_{i=1}^{n}i^3=\dfrac{n^2(n+1)^2}{4}\ \text{holds for all } n\geq1 \text{ by induction}}$
3. b) Base case ($n=1$). $9^1-2^1=7$, and $7$ is divisible by $7$. Base case holds.
4. b) Inductive step. Assume $9^k-2^k=7m$ for some integer $m$ (some $k\geq1$). Then $$9^{k+1}-2^{k+1}=9\cdot 9^k-2\cdot 2^k = 9\big(9^k-2^k\big)+\big(9-2\big)2^k = 9(7m)+7\cdot 2^k = 7\big(9m+2^k\big)$$ which is a multiple of 7. $\boxed{9^n-2^n \text{ is divisible by } 7 \text{ for all } n\geq1 \text{ by induction}}$