1
$\begingroup$

So I'm just studying for my midterm and I came across this exercise:

Prove by mathematical induction that $\vphantom{\Large A}3\mid\left(n^{3} - n\right)$ for every positive integer $n$.

What does the pipe symbol "$\mid$" mean? I have never seen it before.

$\endgroup$
1
  • $\begingroup$ that pipe symbol means that $3$ divides $n^3-n$... you could have at least showed what you have tried... $\endgroup$
    – user87543
    Dec 4, 2013 at 2:23

3 Answers 3

2
$\begingroup$

If $n = 1$, then $n^3 - n = 0 = 3 \times 0 $. So, result holds for the base case. Now let us suppose your statement holdsl for $n \in \mathbb{N}$. In other words, suppose

$$ n^3 - n = 3k_0 $$

We want to show $(n+1)^3 - (n+1) = 3k_1 $ for some $k_1 $.

But, Notice

$$ (n+1)^3 - (n+1) = n^3 + 3n + 3n^2 + 1 + n - 1 = n^3 - n + 3(n + n^2) + 3k_0 + 3(n + n^2) = 3(k_0 + n + n^2) \cong_3 0$$

Hence, the result follows by mathematical induction.

$\endgroup$
2
$\begingroup$

Note that in this case you have a direct proof:

$n^3-n = n(n^2-1) =n(n-1)(n+1) $ and this is the product of $3$ consecutive integers, so one of them must be divisible by $3$.

Though this is not what you asked, I find it often useful to know more than one proof of a result, because this gives me additional insights which can be useful in other situations.

As is often true, nothing about this proof is original.

$\endgroup$
2
  • 2
    $\begingroup$ Agreed. I'm disappointed when questions like this one require induction as the method of proof. $\endgroup$ Jan 5, 2016 at 13:34
  • $\begingroup$ I'm not. The point of the exercise is to teach induction. But multiple proofs of a result are always good. $\endgroup$ Jan 5, 2016 at 15:53
1
$\begingroup$

$a \vert b$ means $a$ divides $b$, i.e., $b$ is a multiple of $a$, i.e., $b = ak$, where $k \in \mathbb{Z}$.

To prove by induction, prove for $n=1$ and note that $$\left((n+1)^3 - (n+1) \right) - \left(n^3 - n\right) = \left(n^3 + 3n^2 + 3n + 1 - (n+1)\right) - n^3 + n = 3n^2 + 3n$$ Now use induction hypothesis to conclude what you want.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .