Skip to main content

Subsection 8.11.3 Strategies for Discovering Proofs

We have just presented a collection of major strategies for designing proofs. Suppose that you have a nontrivial statement that you’d like to prove. How should you go about choosing one or more of these strategies? Then let’s say you’ve picked one (or more). For example, suppose you plan to write a forward, direct proof. You still have a lot of decisions left to make. What premises should you use? What key inference rules should you use? In what order? In nontrivial domains, you’ll find yourself searching in a very large space of possible proofs, hoping to find one that leads to the conclusion that you seek.

Here’s a picture that may help you understand the problem.

Read the picture as follows: Assume that you start your proof with a set of premises (some or all of which may be relevant). So you start in the state that corresponds to the top oval. The premises are what you know. Each time you write a non-premise line in your proof, you add a new statement that you know to be true. So you move to a new state in which you know everything you used to know, plus something new. Each line in the picture corresponds to one application of a sound inference rule or identity. Your goal is to arrive at a state (represented as an oval) in which your desired conclusion has become one of the things that you know. If, say, your desired conclusion were F, then the oval shown in red would correspond to a goal state.

Your problem may now be obvious. There may be a lot of branches coming out of the state you’re currently in. How do you know which of them will take you to your desired conclusion? You don’t want to waste time on paths that don’t lead to your goal.

So what’s a budding proof engineer to do?

The answer is that you need to develop for yourself a set of rules of thumb that will guide you in the direction of effective proofs.

We call these rules of thumb heuristics. Think of a heuristic not as an algorithm that is guaranteed to lead you immediately to the right answer. Rather, it’s a technique that (substantially, we hope) beats blind search most of the time.

Nifty Aside

The word “heuristic” comes from the same Greek word as “Eurika”, the exclamation that Archimedes is reputed to have uttered when, while sitting in the bath tub, he realized that he could compute the amount of gold in the king’s crown by measuring its displacement in water. The Greek root word means “to find”.

The heuristics that you’ll develop will typically look like pattern/action rules. Think of them as being written as:

A ⇒ B

This rule says that if your problem looks like A, do B.

Here’s a table with some simple rules:

Table 8.11.1.
Problem Characteristics Proof Technique to Try
Straightforward application of logical or algebraic rules may work. Direct proof.
I’m trying to prove something about a sequence. Inductive proof.
I tried direct proof and got stuck. Proof by contradiction.
I’m trying to prove a claim of the form: ∃y ( …) Proof by example.
I’m trying to prove a claim of the form: ∀x (∃y ( …) ) Proof by construction.
I’m trying to prove a claim of the form: ¬∀x ( …) Proof by counterexample
I can’t find a good general proof but a manageable number of cases covers everything Case Enumeration

And then, once you’ve chosen your overall approach, you’ll have to exploit similar pattern/action rules that are specific to the technique that you’re using.

At this point, you’re probably saying something like, “Bring them on. Tell me exactly how I’ll know what to do next at each step of my proof.” Unfortunately, we don’t know how to do that. Every situation is different. Writing a proof is like designing anything else. We will attempt to give you some good advice. But the best way to get good at writing proofs is to practice. If you do that, you’ll acquire rules that work.

Nifty Aside

It’s so hard that powerful automatic theorem provers are often interactive so human experts can guide them when necessary. Several such interactive provers are being developed today. Visit http://en.wikipedia.org/wiki/Proof_assistant for more about them.

In the next set of problems, you will need to figure out which technique(s) to use to complete the required proofs.

Exercises Exercises

Exercise Group.

Define the following predicates:

USP(x): True if x was a President of the United States.

M(x, y): True if x and y have ever been married to each other.

Prove or disprove the claim that every US President has been married. We can state the claim as:

[1] ∀x (USP(x) → ∃y (M(x, y)))

Part 1.
Is [1] True or False?
Answer.
Correct answer is False
Part 2.

Which of the following proof techniques can be used to prove or disprove [1]?

  1. Proof by Example

  2. Proof by Counterexample

  3. Proof by Case Enumeration

  4. Proof by Contradiction

  5. Direct Proof

Answer.
Correct answer is B.
Solution.
Explanation: We prove that [1] is false by counterexample. James Buchanan, the 15th President of the United States, never married. Notice that, if the claim had been true, the way to prove it would have been case enumeration. There have been a finite number of US Presidents. So it is possible to examine each of them and determine whether he’d been married.

Exercise Group.

