Proof by cases(4)

If a and b  are real numbers.

Case 1: Assume that a >= 0, b >= 0. Then |a| = a, |b| = b, and |a - b| = a - b. So in this case
||a| - |b|| = |a - b| =< |a - b|.

Case 2: Assume that a >= 0, and b < 0. Then |a| = a and |b| = -b.

-Sub-case 1: Assume that |a| >= |b|, then 0=< a + b =< a =< a - b.
So |a + b| < |a - b| giving us

||a| - |b|| = |a + b| < |a - b|.

-Sub-case 2: Assume that |b| > |a|, then we have both 0 < -b =< a - b, and b < a + b < 0. So it follows that |a + b| < |a - b| giving us

||a| - |b|| = |a + b| < |a - b|

Case 3: Assume that a < 0, and b >= 0. Then |a| = - a and |b| = b.
-Sub-case 1: Assume that |a| >= |b|, then 0 < - a =< b - a = |a - b|, and a=< a + b =< 0. So that |a + b| =< |a - b|. It follows that

||a| - |b|| = |- a - b| = |a + b| =< |a - b|.

-Sub-case 2: Assume that |b| > |a|, then a - b =< - a - b< 0. This gives us |- a - b| =< |a - b|. So again
||a| - |b|| = |- a - b| =< |a - b|.

Case 4: Assume that a < 0, and b < 0. Then |a| = - a and |b| = - b.
Then in this case
||a| - |b|| = |- a + b| = |a - b| =< |a - b|.

So in all cases ||a| - |b|| =< |a - b|

QED

Proofs by Case (3)

(3) If n is an even integer, then n = 4j or n = 4j - 2 for some integer j.

Proof. Assume that n is an even integer. Then n = 2k for some integer k.
Case 1: Assume that k is even. Then k = 2p for some integer p. So in this case

n = 2k = 2(2p) = 4p

and the results holds.

Case 2: Assume that k is odd. Then k = 2p + 1 for some integer p. So in this case

n = 2k = 2(2p + 1) = 4p + 2 + 4 - 4 = 4(p - 1) - 2 = 4j - 2

where j = p - 1 is an integer, and therefore the result holds.

So in all cases n = 4j or n = 4j - 2 for some integer j.

QED

Proofs by Case (2)

Write clear and complete proofs by cases for the mathematical statement.

(2) If x is a real number, then |x - 1| + |x + 5| >= 6.

Proof. Assume that x is a real number. Consider the following cases:

Case 1: Assume that x  < -5. In this case x - 1 < 0, and x + 5 < 0. So |x -1| = -(x - 1) = 1 - x, and |x + 5| = -(x + 5) = -5 - x. Then

|x - 1| + |x + 5| = 1 - x - 5 - x = -4 - 2x > -4 -2(-5) = -4 + 10 = 6.

So in this case |x - 1| + |x + 5| >= 6.

Case 2: Assume that -5 =< x < 1. In this case x - 1 < 0, and x + 5 >= 0.

So |x - 1| = -(x - 1) = 1 - x, and |x + 5| = x + 5. Then

|x - 1| + |x + 5| = 1 - x + x + 5 = 6 >= 6.

Case 3: Assume that x >= 1. In this case x - 1 < 0, and x + 5 >= 0. So

|x - 1| = x -1 and |x + 5| = x + 5. Then

|x - 1| + |x+5| = x - 1 + x + 5 = 2x + 4 >= 2(1) + 4 = 6

So in all cases |x - 1| + |x + 5| >= 6.

QED

Proofs by Case (1)

Write clear and complete proofs by case for the following statement.

(1) If x is a real number, then |x + 3| - x > 2.

Proof. Assume that x is a real number.

- Case 1: Assume that x >= -3, so that x + 3 >= 0. In this case |x + 3| = x + 3. So we have

              |x + 3| - x = x + 3 - x = 3 > 2.

- Case 2: Now assume that x < - 3, so that x + 3 < 0. In this case |x + 3| = -(x + 3) = - 3 - x. So we have

|x + 3| - x = - 3 - x -x = - 2x - 3 > -2(-3) -3 = 6 - 3 = 3 > 2.

So in all cases |x+3| - x > 2.

QED

Direct Proofs (4)

(4) If m is odd, then m^2 + 1 is even.

Proof. Assume that m is odd. Then m = 2k + 1 for some integer k. So
       
          m^2 + 1 = (2k +1)^2 + 1
                        = 4k^2 + 4k + 1 + 1
                        = 4k^2 + 4k +2
                        = 2(2k^2 + 2k + 1)
                        = 2q

where q = 2k^2 + 2k + 1 is an integer. So m^2 + 1 is even.

QED

Basic Proofs Methods II

Two-part proof of P <=> Q
(i) Show P => Q by any method.
(ii) Show Q => P by any method.
Therefore, P => Q

Example. Let a be a prime, and b and c be positive integers. Prove that a divides the product bc if and only if a divides b or a divides c.

Proof.
(i) Suppose a is a prime and a divides bc. By the Fundamenta Theorem of Arithmetic, b and c may be written uniquely as products of primes: b = p1p2p3...pkq1q2q3...qr. Since a is a prime and a divides bc, a is one of the prime factors of bc. Thus, either a = pi for some i or a = qj for some j. If a = pi, then a divides b. If a = qj, then a divides c. Therefore, either a divides b or a divides c.
(ii) Suppose a divides b or a divides c.If a divides b, then a divides bc. If a divides c, then again a divides bc. In either case, a divides bc.

QED

Number Theory-Divisibility (1)

Proper divisor. We say that a is a proper divisor of b if a | b and a < b.

For example, 3 is a proper divisor of 6, but 6 is not a proper divisor of 6. Note that for any b, all divisors of b are proper except for b itself.

Nontrivial divisor. We say that a is a nontrivial divisor of b if a | b and 1 < a < b.

For example, the nontrivial divisors of 6 are 2 and 3. Note that 1 is a proper divisor of every large integer, but 1 has no trivial divisors. The following theorem states some properties of divisibility.

Theorem 2.1
Properties of Divisibility
D1: 1 | a and a | a for all a.
D2: If a | b, then a =< b
D3: If a | b and b | a, then a = b.
D4: If a | b and b | c, then a | c.
D5: For all c, a | b if and only if ac | bc.
D6: If a | b and c | d, then ac | bd
D7: If a | b and a | c, then a | (bx + cy) for all x, y

Proof of D2: If a | b, then by proper division, b = ka for some k >= 1, so ka >=a, that is b >=a.
QED

Proof D4: If a | b and b | c, then b = ka and c = jb for some k and j. Therefore c = k(ka) = (jk)a, so a | c.
QED

Proof of D7: If a |b and a | c, then b = ka and c = ja for some j, k. Therefore, bx + cy = (ka)x + (ja)y =
(kx + jy)a, so a | (bx + cy).
QED

Remarks
In order to prove that m = n, it is sometimes convenient to use D3, that is, to prove that m | n and n | m.