Induction Proofs - Mathematics

Question

How do I show by mathematical induction that $2$ divides $n^2 - n$ for all $n$ belonging to the set of Natural Numbers

Answer 1

Generally, you'd prove a base case, e.g. $n=1$ that the claim is true, then state an inductive hypothesis for some $n$ and use that to prove the claim for $n+1$. This is assuming you have to use induction.

$n^2-n=n(n-1)$ and so one could note that either $n$ will be even or $n-1$ will be even and thus their product is even for a more general proof that doesn't use induction.

Answer 2

To prove this with induction (although there is a simpler way) you can proceed as follows.

For $n=1$ this is true since $2$ divides $0$. Let it be true for $n=k$ i.e. that $$2 \underbrace{\mid}_{\text{ divides }} (k^2-k)=k(k-1)$$ then for $n=k+1$ you have that $$(k+1)^2-(k+1)=k^2+2k+\not1-k-\not1=k^2-k+2k=k(k-1)+2k$$ Now, observe that $2$ divides $k(k-1)$ by the induction hypothesis and obviously $2$ divides also $2k$. Thus $2$ divides $k(k-1)+2k$ and this completes the proof by induction.

Answer 3

Normally there are three stages in a proof by mathematical induction. Here we make use of “simple” induction.

Precisely, we give a proof by induction on $n$ of the following proposition: $$ P(n):=\text{“$2$ divides $n^2-n$”}. $$

Basis for the Induction

$P(1)$ is true, since $2$ divides $1^2-1=0$ (indeed every number divides $0$).

Induction Hypothesis

Now we need to show that for all $k\in\mathbb{Z}_{\geq2}$, we have $P(k-1)\implies P(k)$ by showing that under the assumption that $P(k-1)$ is true for some $k\in\mathbb{Z}_{\geq2}$, $P(k)$ must also be true.

So this is our induction hypothesis: $$ \text{“$2$ divides $(k-1)^2-(k-1)$ for some $k\in\mathbb{Z}_{\geq2}$”}. $$

Remark. It would be totally equivalent to show that $P(k)\implies P(k+1)$ under the assumption that $P(k)$ is true for some $k\in\mathbb{Z}_{\geq1}$. Sometimes it might be easier to manipulate $+$ signs instead of $-$ signs.

Induction Step

To show that $P(k)$ is true using our induction hypothesis, we will “uncover” the expression $(k-1)^2-(k-1)$ in $k^2-k$. To do so, note that \begin{align*} (k-1)^2-(k-1)&=k^2-3k+2\\ &=(k^2-k)+(-2k+2), \end{align*} so that $$ k^2-k=(k-1)^2-(k-1)-(-2k+2). $$ By our induction hypothesis, $(k-1)^2-(k-1)$ is divisible by $2$, and clearly $-2k+2=2(-k+1)$ is also divisible by $2$. Therefore their sum is divisible by $2$, that is, $k^2-k$ is divisible by $2$. This is precisely the same as saying that $P(k)$ is true.

This completes the proof by mathematical induction.

Answer 4

I think induction can be useful for divisibility because it often allows you to reduce the polynomial you need to factorise to a lower degree polynomial:

Let's say you checked the base case, and let's call $a_n = n^2-n$. Assuming as inductive hypothesis that $a_n$ is even, it is enough to check that $a_{n+1}-a_n$ is even in order to conclude that $a_{n+1}$ is even. Let's check it:

$$a_{n+1}-a_n = (n+1)^2 - (n+1) - (n^2 - n) = 2n$$

This is even and concludes the proof by induction. Notice that I didn't need to factorise the quadratic but only a linear expression, which was easier. Don't get me wrong, I'd say factorisation is much better here than induction, but factorisation AND induction is overkill imho.