5
$\begingroup$

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}$...

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – WinstonCherf Dec 13 '17 at 13:52
  • 6
    $\begingroup$ 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}$. $\endgroup$ – Mathematician 42 Dec 13 '17 at 13:53
  • $\begingroup$ 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). $\endgroup$ – Bumblebee Dec 13 '17 at 13:58
  • $\begingroup$ If you want to learn more about induction then have a look at this question and its answers. $\endgroup$ – drhab Dec 13 '17 at 14:33
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you also give the proof please? $\endgroup$ – WinstonCherf Dec 13 '17 at 14:09
  • 3
    $\begingroup$ 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. $\endgroup$ – ArsenBerk Dec 13 '17 at 14:23
5
$\begingroup$

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))$.

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

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

$\endgroup$
  • 1
    $\begingroup$ @Avamander Thanks, I repaired. $\endgroup$ – drhab Dec 13 '17 at 15:34
  • $\begingroup$ 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)$ $\endgroup$ – Hagen von Eitzen Dec 13 '17 at 15:50
  • $\begingroup$ @HagenvonEitzen Thank you. I added a remark on this that refers to your comment. $\endgroup$ – drhab Dec 13 '17 at 15:53
  • 1
    $\begingroup$ 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. $\endgroup$ – tomasz Dec 13 '17 at 23:12
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ This does not answer the question. You completely missed the point of this question. $\endgroup$ – Mathematician 42 Dec 13 '17 at 14:02
  • $\begingroup$ Sorry I've extended the result. Now is it ok? $\endgroup$ – gimusi Dec 13 '17 at 14:07
  • $\begingroup$ 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. $\endgroup$ – Mathematician 42 Dec 13 '17 at 14:11
  • $\begingroup$ $\mathbb{Z}$ is countable as $\mathbb{N}$ why shouldn't it work? Isn't t it sufficient? $\endgroup$ – gimusi Dec 13 '17 at 14:18
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Mathematician 42 Dec 13 '17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.