Proof Methods and Strategy

Proof methods and strategy

Exhaustive proof :

An exhaustive proof is a special type of proof by cases where each involves checking a single example.

Example: Prove that every integer n with 2 ≤ n ≤ 26 can be written as a sum of at most three perfect squares.

Proof: Let S = {2, 4, 6, ..., 24, 26}.

We have to prove that the statement: "∀x ϵ S, P(x)" is true. Where P(x): x is a sum of at most three perfect squares.

We observe the following:

2 = 1² +1²

4 = 2²

6 = 2² + 1² + 1²

8 = 2² + 2²

10 = 3² + 1²

12 = 2² + 2² + 2²

14 = 3² + 2² + 1²

16 = 4²

18 = 4² + 1² + 1²

20 = 4² + 2²

22 = 3² + 3² + 2²

24 = 4² + 2² + 2²

26 = 5² + 1²

This show sthat each x in S is a sum of at most three perfect squares.

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

Solution: Given: (n+1)³ ≥ 3ⁿ             for n = 1, 2, 3, 4

In each of these four cases, we see that

(n + 1)³ ≥ 3ⁿ

Proof by cases

This method cover all possible cases that arise in a theorem.

Example 1. Prove that if n is an integer, then n³ ≥ n

Proof : Case (i) When n = 0, we get 0³ = 0

⇒ n³n is true.

Case (ii) when n ≥ 1

 (n²) (n) ≥ (n²) (1)

n³ ≥ n²

⇒ n³ ≥ n for n ≥1

Case (iii) When n ≤ -1. However n³ ≥ 0.

If follows that n³ ≥ n

We can conclude that if n is an integer, then n³ ≥ n

Example 2. Prove the triangle inequality, which states that if x and y are real numbers, then |x|+|y| x+y] (where |x| represents the absolute value of x, which equals x if x ≥ 0 and equals -x if x < 0)

Proof: Case (i) x ≥ 0 and y ≥0

Then |x| + |y| = x + y = | x + y |

Case (ii) x < 0 and y < 0 (x + y) <0

Then |x| + |y| = (-x) + (-y) = - (x + y) = |x + y|

because (x + y) <0

Case (iii) x ≥ 0 and y < 0

Then |x| + |y| = x + (-y).

If x ≥ -y, then |x + y| = x + y

But because y < 0, -y > y, so

[x] + [y] = x + (-y) > x + y = |x + y|

If x < -y, then |x + y| = - (x + y) = (-x) + (-y)

But because x ≥ 0, x ≥ -x, so

|x| + |y| = x + (-y) ≥ -x + (-y) = |x + y|

Case (iv) x < 0 and y = 0

It is identical to case (iii) with the roles of x and y reversed.

Leveraging proof by cases

Generally, look for a proof by cases when there is no obvious way to begin a proof, but when extra information in each case helps move the proof forward.

Example: Show that there are no solutions in integers x and y of x² + 3y² = 8

Solution: x² > 8 when |x| ≥ 3 and

3y² > 8 when |y| ≥ 2

This leaves the cases when x takes on one of the values -2, -1, 0, 1 or 2 and y takes on one of the values -1, 0 or 1.

We can finish using an exhaustive proof.

Now possible values of x² are 4, 0, 1 and possible values of 3y² are 3, 0 and the largest sum of possible values

for x² and 3y² is 7.

Consequently, it is not possible

for x² + 3y² = 8 to hold when x and y are integers.

Without loss of generality:

Many incorrect proofs of famous theorems turned out to rely on arguments that used the idea of "without loss of generality" to establish that could not be quickly proved from simpler cases.

Example: Prove or disprove that you can use dominoes to tile the standard checker board with two adjacent corners removed (that is, corners that are not opposite).

Solution: Without loss of generality, assume that the upper left and upper right corners of the board are removed. Place three dominoes horizontally to fill the remaining portion of the first row, and fill each of the other seven rows with four horizontal dominoes.

Example 2. Show that (x + y)^r < x^r + y^r whenever x and y are positive real numbers and r is real number with 0 < r < 1.

Solution: Without loss of generality

Assume that x + y =1, because x and y are positive, 0 < x < 1 and 0 < y < 1, 0 < r < 1

⇒ 0 < 1-r < 1

⇒ x^1-r < 1 and y^1-r < 1

⇒ x < x^r and y < y^r

⇒ x^r + y^r > x + y = 1

This means that (x + y)^r = 1^r < x^r + y^r

This proves the theorem for x + y = 1

Common errors with exhaustive proof and Proof by cases :

A common error of reasoning is to draw incorrect conclusions from examples. No matter how many separate examples are considered, a theorem is not proved by considering examples n less every possible case is covered.

Example 3. What is wrong with this "proof"?

Theorem: If x is a real number, then x² is a positive real number.

Proof : Let a₁ be "x is positive,"

Let a₂ be "x is negative," and

Let b be "x² is positive."

To show that a₁→b is true, not that when x is positive, x² is positive since it is the product of two positive numbers, x and x. To show that a₂→b, note that when x is negative, x² is positive because it is the product of two negative numbers, x and x. This completes the proof.

Solution: Here we missed the case x = 0.

If x = 0, x² =0 is not positive, so the supposed theorem is false.

If a is "x is a real number.",

Let a₁: x is positive,

a₂: x is negative,

a₃: x=0

then a  ↔  a₁ V a₂ V a₃

Existence proof:

It was pointed out that a proposition of the form "Ǝx ϵ S, P (x)" is true if any one element a ϵ S such that P (a) is true is exhibited. Hence, the best way of proving a proposition of the form "Ǝx ϵ S, P (x)" is to exhibit the existence of one a ϵ S such that P (a) is true. This method of proof is called the proof of existence.

Example 1. Prove that there exists a real number x such that x³ + 2x² - 5x - 6=0

Solution: It is sufficient to exhibit one real number x such that x³ + 2x² - 5x - 6=0.

We check that x = -1 is one such real number.

Example 2. Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

Solution: Our great mathematician Ramanujan number 1729 is the best example.

1729 = 10³ +9³ = 12³ + 1³

It is a constructive existence proof.

Uniqueness proofs

The two parts of a uniqueness proof are

1. Existence: Ǝ an element x with the desired property exists.

2. Uniqueness: Ǝ if y ≠ x, then y does not have the desired property.

Another form of uniqueness

We can show that if x and y both have the desired property, then x = y

Example: Show that if a and b are real numbers and a 0, then there is a unique real number such that ar - b = 0

Solution :

1. Existence proof :

Given ar- b = 0

the real number r = b/a is a solution of ar - b = 0 consequently,

a real number r exists for which ar - b=0

2. Uniqueness proof:

Suppose that s is a real number such that as - b = 0.

Then ar - b = as - b where r = b/a

⇒ ar = as

⇒ r=s

This means that s ≠ r, then as - b ≠ 0.

This establishes the uniqueness part of the proof.