Is there a better way to present proofs by contradiction?

[Dr. Seafood]

Sometimes I find that while a proof can be carried out "by contradiction", this is a pretty sloppy way of proving the desired statement. I wonder if the "←" direction of the following proof is sound presentation of proof by contradiction.

Statement. An integer is even if and only if its square is even.

Proof. First suppose the integer n is even. Then for some k ∈ ℤ, n = 2k and n² = 4k² = 2(2k²), so n² is even. Conversely, if n² is even, suppose n is odd. Then n = 2k + 1 with k ∈ ℤ. Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, so n² is odd; a contradiction. Thus n must be even. □

Is it messy to prove "n² is even ⇒ n is even" (*) via contradiction? It seems like a jumble of words in this case. I didn't actually rely on the assumption "n² is even" when directly showing that n = 2k + 1 leads to contradict that. I feel like all I've done is shown that the square of an odd integer is also odd. It seems like a messy way to go about it, there should be a more well-crafted proof for that.

In my opinion the next proof is a strong example of proof by contradiction:

Statement. Every integer greater than 1 can be written as a product of prime numbers.

Proof. Suppose towards contradiction that the result is false. Then let n > 1 be the smallest integer that cannot be written as a product of primes. n is not prime, so n = pq for some integers p, q with 1 < p ≤ q < n. Since p and q are both smaller than n, it must be possible to factor them into primes; thus n can be written as a product of primes after all, a contradiction. □

The difference between this and the previous statement proven is that the assumption made (towards contradiction) directly contradicts itself: we assumed n cannot be written as a product of primes, and showed that this implies that it indeed can be. I tend to think that presenting it this way really strikes at the core of proving by contradictions.

For the first proof about even numbers, I think there's a better way to carry that out. It just seemed to work when worded as a "proof by contradiction", but it's actually a simpler proof in disguise.

 

[pwsnafu]

Proof.Conversely, if n² is even, suppose n is odd. Then n = 2k + 1 with k ∈ ℤ. Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, so n² is odd; a contradiction. Thus n must be even. □

I removed the first part of the proof. This is more of a contrapositive proof than contradiction:

n is odd => n² is odd

is the same thing as

n is even <= n² is even.

Amusingly, in the http://en.wikipedia.org/wiki/Proof_by_contrapositive" on the topic uses this example.

 

[Dr. Seafood]

LOL, oh wow yeah that is indeed amusing.

I guess the kinks I'm trying to work out are regarding the presentation of the proof. It seemed pretty ugly when shown as a "proof by contradiction". Stating it as showing the contrapositive works a lot nicer there, thanks.