(3) Prove:

3^{n} > n^{3}

for

n \geq 4

.
Hint:

3 k^{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} + 6 k - 1$ is divisible by 9. That is, $4^{k} + 6 k - 1 = 9 m$ 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} + 6 k - 1) - 18 k + 9$ ? This is more elegant, but perhaps harder to spot without practice!