# Proof by mathematical induction in Z

Is it possible to proof the following by mathematical induction? If yes, how?

$a\in \mathbb{Z} \Rightarrow 3$ | $(a^3-a)$

I should say no, because in my schoolcarrier they always said that mathematical induction is only possible in $\mathbb{N}$. But I never asked some questions why it is only possible in $\mathbb{N}$...

• So, normally it only works on ℕ but with a "trick" you can apply it on ℤ? What do you mean with "assuming for n and proving it for n−1"? – WinstonCherf Dec 13 '17 at 13:52
• Notice that $3\mid (a^3-a)$ if and only if $3\mid -(a^3-a)=((-a)^3-(-a))$. So it suffices to prove the statement for all $a\in \mathbb{N}$. – Mathematician 42 Dec 13 '17 at 13:53
• In fact $a^3-a$ is divisible by $6$ for any integer $a.$ To prove this by induction, first prove it on $\Bbb{N}$ by induction. Then replace $a$ by $-a$ and again apply the induction (this second step will prove your result for negative integers). – Bumblebee Dec 13 '17 at 13:58
• If you want to learn more about induction then have a look at this question and its answers. – drhab Dec 13 '17 at 14:33

In this particular question, you can consider it in two separate cases, first case for $a \ge 0$ and second case for $a < 0$.

Case $a \ge 0$: We will check whether $3 | (a^3-a)$ or not by using induction on $a$. For $a = 0$, we have $3|0$. Now suppose $a \ge 1$ and for all $a$, the argument holds. Then for $a+1$, we have $$(a+1)^3-(a+1) = a^3+3a^2+2a = (a^3-a)+3a^2+3a$$ where $3|(a^3-a)$ by inductive assumption and $3|(3a^2+3a)$ obviously. Therefore, by induction, it holds for all $a \ge 0$.

Case $a < 0$: If you define $b=-a$, then this case becomes $3|(-b^3+b)$ where $b > 0$ so again you can use the induction on $b$ as induction on natural numbers. Proof for this case is similar to the first case.

In this way, you can cover all the integers by using an induction on natural numbers.

• Can you also give the proof please? – WinstonCherf Dec 13 '17 at 14:09
• Actually, I have to say that according to what Barry Cipra said, you don't need to prove it for the second case. But I really suggest you to do it just for practicing induction. – ArsenBerk Dec 13 '17 at 14:23

Technically you need to do two separate inductions. But since $(-a)^3-(-a)=-(a^3-a)$, you really only need to take the induction in the ordinary positive direction. If you do want to do both inductions, you can combine them in a single argument, along the following lines:

The base case is $3\mid0^3-0$, and

$$(a\pm1)^3-(a\pm1)=(a^3\pm3a^2+3a\pm1)-(a\pm1)=(a^3-a)\pm3a^2+3a$$

so $3\mid(a^3-a)$ implies $3\mid((a\pm1)^3-(a\pm1))$.

• Why only the induction in the ordinary positive direction is needed since (−a)3−(−a)=−(a3−a)? Can you please explain that? – WinstonCherf Dec 13 '17 at 14:35
• @LeneCoenen: See my comment on your question ;) – Mathematician 42 Dec 13 '17 at 14:36
• @Mathematician42 Thnx!! – WinstonCherf Dec 13 '17 at 14:38

Induction can be applied on a set if the set involved is equipped with a so-called well-order.

Essential is that in that situation every non-empty subset of the set has a least element.

Note that $\mathbb N$ has a very natural well-order: $0<1<2<\cdots$.

The famiar and well known order $<$ on $\mathbb Z$ is not a well-order. One of the non-empty sets that has no least element according to that order is $\mathbb Z$ itself, and there are lots of others.

This is why on school you were taught that induction was not for $\mathbb Z$.

Overlooked is there that there are well-orders on $\mathbb Z$ also.

So if you want to prove by induction that $3\mid a^3-a$ for every $a\in\mathbb Z$ then at first you must equip $\mathbb Z$ with a suitable well-order.

One (there are more) that can be used for it is:

$$0<'1<'2<'3<'\dots<'-1<'-2<'-3<'\dots$$

If $P(a)$ is true iff $3\mid a^3-a$ then it is enough to prove that:

• $P(0)$
• $P(n)\implies P(n+1)$
• $P(n)\implies P(n-1)$

I should say that it is even more than enough (see the comment of Hagen).

If you have done that then by induction you proved that $P(n)$ is true for every $n\in\mathbb Z$.

• @Avamander Thanks, I repaired. – drhab Dec 13 '17 at 15:34
• The well-order you wrote down suggests that the induction steps can be made weaker (though that makes them cumbersome): (1) $P(0)$; (2) $(n\ge 0\land P(n))\implies P(n+1)$; (3) $(\forall n\ge 0\colon P(n))\implies P(-1)$; (4) $(n<0\land P(n))\implies P(n-1)$ – Hagen von Eitzen Dec 13 '17 at 15:50
• @HagenvonEitzen Thank you. I added a remark on this that refers to your comment. – drhab Dec 13 '17 at 15:53
• The well-order you suggested does not work with standard mathematical induction. Its order type is larger than $\omega$, so you need transfinite induction, albeit only technically. – tomasz Dec 13 '17 at 23:12

The induction principle on $\mathbb{N}$ says: assuming that a property holds for $0$, and that if it holds for $n$ then it holds for $n+1$, then the property is true for all the elements of $\mathbb{N}$. The principle holds because all the elements of $\mathbb{N}$ can be reached by starting from $0$ and applying the operation $n \mapsto n+1$ a finite number of times.

