Induction Proofs - Mathematics How do I show by mathematical induction that $2$ divides $n^2 - n$ for all $n$ belonging to the set of Natural Numbers
 A: 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.
A: 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.
A: 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.
A: 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.
