Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 8.5.2 The Usefulness of Constructive Proofs

Constructive proofs are often more useful than direct ones because they yield actual values that we can use.

We’ve already seen one example of this.

Prove that, for every prime number, there exists a larger one. In our proof that there is no largest prime (back in our discussion of proof by contradiction), we showed not only that such a larger one must exist, but we gave an algorithm for computing it: Define the sequence pi of prime numbers, where p1 = 2, p2 = 3, and so forth. Now consider the nth prime number, which we can write as pn. Then q, as computed here, must be a prime number greater than pn:

q = (p1p2p3 … pn) + 1.

In our proof by contradiction that there is no largest prime, we showed why q must, in fact, be prime.

Now let’s look at another example.

Prove that every quadratic equation with real coefficients has at least one root.

First, notice that, while we didn’t say so explicitly, this claim has the form of an existential quantifier inside a universal one:

 quadratic equations ( root)

The proof is by construction: Any quadratic equation can be written as: y = ax2 + bx + c, where a is not 0.

Then the root(s) are given by the quadratic formula: x= (-b±√(b^2-4ac))/2a

To complete the proof, we must show that this formula is correct:

Let: x_1= (-b+√(b^2-4ac))/2a and x_2= (-b-√(b^2-4ac))/2a These are the two roots.

Notice that a (x – x1) (x – x2) = 0 has solutions x1 and x2. Notice also:

Thus x1 and x2 are also solutions to ax2 + bx + c.

So we know not only that roots exist. We know what they are.

Prove that, for every positive integer n there exists a sequence of n consecutive positive integers containing no primes. For example, if n is 3, such a sequence would be 8, 9, 10. Another such sequence is 24, 25, 26. Again, notice the form of this claim:

n ( sequence of consecutive positive nonprime integers of length n)

We’ll prove this claim by construction, which has the advantage of giving us an example of the desired sequence for any value of n.

How should we start designing our construction? The first thing we notice is that we need numbers that are composite. That means that every one of them must have some nontrivial (not itself or 1) factor. And that has to be true not just of the first one but of all the others that we get by adding 1, 2, etc. to it. Recall that n! (n factorial) is defined to be 123 … n. We observe that n! has a lot of factors. And, in particular, every positive integer less than or equal to n is a factor. This might be a good place to start.

The sequence that we need is the sequence of n integers starting with (n+1)! + 2. To see why this works, observe:

Call the first element of the sequence x. Then we have:

\(x = (n+1)! + 2 \)

The rest of the numbers in the sequence will then be x + 1, then x + 2, and so forth up to x + (n – 1). That’s n of them. To set the stage for the rest of the sequence, let’s think of the first one as x + 0:

x + 0 = (n+1)! + 2 + 0 Then we also have:

x + 1 = (n+1)! + 2 + 1

… x + (n – 1) = (n+1)! + 2 + (n – 1)

More generally, for every value of i between 0 and (n – 1), we have:

[1] x + i = (n+1)! + (2 + i)

= (n+1)! + (i + 2)

Now, since i is less than n, i + 1 must be less than or equal to n and i + 2 must be less than or equal to (n+1). So i + 2 is one of the factors of (n+1)! Let’s rewrite (n+1)! so that we list the factors up to i + 2, then i + 2, then the remaining ones. That gives us:

[2] x + i = (1  2  …  i  (i + 1)  (i + 2)  … n  (n + 1)) + (i + 2)

(Don’t worry about what happens if i were, say, 2. We’ll still include it only once in the expansion above. We’ve shown 2 explicitly here just to make it clear what’s going on.)

Notice that the right hand side of [2] is the sum of two quantities, both of which have (i + 2) as a factor. So we can factor it out, which produces:

[3] x + i = (i + 2)  ((1  2  …  i  (i + 1)  … n  (n + 1)) + 1)

Now we see that x + i must be composite because it has two factors, neither of which is 1. (Since i starts at 0, i + 2 must be at least 2. In fact, that’s why we had to add 2 to (n+1)! to get the first value in our sequence.)