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$.1
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
$
\begin{split}
(n + 1)^3 – (n + 1) & = n^3 – n + 3n^2 + 3n \\
& = 3b + 3n^2 + 3n \\
& =3(b + n^2 + n)
\end{split}
$
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
$
\begin{split}
(n + 1)^3 – (n + 1) & = n^3 – n + 3n^2 + 3n \\
& = 3b + 3n^2 + 3n \\
& =3(b + n^2 + n).
\end{split}
$
Could someone please explain what happened, because I am totally lost?
Best Answer
We want to show the following proposition
$$k^3 - k \ \text{is 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
true for the first positive integer, $n=1$ (analogy: the first domino is knocked over) and
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!
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
Pf:
$$LHS = n^3 - n + 3n^2 + 3n$$
$$ = \underbrace{n^3 - n}_{\text{We 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. $\text{something}=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
$$\underbrace{n^3 - n}_{\text{We assume for the sake of (inductive) argument that this is divisible by 3.}} + 3n^2 + 3n$$
$$=\underbrace{n^3 - n}_{\text{We assume for the sake of (inductive) argument that this is a multiple of 3.}} + 3n^2 + 3n$$
$$=\underbrace{n^3 - n}_{\text{We assume for the sake of (inductive) argument that this is equal to 3b, for some integer b.}} + 3n^2 + 3n$$
$$=\overbrace{3b} + 3n^2 + 3n = RHS$$
$$LHS = 3b + 3n^2 + 3n$$
$$=\underbrace{3b}_{\text{Hey look, this expression has a '3' in it. That means, it's a multiple of 3.}} + 3n^2 + 3n$$
$$=3b + \underbrace{3n^2}_{\text{Hey look, this expression has a '3' in it. That means, it's a multiple of 3.}} + 3n$$
$$=3b + 3n^2 + \underbrace{3n}_{\text{Hey 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$$
$$= \underbrace{n^3 - n}_{\text{divisible by 3 by assumption}} + 3n^2 + 3n$$
$$= n^3 - n + \underbrace{3n^2}_{\text{divisible by 3 because it has '3' as a factor}} + 3n$$
$$= n^3 - n + 3n^2 + \underbrace{3n}_{\text{divisible 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, \text{for some integer b}$$
Thus,
$$(**) = \underbrace{3b}_{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
$n^3 - n$,
some number with 3 in it
some number with 3 in it