Copyright © University of Cambridge. All rights reserved.
'An Introduction to Mathematical Induction' printed from https://nrich.maths.org/
(3) Prove: $3^n> n^3$ for $n\geq 4$.
Hint: $3k^3 - (k+1)^3 = (k-1)^3 + k(k^2-6)$
(4) The left-hand side is the number of ways of choosing $r$ balls
from $n+1$. Suppose one ball is coloured blue (and the others
aren't). Now explain why the right-hand side is the number of ways
of picking $r$ balls including the blue one plus the number of ways
of picking $r$ balls excluding the blue one.
(5) OK, this isn't true. But the inductive step works. So what's
gone wrong? It's not true for $n=1$. This is why it's absolutely
vital that you check the starting point!
(6) The inductive hypothesis is that $4^k + 6k - 1$ is divisible by
9. That is, $4^k+6k-1=9m$ for some integer $m$. Now use this to get
an expression for $4^k$ that you can substitute into
$4^{k+1}+6(k+1)-1$. Alternatively, what is $4(4^k+6k-1)-18k+9$?
This is more elegant, but perhaps harder to spot without
practice!