The most common type of mathematical theorem can be symbolized as p ⇒ q, where p and q may be compound statements. To assert that p ⇒ q is a theorem is to claim that p ⇒ q is a tautology; that is, that it is always true. From Section 1 we know that p ⇒ q is true unless p is true and q is false. Thus, to prove that p implies q, we have to show that whenever p is true it follows that q must be true. When an implication p ⇒ q is identified as a theorem, it is customary to refer to p as the hypothesis and q as the conclusion. The construction of a proof of the implication p ⇒ q can be thought of as building a bridge of logical statements to connect the hypothesis p with the conclusion q. The building blocks that go into the bridge consist of four kinds of statements: (1) definitions, (2) assumptions or axioms that are accepted as true, (3) theorems that have previously been established as true, and (4) statements that are logically implied by the earlier statements in the proof. The logical equivalences discussed in Section 1 provide alternate ways to join the blocks together. When actually building the bridge, it may not be at all obvious which blocks to use or in what order to use them. This is where experience is helpful, together with perseverance, intuition, and sometimes a good bit of luck. In building a bridge from the hypothesis p to the conclusion q, it is often useful to start at both ends and work toward the middle. That is, we might begin by asking, “What must I know in order to conclude that q is true?” Call this q₁. Then ask, “What must I know to conclude that q₁ is true?” Call this q₂. Continue this process as long as it is productive, thus obtaining a sequence of implications:

Then look at the hypothesis p and ask, “What can I conclude from p that will lead me toward q?” Call this p₁. Then ask, “What can I conclude from p1?” Continue this process as long as it is productive, thus obtaining

Example 3.3

Consider the function g(n, m) = n² + n + m, where n and m are understood to be positive integers. We saw that g(16, 17) = 162 + 16 + 17 = 172 . We might also observe that

On the basis of these examples (using inductive reasoning) we can form the conjecture “∀ n, q(n),” where q(n) is the statement

without having to do any computation. This is an example of deductive reasoning: applying a general principle to a particular case. Most of the proofs encountered in mathematics are based on this type of reasoning.