Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Question

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$.

That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive integer.

I've tried the following: $$\begin{split} (n+1)^2 − (n+1) &= (n+1)(n+1) - (n+1)\\ &=(n+1)(n-1)+2 - (n+1)\\ &=n^2 +n -n -1 +2 -n -1\\ &=n^2 -n, \end{split}$$ but I'm not particularly good at maths so I have no idea if this is even correct, and if it is, what it even means.

Answer 1

Comment: As others have mentioned a number of times, induction is not at all necessary in this particular problem, but I am sure you hear that loud and clear by now. You probably just want to see how an induction proof would look. I've sketched out a proof below, but before you read it, I would encourage you to take a look at this post on how to write a clear induction proof. I imagine it would help you a good bit in both understanding how to write up your induction proofs clearly but also constructing your proofs. Following the instructions in that link will force you to understand your problem. That being said, see if you can follow the proof below (feel free to leave a comment if a point does not make sense).

---

For any positive integer $n$, let $S(n)$ denote the statement $$ S(n) : 2\mid (n^2-n). $$

Base step: For $n=1, S(1)$ gives $1^2-1 = 0$, and $2$ divides zero. Thus, $S(1)$ holds.

Inductive step: Let $k\geq 1$ be fixed, and suppose that $S(k)$ holds; in particular, let $\ell$ be an integer with $2\ell = k^2-k$. Then \begin{align} [(k+1)^2-(k+1)]&= (k^2+2k+1)-(k+1)\tag{expand}\\[0.5em] &= (k^2-k)+2k\tag{rearrange/simplify}\\[0.5em] &= 2\ell+2k\tag{by ind. hyp.}\\[0.5em] &= 2(\ell+k)\tag{factor out $2$}\\[0.5em] &= 2\eta\tag{$\eta=\ell+k. \eta\in\mathbb{Z}$} \end{align} This proves $S(k+1)$ and concludes the inductive step $S(k)\to S(k+1)$.

By mathematical induction, for each $n\geq 1$, the statement $S(n)$ is true. $\blacksquare$

Answer 2

Use induction to show that $\forall n\in\Bbb Z^+ : P(n)$ where $P(n) := \Big[2\mid (n^2-n)\Big]$

A proof by induction requires demonstrating a base case, and iterative step.

$$P(c), \forall n\geq c: [P(n)\to P(n+1)] \vdash \forall n\geq c: P(n)$$

Base Case(s): $P(0), P(1)$

$$P(0) = 2\mid (0^2-0)\\P(1) = 2\mid (1^2-1)$$

As $2\mid 0$, the base case is verified.

Iterative Step: Now demonstrate $P(n)\to P(n+1)$

$$2\mid (n^2-n) \implies 2\mid (n+1)^2-(n+1) \qquad\text{You must demonstrate this}$$

What have you tried so far?

Answer 3

About your attempt. You wrote:

I've tried $$\begin{split} (n+1)^2 − (n+1) &= (n+1)(n+1) - (n+1)\\ &=(n+1)(n-1)+2 - (n+1)\\ &=n^2 +n -n -1 +2 -n -1\\ &=n^2 -n \end{split}$$

This is not correct. Just plug in $n=1$ to see that $n^2-n=0$ and $(n+1)^2-(n+1)=2$, so these two expressions are not always equal.

But you can get $$(n+1)^2-(n+1)=(n+1)[(n+1)-1]=(n+1)n=n^2+n=(n^2-n)+2n.$$ This means that the difference between the two expressions equals $2n$, therefore it is even and they have the same parity.

---

There is also an easy proof without induction. You just need to notice that $n^2-n=n(n-1)$ and one of the consecutive integers $n$ and $(n-1)$ is even.