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.

Advertisements