mjhjmtu

Please notice the following before reading: the following text is translated from Swedish and it may contain wrong wording. Also note that I am a first year student at an university - in the sense that my knowledge in mathematics is limited.

Translated text:

Example 4.4 Show that it for all integers $n$ is true that $n^3 - n$ is evenly divisible by $3$.¹

Here we are put in front of a situation with a statement for all integers and not all positive. But it is enough that we treat the cases when $n$ is non-negative, for if $n$ is negative, put $m = -n$. Then $m$ is positive, $n^3 - n = -(m^3 - m)$ and if $3$ divides $a$, then $3$ also divides $-a$.

Now here also exists a statement for $n = 0$ so that we have a sequence $p_0, p_1, p_2, ; ldots$ of statements, but that the first statement has the number $0$ and not $1$ is of course not of any higher meaning. Statement number $0$ says that $0^3 - 0$, which equals $0$, is evenly divisible by $3$, which obviously is true. If the statement number $n$ now is true, id est $n^3 - n = 3b$ for some integer $b$, then the statement number $n+1$ also must be true for

$
beginsplit
(n + 1)^3 - (n + 1) & = n^3 - n + 3n^2 + 3n \
& = 3b + 3n^2 + 3n \
& =3(b + n^2 + n)
endsplit
$

and $b + n^2 + n$ is an intege. What we was supposed to show now follows from the induction principle. $square$

1. That an integer $a$ is "evenly divisible by 3" are everyday language rather than mathematical. The precise meaning is that it exists another integer $b$ such that $a = 3b$.

In the above written text, I understanding everything (or I at least think so) except

$
beginsplit
(n + 1)^3 - (n + 1) & = n^3 - n + 3n^2 + 3n \
& = 3b + 3n^2 + 3n \
& =3(b + n^2 + n).
endsplit
$

Could someone please explain what happened, because I am totally lost?

We want to show the following proposition

$$k^3 - k textis always divisible by 3 for positive integers k tag*$$.

The set of positive integers has a special property that if some proposition, such as Proposition (*), is

1. true for the first positive integer, $n=1$ (analogy: the first domino is knocked over) and




2. true for $k=n+1$th positive integer, assuming, for the sake of argument, that the same property is true for the $k=n$th positive integer (analogy: the $n+1$th domino is knocked over, if, for the sake of argument, its predecessor, the $n$th domino, is knocked over first).

To better understand this, consider that unlike the positive integers, sets like the real numbers or $(0,1) cup 7$ don't have this special property that the positive integers do. (Analogy: We can imagine countably infinite dominoes for each of the positive integers, but can you imagine uncountably infinite dominoes for each of the numbers in $(0,1) cup 7$?)

Now, back to the positive integers. Showing $(1)$ is easy. To show $(2)$, we pretend the proposition is true for some arbitrary positive integer, say $k_n=n=7$ (The first equality reads that the $n$th positive integer is $n$. The second equality reads that $n=7$). Then, we want to show the proposition is true for the next positive integer, $k_n+1=n+1=7+1=8$.

Often this done is with considering the expression for $n+1$ and then manipulating it to come up with the expression for $n$. This can be seen in the proof in your question post and the rest of this post.

Now for your question...

Underbrace to the rescue!

1. Let's prove $beginsplit
   (n + 1)^3 - (n + 1) & = n^3 - n + 3n^2 + 3n
   endsplit$

Pf:

$$LHS = (n + 1)^3 - (n + 1) = (n + 1)^2(n+1) - (n + 1)$$

$$ = (n^2+2n+1)(n+1) - (n + 1)$$

$$ = (n^3+3n^2+3n+1) - (n + 1)$$

$$ = n^3+3n^2+3n+1 - (n + 1)$$

$$ = n^3+3n^2+3n underbrace+1 - n - 1$$

$$ = n^3+3n^2+3n overbrace- n +1 - 1$$

$$ = n^3+3n^2+3n - n +0$$

$$ = n^3+3n^2+3n - n$$

$$ = n^3 - n+3n^2+3n = RHS$$

QED

