All Integers Are Even

We are going to prove by induction that,

For all integer n ≥ 2, n is even.

(This was brought up by Adam Liss at a Linkedin discussion.)

The claim is verified for n = 2; for indeed, 2 is the smallest even number.

Assume the claim holds for all 2 ≤ n < k, that is

All integers below k starting with 2 are even.

From these we now derive that k is also even.

Split it into two parts, m₁ and m₂, respectively. Of course, m₁ + m₂ = k. By the induction hypothesis we know that m₁ is even and m₂ is even. So the total N = m₁ + m₂ must be even.

Induction is complete.

What went wrong?

The error in the proof is subtle. The inductive step had to be formulated as

Assume the claim holds for all 2 ≤ n < k, that is, all integers below k starting with 2 are even, k ≥ 2.

The derivation then clearly fails for k = 3 since it is impossible to split 3 into the sum of two numbers each at least 2.

71547294