2.3. Proof Methods and Strategy...

Suppose we want to prove a conditional statement of the form:


We shall prove this statement using the following Tautology


This argument is called a “proof by cases”.

2.3.1 Example

Prove that if n is an integer, then n² ≥ n.

Proof

Obviously we can prove the given statement by proving the following conditional statement

2.3. Proof Methods and Strategy...

Thus we use a “proof by cases” as follows:


Thus multiplying both sides of n = 1 by n yields n² = n as asserted.


Therefore we have proved that n² ≥ n in all possible cases of an integer n.

2.3. Proof Methods and Strategy...

2.3.2 Definition

The absolute value |a| of a real number a is defined as follows:


2.3.3 Example

Show that if x and y are real numbers then
Solution

We use a “proof by cases”. Consider the following cases which cover all possible cases for the
real numbers x and y:

2.3. Proof Methods and Strategy...

Some statements can be proved by examining a small number of possibilities. Such simple proofs are a special type of proofs by cases and are called “exhaustive proofs”. The following two examples illustrate such type of proofs.

2.3. Proof Methods and Strategy...

2.3.4 Example

Prove that (n+1)³≥3ⁿ if n is a positive integer with n ≤ 4. Solution

We need only to verify the given inequality when n=1, 2, 3.


Thus we used an exhaustive proof to prove the required statement.

2.3. Proof Methods and Strategy...

2.3.5 Definition

An integer m is a perfect power if m=na, where a is an integer greater than 1.

2.3.6 Example

Prove that the only consecutive positive integers not exceeding 100 that are perfect powers are 8 and 9.

Solution

We use an exhaustive proof. Since there is no power of positive integers higher than the sixth power not exceeding 100 (as 2⁷=128 and soon) then we only consider powers less than the seventh powers. Thus we consider the following cases:

Case (i): The squares of positive integers not exceeding 100 which are 1,4,9,16,25,36,49,64,81 and 100.
Case (ii): The cubes of positive integers not exceeding 100 which are 1, 8, 27, 64.
Case (iii): The fourth powers of positive integers not exceeding 100 which are 1, 16, 81.
Case (iv): The fifth powers of positive integers not exceeding 100 which are 1, 32.
Case (v): The sixth powers of positive integers not exceeding 100 which are 1, 64.

2.3. Proof Methods and Strategy...

Looking at this list one can easily deduce that the only consecutive positive integers not exceeding 100 which are perfect powers are 8=2³ and 9=3². 2.3.7 Example

Use an exhaustive proof to prove that there are no integers x and y such that x²+3y²=8.

Solution

The values of x² we can consider are 0, 1 and 4. The values of 3y² that can be taken into account are: 0=3(0)² and 3=3(1)².

So the ordered pairs are (x2, 3y2) that should be considered are (0,0), (0,3), (1,0), (1,3), (4,0) and (4,3). It follows that the possible values of x²+3y², where x and y are integers are: 0, 3, 1, 4, 7. Therefore it is impossible to find integers x and y such that x²+3y²=8.

2.3.8 Remark

In the proof of example 2.3.3, we can dismiss case (iv) where x < 0 and y ≥ 0 because it is the same as case (iii) where x ≥ 0 and y < 0, with the roles of x and y reversed. To shorten the proof, we could have proved cases (iii) and (iv) together by assuming, without loss of generality, that x ≥ 0 and y < 0. Implicit in this statement is that we can complete the case with x < 0 and y ≥ 0 using the same argument as used for the case with x ≥ 0 and y < 0 with the obvious changes.

2.3. Proof Methods and Strategy...

In general, when the phrase “without loss of generality” is used in a proof (often abbreviated as WLOG), we assert that by proving one case of a theorem, no additional argument is required to prove other specified cases, [ ].

That is, other cases follow by making straightforward changes to the argument or by filling in same straightforward initial step. In the next example we illustrate a proof where “WLOG” is used effectively together with other proof techniques.

2.3.9 Example

Show that if x and y are integers such that xy and x+y are even then both x and y are even.

Solution

We first use a proof by contraposition. Thus suppose that x and y are both even. This implies that either x is odd or y is odd (or both). Obviously we may assume WLOG that x is odd, say x=2n+1 for some integer n. we now use “proof by cases”, we consider the following cases:

Case (i): If y is even then y=2m, for some integer m. Thus

2.3. Proof Methods and Strategy...

Hence x+y is odd. This contradicts the assumption that x+y is even.

Case (ii): If y is odd then y=2k+1, for some integer k. Thus


Hence xy is odd. This contradicts the assumption that xy is even.

This completes the proof by contraposition.