2. Let's prove $beginsplit n^3 - n + 3n^2 + 3n = 3b + 3n^2 + 3n
   endsplit$ (and understand what's going on).

Pf:

$$LHS = n^3 - n + 3n^2 + 3n$$

$$ = underbracen^3 - n_textWe assume for the sake of (inductive) argument that this is divisible by 3. + 3n^2 + 3n$$

Now, something's being divisible by $3$ means that it is a multiple of $3$, i.e. $textsomething=3b$ for some integer $b$. For example, $6$ is divisible by $3$ because $6$ is the double of $3$, i.e. $6=3b$ for $b=2$. $312$ is divisible by $3$ because $312$ is a multiple of $3$ because it is the $104$-ble of $3$, meaning $312=3b$ for $b=104$. $0$ is divisible by $3$ because $0=3b$ for $b=0$ itself. Hence, we have that

$$underbracen^3 - n_textWe assume for the sake of (inductive) argument that this is divisible by 3. + 3n^2 + 3n$$

$$=underbracen^3 - n_textWe assume for the sake of (inductive) argument that this is a multiple of 3. + 3n^2 + 3n$$

$$=underbracen^3 - n_textWe assume for the sake of (inductive) argument that this is equal to 3b, for some integer b. + 3n^2 + 3n$$

$$=overbrace3b + 3n^2 + 3n = RHS$$

3. Let's prove $3b + 3n^2 + 3n = 3(b + n^2 + n)$ (and understand what's going on).

$$LHS = 3b + 3n^2 + 3n$$

$$=underbrace3b_textHey look, this expression has a '3' in it. That means, it's a multiple of 3. + 3n^2 + 3n$$

$$=3b + underbrace3n^2_textHey look, this expression has a '3' in it. That means, it's a multiple of 3. + 3n$$

$$=3b + 3n^2 + underbrace3n_textHey look, this expression has a '3' in it. That means, it's a multiple of 3.$$

So, let's take out $3$ from all of them.

$$ =3(b + n^2 + n) = RHS$$

So, what just happened?

We assumed for the sake of argument that $n^3 - n$ is divisible by 3 and wanted to show that $(n+1)^3 - (n+1)$ is divisible by 3. Well, we were able to rewrite $(n+1)^3 - (n+1)$ as

$$(n+1)^3 - (n+1) = n^3 - n + 3n^2 + 3n$$

$$= underbracen^3 - n_textdivisible by 3 by assumption + 3n^2 + 3n$$

$$= n^3 - n + underbrace3n^2_textdivisible by 3 because it has '3' as a factor + 3n$$

$$= n^3 - n + 3n^2 + underbrace3n_textdivisible by 3 because it has '3' as a factor = (**)$$

Now, we can end here by saying that the finite sum of things that are divisible by 3 is another thing that is divisible by 3, or we don't have to take that for granted and rewrite $n^3-n$ as

$$n^3-n=3b, textfor some integer b$$

Thus,

$$(**) = underbrace3b_n^3-n + 3n^2 + 3n = (***)$$

While all the terms have a factor of 3, we're still not taking for granted that the finite sum of things that are divisible by 3 is another thing that is divisible by 3, so one last step:

$$(***) = 3(b+ n^2 + n)$$

Therefore, $(n+1)^3 - (n+1)$ is divisible by 3 assuming for the sake of argument that $n^3 - n$ is divisible by 3. Specifically, we have shown this by writing $(n+1)^3 - (n+1)$ as sum of

1. $n^3 - n$,




2. some number with 3 in it




3. some number with 3 in it

First line: Just expand the third power:
$$ (n+1)^3=(n+1)(n+1)(n+1)=n^3+3n^2+3n+1$$
(and then subtract $n+1$, of course).

Second line: We know by induction hypothesis that $n^3-n=3b$ (for some $b$)

Third line: extract the common factor $3$.

Since the $n$-th statement is assumed to be true, first it writes $n^3 - n = 3b$ because it should be divisible by $3$.

Then, for $(n+1)$-th statement, it rearranges the expression $(n+1)^3-(n+1)$ as $(n^3+3n^2+3n+1) - (n+1) = (n^3-n) + (3n^2+3n)$, then puts $3b$ in the place of $(n^3-n)$. Then it concludes that $3n^2+3n+3b$ is divisible by $3$.

Since we have assumed the $$n^3-n$$ is divisible by $3$ we can write $$n^3-n=3b$$ with $b$ is an integer number.
The proof becomes very easy if we write $$n^3-n=(n-1)n(n+1)$$