In this post we want to prove that .
Proof (by induction): Let be the predicate that . It’s trivial to prove . For the latter, we’re going to assume . For this proof to work, , so let’s examine the case . This yields , which is divisible by three by the induction hypothesis.