Question 9 of 12

Question 9 (10 marks)

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. (a) The expression $n^3+2n$ for positive integers $n$. (b) The inequality $3^n\gt n^2$ for positive integers $n$.

Find. (a) A non-inductive divisibility proof. (b) A complete induction proof.

Approach. (a) rewrite $n^3+2n$ as a product-of-consecutive-integers term plus a multiple of 3 (or case-split on $n\bmod 3$); (b) verify base case(s), then show the inductive step algebraically, checking where the step's inequality actually holds.

1. (a) $n^3+2n$ divisible by 3, without induction. Rewrite: $n^3+2n = (n^3-n)+3n = n(n-1)(n+1)+3n$. The term $3n$ is trivially divisible by 3. The term $n(n-1)(n+1)$ is the product of three consecutive integers $n-1,n,n+1$; among any three consecutive integers exactly one is a multiple of 3, so their product is always divisible by 3. Both terms are divisible by 3, hence so is their sum: $$n^3+2n = \underbrace{n(n-1)(n+1)}_{\text{div. by }3}+\underbrace{3n}_{\text{div. by }3}$$ $\boxed{3\mid n^3+2n\text{ for every positive integer }n}$ (Equivalently, case-splitting on $n\bmod 3\in\{0,1,2\}$ and reducing $n^3+2n\pmod3$ in each case gives $0$ every time — the same conclusion by direct computation.)
2. (b) Induction: $3^n\gt n^2$ for all positive integers $n$. Base case $n=1$: $3^1=3\gt 1=1^2$. True. Inductive hypothesis: assume $3^k\gt k^2$ for some $k\ge1$. Inductive step (show $3^{k+1}\gt(k+1)^2$): $$3^{k+1} = 3\cdot 3^k \gt 3k^2 \quad(\text{by the hypothesis})$$ It remains to show $3k^2\ge k^2+2k+1=(k+1)^2$, i.e. $2k^2-2k-1\ge 0$. This holds for $k\ge 2$ (at $k=2$: $8-4-1=3\ge0$, and the quadratic is increasing for $k\ge1$), but fails at $k=1$ ($2-2-1=-1\lt0$). So the inductive step is valid starting from $k=2$; check $n=2$ directly as a second base case: $3^2=9\gt4=2^2$. True. With both $n=1,2$ verified directly and the step valid for every $k\ge2$, the chain $n=2\to3\to4\to\cdots$ covers all $n\ge2$, and $n=1$ is covered by the base case: $$\boxed{3^n\gt n^2\text{ for every positive integer }n\text{ (bases }n=1,2\text{; step valid for }k\ge2)}$$