Is this proof of $n(n+1)$ is even for any $n\in\mathbb{N}$ correct?

Question

I know that there are a lot (and easier) ways to prove this, but I would like to know if this is correct.

Prove that $n(n+1)$ is even for any $n\in\mathbb{N}$.

Suppose by contradiction that this isn't true, so $n(n+1)=2l+1$ for some $l\in\mathbb{Z}$, but we know that $$\sum_{k=0}^{n} k=\frac{n(n+1)}{2}$$ Since the left hand side is a sum of positive integers it must be a positive integer, but $n(n+1)=2l+1$ and so the right hand side is $\frac{n(n+1)}{2}=\frac{2l+1}{2}=l+\frac{1}{2} \in \mathbb{Q} \setminus {\mathbb{Z}}$ and this is absurd.

Answer 1

It works if you can assume

1) it is known that $\sum_{k=0}^n k = \frac {n(n+1)}2$

and 2) it is known that if $a_1, a_2,....,a_n$ are all integer then $\sum a_i$ is an integer.

But then, a) I'd suggest there is no reason to assume $n(n+1)$ is odd. The definition of "even" is $m$ is even $\iff 2|m \iff \frac m2$ is an integer $\iff $ there is an integer $w$ so that $m = 2w$. And as $\frac {n(n+1)}2 = \sum_{k=0}^nk $ is and integer, it follows directly that $n(n+1)$ is even.

b) I wouldn't use $k$ for both $\sum_{k=0}^n k$ and fro $n=2k+1$. Those are the same variable for different purposes. ANd $\sum_{k=0}^nk = \frac {n(n+1)}2 = \frac k2$ would be ... just plain nutty.

c) I'm going to be a real asshat and ask you how you know that "$m$ is odd" actually means "there is a $k$ so that $m = 2k+1$"? Why can't $m$ be odd so there doesn't exist any $w$ so that $m = 2w$ but what if there isn't any $k$ so that $m = 2k+1$? Do you have any reason to thing every number must be either equal to $2k$ for some $k$ or equal to $2k+1$ for some $k$? Why can't some numbers be neither? Why can't some numbers be both?

You don't actually have to answer c). I'm just being a real jerk. But it's worth thinking about.

(For that matter: I'm being a jerk with 2). Of course the sum of integers is an integer because.... um.... well, because.....)

Answer 2

Yes, your proof looks correct. Certainly an interesting way to prove it. FYI, I would recommend not using $k$ as the index you sum over as it makes the proof confusing since $k$ represents two different things.

Answer 3

Your proof is correct, but with the same plan of attack, you can have a direct proof . . .

As you argued, ${\large{\frac{n(n+1)}{2}}}$ is an integer, equal to $m$ say, hence \begin{align*} &\frac{n(n+1)}{2}=m\\[4pt] \implies\;&n(n+1)=2m\\[4pt] \end{align*} so $n(n+1)$ is even.

But note: Your proof only works as is for the case where $n$ is a nonnegative integer. The more standard proofs work for all integers $n$.

Answer 4

Congratulations, you discovered the natural telescopic inductive proof. Let's highlight it.

Let $\,f(n) = (n\!+\!1)n.\,$ Then $\,f(n)-f(n\!-\!1) = (\color{#c00}{n\!+\!1})n-n(\color{#c00}{n\!-\!1}) = \color{#c00}2n\,$ is even

i.e. $\,f(n)\,$ has same parity as $\,f(n\!-\!1),\,$ thus $\,f(0)=0$ even $\,\Rightarrow\ f(n)$ even by induction.

Telescopically summing $\,f(k)-f(k\!-\!1) = 2k\,$ makes the factor of $\,\color{#c00}2\,$ explicit, namely

$$\begin{align}f(n)-f(0) &\,=\, \sum_{k=1}^n\ [f(k)-f(k-1)]\\ \Rightarrow\,\ (n\!+\!1)n &\,=\, \sum_{k=1}^{n} \color{#c00}2k\ \ \text{is $\:\!\color{#c00}{\rm even}$}\end{align}\qquad$$

This is a prototypical example of telescopic induction. You can find many other examples in various posts on telescopy and related topics.