The basis step is confusing, Prove by mathematical induction that $3 | (n^3 - n)$ for every positive integer n.

Question

So I have an answer.. but the basis step doesn't make any sense to me. It is possible that I do not understand the syntax used.

Let $P(n)$ be the predicate $3 | (n^3 - n)$ for every positive integer $n$.
For $n = 1, P(1)$ is $3 | (1 - 1)$.
This can be written as $(1 - 1) = 3\cdot0$ which is clearly true.

I assume that $3\cdot 0$ mean $3*0$... but I do not understand why we are multiplying 3 with 0.

Does the pipe character mean to multiply?

Any help would be much appreciated.

Answer 1

To show that a number divides another, say n | k, we have to show that there is some m, such that nm = k (i.e. k is a multiple of n).

x | 0 holds true for all x, because we can select m=0 and show that x*0=0 and 0 is an integer. That is why you are multiplying by zero.

Answer 2

You need to show $3|(1-1)$. By definition, this means: $\exists$ some $k \in \mathbb{Z}$ with $1-1=3k$. All this is showing is that $k=0$ works.

And yes, assume "$3 . 0$" means 3 times 0.

Answer 3

Why use induction when algebra is your friend ;)

The polynomial can be rewritten as (n-1)(n)(n+1) that is the product of 3 consecutive integers. As one of them MUST be divisible by three, the product is also divisible by three :)