Let's make this a little more abstract. Assuming that a property holds for the initial natural ($0$), and that if it holds for a natural then it also holds for the next natural ($n+1$), then it holds for all naturals.

We can generalize this to other domains than $\mathbb{N}$ by generalizing the notions of “initial” and “next”. Assume that all the elements of a set $D$ can be reached by starting from some initial element and by applying a “derivation” operation a finite number of times. Assuming that a property holds for all the initial elements, and that if it holds for an element then it also holds for a derived element, then the property holds for all the elements.

Application: all the relative integers ($\mathbb{Z}$) can be reached by starting from $0$ (the single initial element) and applying one of the operations $n \mapsto n+1$ or $n \mapsto n-1$ a finite number of times. Therefore, the following induction principle holds on $\mathbb{Z}$: assuming that a property holds for $0$, that if it holds for $n$ then it holds for $n+1$, and that if it holds for $n$ then it holds for $n-1$, then the property holds for all the elements of $\mathbb{Z}$.

Given this principle, proving the property you want is a simple modification from the proof on $\mathbb{N}$.

It's possible to generalize this further by generalizing the notion of “derivation”. An element could be derived from multiple arguments. Assume that there is a family of constructor operations $c_i : D^{a_i} \to D$, where each constructor can take a different number of parameters, such that all elements of $D$ can be reached by applying constructors. The starting point comes from constructors with 0 arguments. Then there is an induction principle on $D$ which states that, assuming that for each constructor $c_i$, if the property holds for $(x_1,\ldots,x_{a_i})$ then it holds for $P(c_i(x_1,\ldots,x_{a_i}))$, then the property holds for all the elements of $D$. The induction principle for $\mathbb{N}$ is a special case with two constructors: $0$ (with 0 arguments) and $n \mapsto n+1$ (with 1 arguments). The induction principle for $\mathbb{Z}$ adds a third constructor $n \mapsto n-1$. You could add a fourth constructor with two arguments $(p,q) \mapsto \begin{cases} p/q & \text{if }q \ne 0 \\ 0 & \text{if } q = 0 \end{cases}$ to get an induction principle for $\mathbb{Q}$.

It's possible to generalize this even further to get induction principles on “larger” spaces (which don't even need to be countable). See drhab's answer.

Technically, induction is a technique applied on the natural numbers.

However, there is nothing stopping you from having two statements applying to natural numbers that you prove seperately, but very similarily:

1. $P(n):3\mid (n^3-n)$
2. $Q(n): 3\mid ((-n)^3 - (-n))$

We can apply induction to prove $P$ and $Q$ for all natural numbers. Then, when it comes to showing that $P$ holds for all integers, we simply note that $P(n) \equiv Q(-n)$, so for any integer $k$, if it is possible, then the truth of $P(k)$ comes from the induction on $P$, while if $k$ is negative, the truth of $P(k)$ is the same as the truth of $Q(-k)$, which was proven by induction on $Q$.

Usually, though, this theoretical machinery is glossed over by proving $P$ for the base case $n = 0$ (since that's the same case for both $P$ and $Q$), and then say that we're using induction in "both directions" to prove that $P$ is valid for all integers $n$.

You can extend the induction principle to work for $\mathbb Z$. The difference is that you instead of implication in the "step" part use equivalence:

If $\phi(0)$ is true and $\forall j\in\mathbb Z: \phi(j)\leftrightarrow\phi(j+1)$ is true then $\forall j\in\mathbb Z:\phi(j)$ is true.

You can also use the normal induction principle twice. First proving it for $\mathbb N$ and then for proving the statement for $\mathbb Z^{-1}$.

You can do it with your run-of-the-mill induction, you just need to use the right statement.

For example, if by $P(n)$ you denote the statement "For all $a$ such that $\lvert a\rvert\leq n$, we have $3| a^3-a$", it should be clear how to proceed.

Since $\mathbb{Z}$ is countable as $\mathbb{N}$ we can extend induction over $\mathbb{Z}$.

BASE CASE:

$$a=1 \implies 3|0$$

INDUCTIVE STEP 1 "UPWARD"

assume: $3|a^3-a$

$$(a+1)^3-(a+1)=a^3+3a^2+3a+1-a-1=a^3-a+3a^2+3a\equiv0\pmod 3$$

thus

$$3|(a+1)^3-(a+1)$$

INDUCTIVE STEP 2 "DOWNWARD"

assume: $3|a^3-a$

$$(a-1)^3-(a-1)=a^3-3a^2+3a-1-a+1=a^3-a-3a^2+3a\equiv0\pmod 3$$

thus

$$3|(a-1)^3-(a-1)$$

Thus: $$\forall a\in \mathbb{Z} \Rightarrow 3|a^3-a$$

• This does not answer the question. You completely missed the point of this question. – Mathematician 42 Dec 13 '17 at 14:02
• Sorry I've extended the result. Now is it ok? – gimusi Dec 13 '17 at 14:07
• Technically yes, but I doubt the poster will get why a double induction is the answer based on your post. Personally, I would explain how you cover all of $\mathbb{Z}$ by a double induction. – Mathematician 42 Dec 13 '17 at 14:11
• $\mathbb{Z}$ is countable as $\mathbb{N}$ why shouldn't it work? Isn't t it sufficient? – gimusi Dec 13 '17 at 14:18
• Yes, I know that, but clearly the poster didn't. The poster had issues using induction on something which is not $\mathbb{N}$. I believe an answer should address that issue first. Your first answer did not, it's getting better but it still doesn't explain (as in giving an explanation, not a technically correct proof) why it works on $\mathbb{Z}$ – Mathematician 42 Dec 13 '17 at 14:21