Skip to main content

Subsection 1.4.4 Other Proof Structures

Some proofs look somewhat different from the ones that we have just described.

For example, some claims can be proved or disproved with just a single example.

Activity 1.4.9.

Define the function \(n!\) (pronounced, “n factorial”), on the positive integers, as:

[1] \(n! = n \cdot (n-1) \cdot (n-2) \cdots 1 \)

For example, \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.\)

Now consider the following claim: For any positive integer, \(n!\) is even.

We can prove that this claim is false by exhibiting a single value that contradicts it. So our proof is:

\(1! = 1\text{,}\) which is odd (thus not even).

Sometimes we prove that a claim is true by showing that its negation must be false.

Activity 1.4.10.

Definition 1.4.2.

An integer n is even if and only if it is equal to \(2\cdot k\text{,}\) for some integer \(k\text{.}\)

Definition 1.4.3.

An integer n is odd if and only if it is equal to \((2\cdot k) + 1\text{,}\) for some integer \(k\text{.}\)

Assume that we have already proved (and thus we can take this as a premise) that every integer is either even or odd, but not both.

Now suppose that we want to prove:

[1] For all integers \(n \text{,}\) we if \(n^2 \) is even, then n is also even.

We start by assuming that \(n^2 \) is even. We want to prove that, therefore, n is also even. Assume, to the contrary, that n is not even. In other words, it is odd and there exists some integer k such that:

[2] \(n = 2\cdot k + 1 \)

Squaring both sides, we have:

[3] \(n^2 = (2\cdot k + 1) (2\cdot k + 1)\)

\begin{align*} [4] n^2 & = 4 \cdot k^2 + 2\cdot k + 2\cdot k + 1 \end{align*}

But an integer is odd just in case it is \(1\) more than some integer that is divisible by \(2\text{.}\) The quantity \(2\cdot (2\cdot k^2 + 2\cdot k)\) is divisible by \(2\text{.}\) So we have that \(n^2\) is odd. But that contradicts our starting premise that \(n^2\) was even. Thus the assumption that n is odd (i.e., not even) must be false. So \(n\) is even.

But note that these proofs still possess the structure that is required of all correct proofs: They begin with premises (possibly not stated explicitly, such as the rules of algebra), apply sound inference rules, and finally derive their conclusion.

Problems 1.4.11.

(a)

Consider the claim that there exists some President of the United States who was born in Virginia. Which of the following is true:

  1. The claim is true and it can be proved by exhibiting a single example.

  2. The claim is false and can be proved false by exhibiting a single example.

  3. The claim is true but it’s not possible to prove it with a single example.

  4. The claim is false but it’s not possible to prove it false with a single example.

Answer.
i is correct.
Solution.
Explanation: We can prove an existence claim by showing that even one example does exist. So, for example, we could prove this claim by exhibiting George Washington.

(b)

Consider the claim:

For any positive integer greater than 1, \(n! \) is even.

Which of the following is true:

  1. The claim is true and it can be proved by exhibiting a single example.

  2. The claim is false and can be proved false by exhibiting a single example.

  3. The claim is true but it’s not possible to prove it with a single example.

  4. The claim is false but it’s not possible to prove it false with a single example.

Answer.
iii is correct
Solution.

We can’t prove a universal claim (one that asserts some property of everything) by showing that it’s true of one or more individual examples. So that’s out as a proof strategy.

But it’s easy to see that the claim is true. If \(n > 1 \text{,}\) it is at least 2. That means that:

\(n! = n \cdot (n-1) \cdot (n-2)\cdot \cdots \cdot 2 \cdot 1 \)

So \(n! \) must have 2 as a factor. Thus it’s even.