how to know when a particular proof is appropriate for the given problem?

Question

The main trouble I am currently having in math is knowing when the use cases are appropriate in a proof. I see many videos where they seem to choose a strategy like proof by contrapositive or proof by contradiction, but never quite understand how they came to the conclusion to use that proof strategy.

Here are some examples I have come across and my own solutions to them using the recommended proofs

the product of two odd integers is odd

I used contradiction to solve it

• suppose the product of two odd integers is even
• (2k+1)(2k+1) = 2k
• 2(2k^2 + 2k) + 1 = 2k
• given k is an integer, (2k^2 + 2k) is an integer. Therefore, an even number cannot be an odd number

if x^2 is even, x is even

Based on the wikipedia article on contrapositive

• if x is odd, then x^2 is odd
• (2k+1)^2 == 2(2k^2 +2k) + 1
• therefore, if x^2 is even, then x is even

However, what I am wondering is, is there a general principle as to when to use specific strategies for proofs? Eg, if you specifically know a theory is false, do you choose a strategy accordingly? What determines which strategy will be most effective, or is it arbitrary?

Answer 1

This skill comes with lots of practice. Generally speaking, direct proofs are used when the result is "positive-sounding". In your example, the result is, "the product of two odd integers is odd". This result is positive-sounding (as opposed to a result like, "there is no smallest positive real number").

For the result, "if $x^2$ is even, then $x$ is even," you could do either a direct proof or a proof by contrapositive. A lot of times it does not matter and there is usually more than one way to prove something. The direct proof, in this case, is favored over a proof by contrapositive simply because it is more, well, direct. Here is how the result would be proven using the contrapositive:

Proof:

Suppose $x$ is odd. We show that $x^2$ is odd. So $x=2k+1$ for some integer $k$. Thus $x^2=(2k+1)^2=(2k+1)(2k+1)=4k^2+4k+1=2(2k^2+2k)+1.$ Now, since $(2k^2+2k)$ is an integer, it follows that $x^2$ is odd.

For a result like "there is no smallest positive real number", this would be difficult to prove using a direct proof. The result is better suited for a proof by contradiction. It would start like this: "Suppose there exists a smallest positive real number…"

Some other examples of negative sounding results that would be more suited for proof by contradiction:

• If a is an even integer and b is an odd integer, then 4 does not divide $a^2+2b^2$
• The integer 100 cannot be written as the sum of three integers, and odd number of which are odd
• The sum of a rational number and an irrational number is irrational.

[Source: Chartrand, G., Polimeni, A.D., Zhang, P., 2013. Mathematical Proofs: A Transition to Advanced Mathematics, 3rd ed. Boston: Pearson.]

Answer 2

There are many ways to write down a proof. The question is, apart from correctness, which one is more elegant, more concise, more constructive, and last not least easier und thus clearer. In your case, for me the easiast way is to do first an obvious computation, i.e. $$ (2k+1)(2l+1)=4kl+2k+2l+1. $$ Your first step here is wrong, because you assume that both integers are equal, i.e., both given by $2k+1$. This would be a special case.
Then, in the second step, we consider everything modulo $2$. The integer on the RHS is odd, because it is of the form $2m+1$, with $m=2kl+k+l$. This finishes the proof.