04-BS-16, Undated paper, Q8 | Nivaar Exam Prep

Question 8

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-n$. (b) the inequality $4^n>n^4$.

Find. (a) a non-inductive divisibility proof. (b) an inductive proof of $4^n>n^4$ over the correct range.

Approach. (a) factor $n^3-n$ into three consecutive integers and use the pigeonhole fact that one of any three consecutive integers is a multiple of 3. (b) test small cases first (a prerequisite for choosing a valid base case), then induct from the first $n$ where the inequality actually holds.

a) $n^3-n$ divisible by 3 (no induction). Factor: $n^3-n=n(n^2-1)=n(n-1)(n+1)=(n-1)\,n\,(n+1)$, the product of three consecutive integers. Among any three consecutive integers, exactly one is a multiple of 3 (the integers mod 3 cycle through $0,1,2$, so one of any three consecutive residues is $0$). Hence $3\mid(n-1)n(n+1)=n^3-n$ for every integer $n$, in particular every positive integer $n$. $\boxed{3\mid n^3-n}$.
b) $4^n>n^4$ for integer $n$ — check the stated range first. Testing small values: $n=3$: $4^3=64$ vs $3^4=81$ ($64<81$, false); $n=4$: $4^4=256$ vs $4^4=256$ (equal, not strictly greater); $n=5$: $4^5=1024$ vs $5^4=625$ (true). So the inequality is actually false at $n=3,4$ and only becomes and stays true from $n=5$ onward — the literal premise "for any integer $n>2$" is not correct as printed.

Check: The paper genuinely prints "for any integer $n>2$", but the statement is false there ($n=3,4$ are counterexamples, verified above). The intended statement is almost certainly the standard textbook one, "for any integer $n\ge5$" (or "$n>4$"). The corrected statement is proved below by induction starting at $n=5$.

b, corrected) Prove $4^n>n^4$ for all integers $n\ge5$, by induction. Base case $n=5$: $4^5=1024>625=5^4$. True. Inductive step: assume $4^m>m^4$ for some $m\ge5$. Then $$4^{m+1}=4\cdot4^m>4m^4.$$ It suffices to show $4m^4\ge(m+1)^4$ for $m\ge5$. Since $m\ge5$, we have $\frac{m+1}{m}=1+\frac1m\le\frac{6}{5}=1.2$, so $\left(\frac{m+1}{m}\right)^4\le1.2^4=2.0736<4$, i.e. $(m+1)^4<4m^4$. Combining, $$4^{m+1}>4m^4>(m+1)^4,$$ so the inequality holds at $m+1$. By induction, $\boxed{4^n>n^4\text{ for all integers } n\ge5}$.

Question 8 results
Part	Result
a	Proved: $3\mid n^3-n$ for all integers $n$ (factor as 3 consecutive integers)
b	"$n>2$" is false at $n=3,4$; corrected statement $4^n>n^4$ for $n\ge5$ proved by induction

Topic: Methods of proof — direct/combinatorial proof and mathematical induction.

Key relations: among any $k$ consecutive integers, exactly one is divisible by $k$; induction requires the base case to actually be the smallest case where the claim is true.

Why this works: Factoring into consecutive integers turns a divisibility claim into a pigeonhole fact about residues mod 3; testing small cases before inducting catches a false or mis-stated base range before it silently poisons a "proof" of a false statement.

Common pitfall: Attempting to induct on a statement without first checking whether the claimed base case is even true — here, blindly inducting from $n=3$ (as literally printed, "n>2") would build a syntactically valid-looking induction from a false starting point.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 4.1–4.3 (Divisibility), Ch. 5.1 (Mathematical Induction).

Question 8 of 12

Question 8