Well-ordering proof

Number Theory Level 2

What is wrong with this "proof" of the following statement?

For every positive integer $n,$ the number $n^2+n+1$ is even.

Proof:

Let $S$ be the subset of positive integers $n$ for which $n^2+n+1$ is odd. Assume $S$ is nonempty.

Let $m$ be its smallest element.

Then $m-1 \notin S,$ so $(m-1)^2+(m-1)+1$ is even.

But $(m-1)^2+(m-1)+1 = m^2-m+1 = (m^2+m+1)-2m,$ so $m^2+m+1$ equals $\big((m-1)^2+(m-1)+1\big)+2m,$ which is a sum of two even numbers, which is even.

So $m \notin S;$ which is a contradiction. Therefore, $S$ is empty, and the result follows.

Nothing is wrong; the statement is true

S

might not have a smallest element, so the second paragraph is wrong

m-1

is not necessarily a positive integer, so the third paragraph is wrong There is an algebra error, so the fourth paragraph is wrong There is no contradiction, so the fifth paragraph is wrong

3 solutions

Michael B
Mar 16, 2018

The theorem: For every positive integer the number $n^2+n+1$ is even.
Notice how it says "every positive integer".

Consider $n=1$ . In paragraph 3, the proof says that $m-1\notin S \longrightarrow (m-1)^2+(m-1)+1$ not odd, thus even. But the theorem is not applicable in this case, because $m-1=1-1=0$ is not a positive integer. Thus, everything what follows does not prove anything.

If you would try a proof by induction, you would fail right at the beginning. Indeed, for every positive integer $n^2+n+1$ is odd.

Proof :

The addition of two even and two odd numbers is even.
The multiplication of two even numbers is even.
The multiplication of two odd numbers is odd. (Suppose n is odd, then $n*(n-1)$ is even and $n*(n-1)+n$ is odd again).

Suppose n is even. Thus, $n^2$ is even (2), and $n^2 + n$ is even (1), and $n^2+n+1$ is odd.
Suppose n is odd. Thus, $n^2$ is odd (3), and $n^2+n$ is even (1), and $n^2+n+1$ is odd again. $\square$

for odds: take n=1, then 1^2 + 1 + 1 = 3...... take n= 3, then, 3^2 +3 + 1 = 13....

an even n is always an even, and an odd n is always odd. Didn't follow your logic Michael B

Matt Champlin - 1 year, 3 months ago

Matt, try it with n=2. --> 2^2 +2+1 = 7. this is not a proof, but hopefully you get the intuition behind "for every positive integer n, n^2+n+1 is odd (or of the form 2k+1).

MathHead Duuble - 3 months, 1 week ago

I got correct✅

Chiranjibi Mahapatra - 3 months, 2 weeks ago

Sayandeep Ghosh
May 4, 2016

Yes that's the only reason....(m-1) Is not necessarily to be a positive number ...

Somi Gupta
Aug 9, 2018

As we see 1 belong to S which is the smallest positive integer(0 is not included in positive number) that belong to S. so m-1=0 does not belong to set of positive number so we cannot apply the given statement. Therefore using this to proceed further is not correct.

I do not think it’s a good example.

In fact, given b∈Z, any non-empty subset A⊆ {b, b + 1, b + 2, b + 3,…} has a smallest element. Even thought b is a negative number.

The logical error occurs here, that you can not deduce (m−1) ^2+(m−1)+1 is even merely by m−1 do not belong to S.

Marko Hanks - 1 month ago

Well-ordering proof

3 solutions

0 pending reports