Prove or disprove the following claim. (Recall that |x|, read as “absolute value of x”, is simply x if x is nonnegative. It is –x otherwise. For any x, |x| is thus nonnegative.)

[1] For any reals x and y, |xy| = |x| ⋅ |y|

Part 1.
Is [1] True or False?
Answer.
Correct answer is True
Part 2.

Which of the following proof techniques can be used to prove or disprove [1]?

  1. Proof by Example

  2. Proof by Counterexample

  3. Proof by Case Enumeration

  4. Proof by Contradiction

  5. Direct Proof

Answer.
Correct answer is C.
Solution.

Explanation: We can’t use Counterexample, since the claim is true. We can’t use Induction since there is no series to work with. We can’t use Example, since we are trying to prove a universal claim. The most straightforward thing to do is to enumerate the cases that arise when we consider the signs of x and y. So here’s a proof:

There are four cases to consider:

  • x and y are both positive. Then |x| = x and |y| = y. So |xy| = xy = |x|  |y|.

  • x and y are both negative. Then |x| = -x and |y| = -y. xy is positive, thus |xy| = xy = |x|  |y|.

  • x is positive and y is negative. xy is negative. |xy| = -xy. |x| = x and |y| = -y. So |x|  |y| = -xy.

  • x is negative and y is positive. xy is negative. |xy| = -xy. |x| = -x and |y| = y. So |x|  |y| = -xy.

3.

Assume the universe of positive integers. Prove or disprove the following claim:

[1] ∀n (Prime(n2 + 4n + 3))

Is [1] true or false? (Hint: Recall that a number is prime if its only two integer factors are itself and 1.) Prove your answer.

Which of the following statements is correct:

  1. [1] is true.

  2. [1] is false.

Answer.
Correct answer is B.
Solution.
Explanation: We can prove that [1] is false with a single counterexample. Let n = 1. Then n2 + 4n + 3 = 8, which isn’t prime. In fact, what’s true is that, for all n, n2 + 4n + 3 must be composite. To see why that is so, notice that we can factor n2 + 4n + 3 as (n+3) (n+1). So we have two factors. Since we are considering only positive values of n, neither of those factors is 1. Nor is either of them n.

Exercise Group.

4. Prove or disprove the following claim:

[1] For all x ≥ 1 and k ≥ 1, (x + k)2 > x2 + k2

Part 1.

It is possible to prove [1] by example.

  1. True.

  2. False.

Answer.
Correct answer is B.
Solution.
Explanation: The statement is false. It’s not possible to prove a universal claim by example.
Part 2.

It is possible to disprove [1] by counterexample.

  1. True.

  2. False.

Answer.
Correct answer is B.
Solution.
Explanation: The statement is false. [1] is true, so it cannot be disproved.
Part 3.

It makes sense to prove [1] by direct proof.

  1. True.

  2. False.

Answer.
Correct answer is A.
Solution.
Explanation. The statement is true. There’s a simple direct proof.
Part 4.

It makes sense to prove [1] by induction.

  1. True.

  2. False.

Answer.
Correct answer is B.
Solution.
Explanation: The statement is false. Induction is useful when there’s a way to describe the n+1 case in terms of n (or some other previous values). That’s not true here. Here is a proof of [1]: (x + k)2 = x2 + 2xk + k2 > x2 + k2 Since x and k are both at least 1, 2xk > 0.

Exercise Group.

5. Prove or disprove the following claim:

[1] For any nonnegative integer n, \((\sum_{i = 0}^{n}{i^{3})}\) = \(\frac{n^{2}{(n + 1)}^{2}}{4}\text{.}\)

Part 1.

It is possible to prove [1] by example.

  1. True.

  2. False.

Answer.
Correct answer is B.
Part 2.

It is possible to disprove [1] by counterexample.

  1. True.

  2. False.

Answer.
Correct answer is B.
Part 3.

It makes sense to prove [1] by direct proof.

  1. True.

  2. False.

Answer.
Correct answer is B.
Part 4.

It makes sense to prove [1] by induction.

  1. True.

  2. False.

Answer.
Correct answer is A.
Solution.
Explanation: The statement in Part 1 is false. It’s not possible to prove a universal claim by example. The statement in Part 2 is false. [1] is true, so it cannot be disproved. The statement in Part 3 is false. There isn’t an easy way to prove this claim directly. But the statement in Part 4 is true. There is a simple proof by induction. Try to find it.