Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

3 Special Kinds of Theorems > Composite Statements - Pg. 58

58 CHAPTER 3 Special Kinds of Theorems Assume that the statement is true for a generic number n > b. Then consider a = n + 1. a = n + 1 = ðbq 1 + r 1 Þ + 1 = bq 1 + ðr 1 + 1Þ Since 0 r 1 < b, then 1 r 1 + 1 b. If r 1 + 1 b, then just set q 1 = q and r 1 + 1 = r. If r 1 + 1 = b, we can write a = bq 1 + b = bq + r where q = q 1 + 1 and r = 0. We are now going to prove the uniqueness part of the statement. Assume that there are two pairs of integers, q and r, q' and r', such that a = bq + r = bq' + r ' with q 0 and 0 r < b, and q' 0 and 0 r' < b. Without loss of generality we can assume that r' r (why?). Thus, bðq - q'Þ = r ' - r 0: Since r' > r' - r (why?), we have b > r' - r (why?). Therefore, b > bðq - q'Þ 0: Dividing by b we obtain 1 > q - q' 0: This implies that q - q' = 0 (why?), or q = q'. Since q - q' = 0, then r' - r = 0. So r' = r. The theorem is now completely proved. COMPOSITE STATEMENTS The hypothesis and/or the conclusion of a theorem might be composite statements that include the words "and," "or." Because of the more complicated structure of this kind of statement, we have to pay even more attention to details. After analyzing a composite statement, we can check whether it is possible to break it down into simpler parts, which can then be proved by using any of the principles and techniques already seen. Other times we will replace the original statement with another logically equivalent state- ment that is easier to handle. Multiple Hypotheses Multiple hypotheses statements are statements whose hypothesis are composite statements, such as "If A and B, then C," and "If A or B, then C." Let us start by examining statements of the form "If A and B, then C."