An Introduction to Mathematical Induction

(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!