Examples of Direct Method of Proof

Example 1 (Version I): Prove the following universal statement:

The negative of any even integer is even.

Proof:

Suppose n is any [particular but arbitrarily chosen] even integer. [We must show that −n is even.] 

By definition of even number, we have

n = 2k for some integer k.

Multiply both sides by −1, we get

−n = −(2k)

= 2. (−k)

Now let r = -k. Then r is an integer [because a product of two integers is an integer],

                                            r = −k

                                              = (−1) k [and −1 and k are integers.]

Hence,

                                          −n = 2r for some integer r.

And so by definition of even number, −n is even. This what was to be shown.

And this completes the proof.

Example 1 (Version II): Prove the following universal statement:

The negative of any even integer is even.

Proof:

Suppose n is any even integer. By definition of even number,

n = 2k for some integer k

Then,

                                        −n = −2k

                                            = 2 (−k)

But, by definition of even number, 2(−k) is even [because -k is an integer (being the product of the integers −1 and k).]

Hence, −n is even. This is what was to be shown.

And this completes the proof.

Example 2: Prove the following universal statement:

If n is any even integer, then (−1)ⁿ = 1.

Proof:

Suppose n is even [particular but arbitrarily chosen] integer. [We must show that (−1)ⁿ = 1.]. Then by the definition of even numbers,

n = 2k for some integer k

Hence, by the laws of exponents of algebra, we have

                                                                        (−1)ⁿ = (v1)^2k

                                                                                = ((−1)²)^k

                                                                                = (1)^k

                                                                                = 1

This is what was to be shown.

And this completes the proof.

Example 3: Prove the following universal statement:

The product of any two odd integers is odd.

Proof:

Suppose m and n are any [particular but arbitrarily chosen] odd integers. [We must show that (m.n) is odd.]

By the definition of odd numbers, we have

                                                            n = 2r + 1 for some integer r

                                                           m = 2s + 1 for some integer s

Then, by substitution, we have

                                                        m . n = (2r + 1) . (2s + 1)

                                                                = 4rs + 2r + 2s + 1

                                                                = 2(2rs + r + s) + 1

Now, (2rs + r + s) is an integer [because products and sums of integers are integers and 2, r and s are all integers] and therefore, by definition of odd number, (m.n) is odd. This is what was to be shown.

And this completes the proof.

Example 4: Prove the following universal statement:

For all integers n, 4(n² + n + 1) − 3n² is a perfect square.

Proof:

Let n is any [particular but arbitrarily chosen] integer. [We must show that (4(n² + n + 1) − 3n²) is a perfect square.] Then, we have

                                            4(n² + n + 1) − 3n² = 4n² + 4n + 4 − 3n²

                                                                        = n² + 4n + 4

                                                                        = (n + 2)²

But is a perfect square [because (n+2) is an integer (being a sum of n and 2).] Hence, (4(n² + n + 1) − 3n²) is an integer, as was to be shown.

And this completes the proof.

Example 5: Prove the following universal statement:

Every integer is a rational number.

Proof:

Suppose n is any [particular but arbitrarily chosen] integer. [We must show that n is a rational number.] Then

                                        n = n . 1

and so

                                        n = n/1

Now n and 1 are both integers and 1 ≠ 0. Hence, n can be written as a quotient of integers with a nonzero denominator, and so n is rational.

And this completes the proof.

Example 6: Prove the following universal statement:

The sum of any two rational numbers is rational.

Proof.

Suppose r and s are rational numbers. [We must show that r + s is rational.] Then, by the definition of rational numbers, we have

                                            r = a/b    for some integers a and b with b ≠ 0.

                                            s = c/d   for some integers c and d with d ≠ 0.

So, by substitution, we have

                                            r + s = a/b + c/d

                                                    = (ad + bc)/bd

Now, let p = ad + bc and q = bd. Then, p and q are integers [because products and sums of integers are integers and because a, b, c and d are all integers. Also, q ≠ 0 by zero product property.] Hence,

r + s = p/q , where p and q are integers and q ≠ 0.

Therefore, by definition of a rational number, (r + s) is rational. This is what was to be shown.

And this completes the proof.

Example 7: Prove the following universal statement:

The product of any two rational numbers is a rational number.

Proof:

Suppose r and s are rational numbers. [We must show that r.s is rational.] Then, by definition of rational number, we have

                                r = a/b    for some integers a and b with b ≠ 0.

                                s = c/d   for some integers c and d with d ≠ 0.

So, by substitution, we have

                                            r . s = (a/b) . (c/d)

                                                    = (ac)/bd

Now, (ac) and (bd) are both integers (being product of integers) and (bd) ≠ 0 (by the zero product property). Hence, (r.s) is a quotient of integers with a nonzero denominator, and so by definition of rational number, (r.s) is rational. This is what was to be shown.

And this complete the proof.

Example 8: (Transitivity of Divisibility) Prove the following universal statement:

For all integers a, b and c, if a divides b and b divides c, then a divides c.

Proof:

We start from hypothesis by supposing a, b, and c are particular but arbitrarily chosen integers such that a divides b and b divides c. Our next step is to define our goal clearly, which is to show that a divides c. In other words, we need to show that

c = a (some integer)

From the hypothesis, we know [using the definition of divisibility] that

Since (a divides b), therefore, 

                                                b = a . r for some integer r ______________(1)

And since (b divides c), therefore, 

                                                c = b. s for some integer s ______________(2)

From equations 1 and 2, we see that equation 2 expresses c in terms of b, and equation 2 expresses b in terms of a. Therefore, if we substitute equation 1 into equation 2, we get an equation that expresses c in terms of a. And we will do exactly that:

                                                c = b . s

                                                  = (a . r) . s

But, by associative law of multiplication (a . r) . s = a . (r . s). Hence, the above equation becomes

                                                c = a . (r . s)

Now, we have c which expresses a as a . (something). Well! if we show that "something" is an integer, we are home free.

But, of course, that "something" is integer because it is a product of two integers. Therefore, by using the definition of divisibility, we can write:

a divides c

And this is what was to be shown.

This completes the proof.

Example 9: Now, we redo the "transitivity of divisibility" again, but this time formally. Prove the following universal statement of transitivity of divisibility:

For all integers a, b and c, if a|b and b|c, then a|c.

Proof:

Suppose a, b and c are [particular but arbitrarily chosen] integers such that a|b and b|c. [We must show that a|c.] By the definition of divisibility, we have

                                                    b = a . r    for some integer r

and                                               c = b . s   for some integer s

By substitution, we have

                                                    c = b . s

                                                       = (a . r) . s

                                                       = a . (r . s)

Let k = r . s. Then k is an integer [since it is a product of integers], and therefore,

c = a . k where k is an integer

Thus, a|c by definition of divisibility and this is what was to be shown.

And this completes the proof.

Example 10: Prove the following universal statement:

For all integer a, b and c, if a|b and a|c, then a|(b+c).

Proof:

Suppose a, b and c are any integers such that a|b and a|c. [We must show that a|(b+c).] By definition of divisibilty, we have

                                                        b = a . r     for some integer r.

and                                                  c = a . s     for some integer s.

Then, by substitution, we have

                                                    b + c = a . r + a . s

                                                            = a (r + s)

Let t = r + s. Then t is an integer [being a sum of integers], and thus

b + c = a . t for some integer t

Then, by definition of divisibility, a|(b+c) and this is what was to be shown.

And this completes the proof.