In the first segment on methods of proof, we learned about how mathematical knowledge is discovered and added to the knowledge base of the discipline. For abstract discoveries -- truths that apply to entire sets of objects aat a time without depending on specific instances -- the means of solidifying knowledge consist in proof. This is a clear, logical, persuasive argument that an abstract statement is always true. We talked about what a proof isn't -- for example a list of examples does not constitute a proof, nor does an abstract argument that isn't sufficiently clear or convincing. In this lesson we begin to learn what a proof is, and how to write one. We'll begin with the simplest possible kind of mathematical proposition to prove, the conditional statement which has the form If $A$, then $B$. The method we will learn is called direct proof and it follows directly (see what I did there?) from the truth table from a conditional statement.
Basic:
Advanced:
We've seen what a proof of an abstract mathematical proposition isn't. It is not a list of examples; nor is it an unclear and poorly written argument. But what is a proof? Well, a proof is a convincing and persuasive argument that explains exactly why a general, asbtracted conjecture is always true. But there is more than way that such an argument can look.
Sometimes a proof is an argument based on using pre-existing knowledge used in a clever way:
Theorem: For any positive integer $n$, we have $$\sum_{i=0}^n \left( {\begin{array}{*{20}c} n \\ i \\ \end{array}} \right) = 2^n$$
Proof: The Binomial Theorem states that for any $x$ and $y$, $$(x+y)^n = \sum_{i=0}^n \left( {\begin{array}{*{20}c} n \\ i \\ \end{array}} \right) x^{n-i}y^i$$ To get the result in the theorem statement, just plug in $x=1$ and $y=1$. On the left side of the Binomial Theorem we get $(1+1)^n = 2^n$. On the right side, we get $$\sum_{i=0}^n \left( {\begin{array}{*{20}c} n \\ i \\ \end{array}} \right) 1^{n-i}1^i = \sum_{i=0}^n \left( {\begin{array}{*{20}c} n \\ i \\ \end{array}} \right)$$ This is what we wanted to show, so we are done. $\square$
Aside: Once a conjecture has been proven, we call it a theorem (sometimes "proposition"). And in a proof of a theorem we often put some kind of symbol at the end to tell the reader we are done; here, I used a square $\square$.
So that's a clever use of the Binomial Theorem to prove an interesting result. But it may leave you with a very important question: How do we know that the Binomial Theorem is true? That's a good question because we want to ask Why is this true? for any mathematical result we meet. Technically we should treat the proof above as a tentative proof, contingent on our finding a proof for the Binomial Theorem.
At other times a proof uses definitions of terms and puts them together in logical ways to derive something new. For example, here's an important pair of definitions:
Definition: An integer $n$ is said to be even if there is an integer $k$ such that $n = 2k$. An integer $n$ is said to be odd if there is an integer $k$ such that $n = 2k+1$.
For example, $48$ is even because $48 = 2 \cdot 24$; and $77$ is odd because $77 = 76 + 1 = 2\cdot 38 + 1$.
Using these definitions of even and odd numbers, we can prove a result we have taken for granted for a long while:
Theorem: An even number times an odd number is an even number.
Proof: Suppose $a$ is even and $b$ is odd. Then there exist integers $x$ and $y$ such that $a = 2x$ and $b = 2y+1$. Multiplying these together gives us: $$ab = (2x)(2y+1) = 2(2xy + x)$$ Since $x$ and $y$ are integers, $2xy + x$ is also an integer. Therefore we have expressed $ab$ as $2c$ where $c$ is an integer. Hence $ab$ is even. $\square$
Note the structure of this second proof. We started off by making an assumption: That we have two integers, and they are called $a$ and $b$ with $a$ even and $b$ odd. In other words we begin by assuming we have the information needed to argue the result. Then, we used the definition of even and odd to rewrite the objects involved in a different form -- for example, $a = 2x$ for some integer $x$. Then we progressed logically by making mathematical steps and using definitions again to arrive at our result, and we clearly state when we have finished.
Questions for you to consider about this proof:
Now consider this proposition:
For every $n \in \mathbb{Z}$, if $n$ is even then $n^2$ is even.
This is a special kind of proposition because it is a conditional statement or "if-then" statement. These are very common in mathematics and in CS, and we can use some of our logic knowledge to help in constructing a proof.
First, recall that the hypothesis of a conditional statement is the "if" part; and the "then" part is called the conclusion. Here, "$n$ is even" is the hypothesis and "$n^2$ is even" is the conclusion.
Second, recall the truth table of a conditional statement "If $p$, then $q$":
$p$ | $q$ | $p \rightarrow q$ |
---|---|---|
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
Whenever the hypothesis of a conditional statement is false, the conditional statement is true. Therefore, if we are trying to prove that a conditional statement is true, we can ignore any situation in which the hypothesis is false because the conditional statement is true automatically in that case. That is: We can assume that the hypothesis is true when proving a conditional statement.
A proof of a conditional statement can therefore proceed as follows:
An argument of this form is called a direct proof of a conditional statement. Here is an example, broken up line by line with justification provided for each line so you can see the flow of the argument.
Theorem: For every $n \in \mathbb{Z}$, if $n$ is even then $n^2$ is even.
Proof:
Notice, again, that in a well written proof:
Before proceeding on to the exercises, watch the following videos:
For the following exercises, consider the conditional statement:
For each integer $a$, if $4$ divides $a-1$, then $4$ divides $a^2 - 1$.
Put in your answers to the exercises here: http://bit.ly/1NkzZmW