Show that $n^2+n$ is even for all $n\in\mathbb{N}$ by contradiction

Question

Show that $n^2+n$ is even for all $n\in\mathbb{N}$ by contradiction.

My attempt: assume that $n^2+n$ is odd, then $n^2+n=2k+1$ for all $k\in\mathbb{N}$.

We have that $$n^2+n=2k+1 \Leftrightarrow \left(n+\frac{1}{2}\right)^2-\frac{1}{4}=2k+1\Leftrightarrow n=\sqrt{2k+\frac{5}{4}}-\frac{1}{2}.$$

Choosing $k=1$, we have that $n=\sqrt{2+\frac{5}{4}}-\frac{1}{2}\notin\mathbb{N}$, so we have a contradiction because $n^2+n=2k+1$ should be verified for all $n\in\mathbb{N}$ and for all $k\in\mathbb{N}$.

Is this correct or wrong? If wrong, can you tell me where and why? Thanks.

Answer 1

Other users have already pointed out your big mistake: you can’t say that $n^2+n=2k+1$ for all $\mathbf k$, since being odd only means that this is true for a specific $\mathbf k$. We can complete your proof as follows. If $n^2+n=2k+1$, by your same calculation, $$n=\sqrt{2k+\frac54}-\frac12=\frac12\left(\sqrt{8k+5}-1\right).$$ However, $8k+5$ isn’t a square for any $\mathbf k$ (as a square must give a remainder of $0$, $1$ or $4$ when divided by $8$), so that, even when assuming the original statement for a single $k$, we arrive at the contradiction that $n$ is irrational. $\blacksquare$

Answer 2

You can't choose $k$ here; you have to show it's true for all of them. I would prove it this way. Assume $n^2+n$ is odd. This means $n(n+1)$ is odd, but that's impossible, because a number and its successor can't both be odd.

Answer 3

I hate to be the bearer of bad tidings, but the presented proof attempt is flawed. There is no guarantee that any $k$ corresponds to a given $n^2 + n$, so the assumption that

$\forall n \in \Bbb N, \exists k \in \Bbb Z, \; n^2 + n = 2k + 1 \tag 1$

is erroneous.

I prove it like this: if $n$ is odd, then $n + 1$ is even; so whether $n$ is odd or even, we have $2 \mid n(n + 1)$, i.e., $n(n + 1)$ is even.

Answer 4

Suppose $n^2 + n$ is odd for all natural numbers $n$. Then $n(n+1)$, the product of two consecutive integers, is also odd. However, an odd number can not have any even factors. Either $n$ is odd, and $n+1$ is even, or $n$ is even and $n+1$ is odd, as they are consecutive integers. The product $n(n+1)$ has one even and one odd factor, which contradicts our previous statement that $n(n+1)$ is odd, as an odd number times an even number is an even number.

Answer 5

To be different. Suppose there some natural number where this is true. But it isn't true for $1$ or $2$. But if there is some value where it is true there must be some first value, $n$ where it is true.

So suppose that $n^2 + n$ is odd but $(n-1)^2 + (n-1)$ is not odd. Then $n^2 - 2n + 1+ n-1 = n^2-n + 2$ is even. So $n^2 - n + 2 = 2k$ for some $k$.

So $n^2 - n + 2 + (2n-2) = 2k + (2n-2) = 2(k+n -1)$ is even. But $n^2 - n + 2 + (2n-2)=n^2 + n$ which we assumed was odd.

The advantage of this proof is that we don't have to assume that if $n^2 + n = n(n+1)$ is odd that means $n$ and $n+1$ are both odd (why is that so?) and that it is impossible for $n$ and $n+1$ to both be odd (why is that so?).

The disadvantage of this proof is it's abstract and not straightforward.