Proving 3|n³-n


In this post we want to prove that \forall n \{ n \in \mathbb{N} : 3 | n^{3} - n \}.

Proof (by induction): Let P(n) be the predicate that 3 | n^{3} - n. It’s trivial to prove P(0). For the latter, we’re going to assume P(n). For this proof to work, P(n) \leftrightarrow P(n+1), so let’s examine the case P(n+1). This yields (n+1)^{3} - (n+1) \leftrightarrow n^{3} + 3n^{2} + 3n + 1 - (n+1) \leftrightarrow n^{3} + 3n^{2} + 2n \leftrightarrow (n^{3} - n) + 3n^{2} + 3n, which is divisible by three by the induction hypothesis. \blacksquare

Advertisements

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s