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}$...
 A: 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))$.
A: The question "If yes, then how?" has been answered properly already. This answer only deals about the question "is induction possible here?"

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$.
A: 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.
A: 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:


*

*$P(n):3\mid (n^3-n)$

*$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$.
A: 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.
A: 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}$.
A: 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.
A: 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$$

