Review of Week 6: Proofs

Review of Week 6: Proofs#

Reading material for proofs:

Proofs#

Proofs have been an central element of our civilization for thousands of years. In Odyssey, Homer gives us proof of Ulysses identity when he describes how he is recognized by his aged, faithful dog. In Bible, the resurrected Christ allows Thomas to touch his wounds, leading to the first acclamation of Jesus as God (John 20:24–29). In the Lord of the Rings, Aragorn’s rightful claim to the thrones of Arnor and Gondor is established by the Ring of Barahir and his wielding of the Andúril sword. In fiction and scripture, proofs have been used to establish veracity of deeds and royal or divine status. Proofs satisfy our doubts and skepticism and give meaning to faith and theory alike.

In mathematics, proofs are arguments that establish the truthfulness of various statements. These arguments are based on the building blocks of mathematical systems: axioms, definitions, and theorems.

Direct proofs#

This is the easiest kind of proofs, relatively speaking. In direct proofs we usually have a statement of the form:

\[p\ \text{implies}\ q\]

The approach we take is to look at axioms, definitions, and theorems available to us based on \(p\) and find the right transformations to arrive to \(q\). For example, let’s consider

\[p=\text{if}\ n\ \text{is odd}\]

and

\[q=n^2\ \text{is odd}\]

In this example, if \(n\) is odd then \(n=2x+1\) and by squaring both sides,

\[\begin{split}n^2&=(2x+1)^2\\ &=4x^2+4x+1\\ &=2(2x^2+2x)+1\\ &= 2z+1\end{split}\]

where \(z=2x^2+2x\). So we showed that \(n^2=2z+1\) which is an odd number.

Sum of two odd numbers is an even number#

Another example of a direct proof is to show that if two numbers are odd, their sum is an even number, i.e.,

\[\text{if}\ m,n\ \text{odd} \Rightarrow m+n\ \text{even}\]

The proof is quite straight forward: if \(m\) is odd then \(m=2x+1\), i.e. it is, by definition, a multiple of 2 (\(2x\)) plus one. Similarly, \(n=2y+1\); where \(x\ \text{and}\ y\) are arbitrary integer numbers. Adding them together:

\[\begin{split}\left.\begin{array}{c}m=2x+1\\n=2y+1\end{array}\right\} \Rightarrow m+n &= 2x+2y+2\\ &= 2(x+y+1)\\ &= 2k\end{split}\]

with \(k=x+y+1\). Thus we showed that the sum of two odd numbers is a multiple of 2, which by definition is an even number.

The product of odd and even numbers is an even number#

Another direct proof is to show that the product of an odd and an even number is an even number. Assuming \(m=2x+1\) (the odd number) and \(n=2y\) (the even number), their product \(mn\) is:

\[mn = (2x+1)2y = 4xy+2y = 2(2xy+y)\]

In other words, \(mn\) is a multiple of 2, therefore an even number.

The square of an even number is an even number#

Can show that if \(n\) is even, then \(n^2\) is also even? An even number is a multiple of 2, so we can write \(n=2x\). Squaring both sides gives us \(n^2=4x^2=2(2x^2)=2z\), where \(z=2x^2\). By showing that \(n^2=2z\) we have proved that \(n^2\) is even.

Proofs by contradiction#

Some times, a direct proof may not be possible. For example, can we prove that if \(n^2\) is even then \(n\) is also even? Trying a direct proof we can write:

\[n^2=2x \Rightarrow n=\sqrt{2x}\]

There is no way to tell if \(\sqrt{2x}\) is an odd or even number. Clearly, a direct proof approach does not work in this case. What if we took a different approach and assumed that if \(n^2\) is even then \(n\) is odd? If \(n\) is odd, then \(n=2x+1\). And by squaring both sizes of the equation,

\[\begin{split}n^2&=(2x+1)^2\\ &=4x^2+4x+1\\ &=2(2x^2+2x)+1\\ &=2z+1\end{split}\]

with \(z=2x^2+2x\). Therefore \(n^2\) is an odd number though our initial assumption is that \(n^2\) is even. By assuming the opposite conclusion of the statement we tried to prove, we reach a contradiction and that allows us to conclude that the initial statement was actually true.

In general, a proof by contradiction works when a statement of the form

\[h\ \Rightarrow \ c\]

cannot be proved directly; here \(h\) and \(c\) are the hypothesis and conclusion parts of the statement and “\(\Rightarrow\)” means “implies”. In this case, the proof by contradiction can be established as follows.

First, we assume that the opposite conclusion is true, i.e., that \(h\Rightarrow\neg c\) is true. Remember, “\(\neg\)” is the negation operator and therefore \(\neg c\) is the opposite of \(c\).

Next, given that we accept \(h\Rightarrow\neg c\) as true, we can now focus on its conclusion and test if we can derive \(h\) from \(\neg c\). In other words, given that \(h\Rightarrow\neg c\) is true can we show that \(\neg c\Rightarrow h\)? Attempting to do so will yield a result other than \(h\). Therefore the assumption \(h\Rightarrow\neg c\) that allowed us to test if \(\neg c\Rightarrow h\), is false. If \(h\Rightarrow\neg c\) is false, then \(h\Rightarrow c\) must be true. And that concludes our proof!

To illustrate this method, let’s look at the earlier example:

\[\begin{split}h&:\ n^2\ \text{even} \\ c&:\ n\ \text{even} \\ \text{prove}&:\ h\Rightarrow c \\ \text{no direct proof available;}\\ \text{trying contradiction}\\ \text{assume true}&:\ h\Rightarrow\neg c \\ \neg c&:\ n\ \text{not even, i.e.,}\ n\ \text{odd} \\ h\Rightarrow\neg c&:\ \text{if}\ n^2\ \text{even}\Rightarrow n\ \text{odd} \\ n&=2x+1 \\ n^2&=(2x+1)^2 \\ &=4x^2+4x+1\\ &=2(2x^2+2x)+1 \\ &=2z+1,\ (\text{where}\ z=2x^2+2x\\ n^2&:\ \text{odd}\\ \text{but}&:\ \text{we assumed}\ h\ (n^2\ \text{even})\\\end{split}\]

Example: if \(n^2\) is odd then \(n\) is odd#

If we tried direct proof here, we’ll end with the expression \(n=\sqrt{2x+1}\) which is of inconclusive parity. Therefore, a proof by contradiction may be a better strategy. Our hypothesis is \(h:\ n^2\ \text{odd}\). Our conclusion is \(c:\ n\ \text{odd}\). And since we cannot prove directly \(h\Rightarrow c\), we will assume that \(h\Rightarrow\neg c\) is true. Given this assumption, \(n\) is odd and therefore \(n=2x\). Squaring both sides of the equation:

\[\begin{split}n^2&=4x^2 \\ &= 2(2x^2) \\ &= 2z,\ (\text{where}\ z=2x^2)\end{split}\]

Therefore \(n^2\) is an even number contrary to the assumed truthfulness of \(h\Rightarrow\neg c\). Our assumption \(h\Rightarrow\neg c\) is false, leading to the conclusion that \(h\Rightarrow c\) is true. In other words, if \(n^2\) is odd then \(n\) is also odd.

Example: if \(a,b \in \mathbb{Z}\) then \(a^2-4b\neq 2\)#

The hypothesis here is \(h:\ a,b \in \mathbb{Z}\). And the conclusion is \(c:\ a^2-4b\neq 2\). There is no direct way to show \(h\Rightarrow c\), and it would seem that a proof by contradiction is the preferred strategy. We begin by assuming that \(h\Rightarrow\neg c\) is true, i.e., there are integer numbers \(a,b\) such that \(a^2-4b=2\). Given that, we can write:

\[\begin{split}a^2-4b&=2 \\ a^2&=4b+2 \\ &2(2b+1)\end{split}\]

From the above we can tell that \(a^2\) is even and therefore \(a\) is also even and thus can be written as a multiple of 2: \(a=2x\) and substituting this in the original expression:

\[\begin{split}a^2-4b &= 2 \\ (2x)^2-4b &= 2 \\ 4x^2-4b &= 2 \\ 2x^2-2b &= 1 \\ 2(x^2-b) &= 1\\ 2z &=1,\ (\text{where}\ z=x^2-b)\end{split}\]

We just concluded that \(1\) is an even number! That’s because the assumption that led us to this astonishing conclusion is false. The assumption was that there are integer numbers \(a,b\) such that \(a^2-4b=2\). This assumption is false which means that there are no integers \(a,b\) such that \(a^2-4b=2\). Therefore, the original statement \(a,b \in \mathbb{Z}\Rightarrow a^2-4b\neq 2\), is true.

Example: there is no largest number#

Let’s suppose that there is a largest number, \(L\), such that \(L\geq x,\ \forall x\). Given that \(1>0\), we can add \(L\) to both sides, resulting to \(L+1 > L\) which cannot be true, because we assumed that \(L\) is the greatest number, and we just showed that it’s less than \(L+1\).

Mathematical Induction#

Mathematical induction – often, just induction – is one of the simplest and yet most challenging concepts to master. It is also one of the most rewarding proof techniques. Induction allows us to prove a property for natural numbers, for which we have a hunch but we need solid proof. For example, we believe that the sum of the first \(n\) numbers is \(n(n+1)/2\). In fact, every time we try for a different \(n\), our hunch turns out to be true:

\[\begin{split}n=3,\ \ 1+2+3 = 6 &= \frac{3(3+1)}{2}=\frac{12}{2} \\ \\ n=4,\ \ 1+2+3+4 = 10 &= \frac{4(4+1)}{2}=\frac{20}{2} \\ \\ n=5,\ \ 1+2+3+4+5 = 15 &= \frac{5(5+1)}{2}=\frac{30}{2}\end{split}\]

There is a story that when Gauss was 10 years old, he derived the sum formula

\[1+2+\ldots+n = \frac{n(n+1)}{2}\]

with a simple observation. When he was asked by a teacher to calculate the sum for \(n=10\), he noticed that

\[\begin{split}1+2+3+4+5&+6+7+8+9+10 = \\ \\ (1+10) + (2+9) + (3&+8) + (4+7) + (5+6) = \\ \\ 11 + 11 &+ 11 + 11 + 11 = \\ \\ 5\cdot 11 & = \frac{10}{2}\cdot (10+1)= \\ \\ \frac{n}{2}&\cdot (n+1)\end{split}\]

But deriving a formula is not the same as proving it. We can claim that the formula \(1+2+\ldots+n = n(n+1)/2\) works for \(n=3\) or 4 or 5 or even 10, but that doesn’t mean that it works for every natural number. We need a more rigorous tool to prove this property. The rigor, in this case, comes from the axiomatic foundation of natural numbers.

In 1889, Giuseppe Peano, an Italian mathematician, put together a few fundamental statements about natural numbers. These statements, known as Peano’s Axioms, are the building blocks of the natural numbers set \(\mathbb{N}\). An axiom is a statement that we accept as true. Peano stated five axioms. The last one is the rigorous tool we need to prove \(1+2+\ldots+n = n(n+1)/2\). It is worth, however, to review all five axioms first.

Before stating his axioms, Peano defined a successor function, i.e., a function that takes a natural number as input and returns the next successive natural number:

\[S(n) = n+1\]

Using the successor function, we can write:

\[\begin{split}1 &= S(0) \\ 2 &= S(S(0)) \\ 3 &= S(S(S(0)))\\ &\vdots\end{split}\]

Peano’s Axioms#

  1. \(0\) is a natural number.

  2. For every natural number \(x\), its successor \(S(x)\) is also a natural number.

  3. For two natural numbers \(x, y\), if \(x=y \Leftrightarrow S(x)=S(y)\).

  4. There is no natural number \(x\) such that \(S(x)=0\).

  5. If a set \(K\) contains \(0\), and if for every natural number \(n\) being in \(K\) implies that \(S(n)\) is also in \(K\), then \(K\) contains every natural number.

The last axiom is the basis for mathematical induction. Let’s demonstrate it with the summation formula \(1+2+\ldots+n = n(n+1)/2\). We want to show that the formula works for every natural number. So far, we have shown that it works for \(n=3, 4, 5\) and \(10\).

We start by defining a set \(K\) to contain the natural numbers that we have shown to work with the formula: \(K=\{3, 4, 5, 10\}\). We can show that \(0\) also belongs to \(K\), because \(0=0\cdot(0+1)/2\). Thus, set \(K\) fulfills the first condition of the induction axiom, i.e., \(0 \in K\).

The next step is to assume that a natural number \(n\) is in \(K\) and then prove that \(n+1\) is also in \(K\). If we do, then we prove (based on Peano’s fifth axiom) that all natural numbers are in set \(K\); or in other words \(K=\mathbb{N}\). And why is this important? Because \(K\) is the set with the numbers for which the sum formula works. And if \(K=\mathbb{N}\), then the formula works for every natural number, which is the proof we wanted!

Let’s assume then that \(n\in K\), therefore:

\[1+2+\ldots + n = \frac{n(n+1)}{2}\]

Next we examine if and how we can show that \(n+1\) is in \(K\). If — and for now, that’s a big if — this is true, if \(n+1\) is indeed in K, we expect that

\[1+2+\dots + n +(n+1) = \frac{(n+1)(n+2)}{2}\]

Our objective now is to start from the left side of the expression above and see if we can arrive to the right side. When we observe the left side:

\[1+2+\dots + n +(n+1)\]

we notice that it contains the expression from the case for \(n\). And since we assumed that the case is true, we can substitute \(1+2+\ldots + n\) with \(\frac{n(n+1)}{2}\). The substitution give us:

\[\begin{split}1+2+\dots + n +(n+1) =\\ \\ \frac{n(n+1)}{2} + (n+1) = \\ \\ \frac{n(n+1)+2(n+1)}{2} = \\ \\ \frac{(n+1)(n+2)}{2}\end{split}\]

And so, we have shown that

\[1+2+\dots + n +(n+1) = \frac{(n+1)(n+2)}{2}\]

and therefore \(n+1\in K\). Or, in other words, every natural number belongs to \(K\) and thus \(K=\mathbb{N}\).

The “price of admission” to set \(K\) is for a natural number \(n\) to satisfy the formula \(1+2+\ldots + n = n(n+1)/2\). And since we showed that all natural numbers are in \(K\), we have proved that the formula works for any natural number.

A template for induction proofs#

Induction problems ask us to prove a property of the form

\[L(n) = R(n)\]

In the example above, \(L(n)= 1+2+\ldots+n\) and \(R(n)=n(n+1)/2\).

Given a problem in the form \(L(n)=R(n)\), the induction proof can be done in three steps.

Step 1#

Show that \(L(n)=R(n)\) holds for \(n=1\). (Yes, Peano says to show for \(n=0\) but \(1\) is just as good).

Step 2#

Assume that \(L(n)=R(n)\) holds for \(n=k\), i.e., \(L(k)=R(k)\) is true.

Step 3#

Start with \(L(k+1)\) and show that it equals \(R(k+1)\). You will notice that the expression \(L(k+1)\) always contains \(L(k)\). And since you just assumed that \(L(k)=R(k)\) in Step 2, you can write

\[\begin{split}L(k+1) &= L(k) + (n+1) \\ &= R(k) + (n+1)\end{split}\]

From here, the problem is reduced to simple (usually) derivations to show that \(R(k) + (n+1) = R(k+1)\). Showing that, completes the proof.

Examples#

The summation formula#

Prove that

\[1+2+\ldots + n = \frac{n(n+1)}{2}\]

We worked this formula above to demonstrate the inductive method. We repeat the proof here in a more formal manner.

Step 1#

For this step, first we need to identify the expressions \(L(n)\) and \(R(n)\). In this case, it’s fairly easy:

\[\begin{split}L(n) &= 1+2+\ldots + n \\ \\ R(n) &= \frac{n(n+1)}{2}\end{split}\]

Next we have to test if \(L(n)=R(n)\) for a specific value of \(n\). Peano said to use \(n=0\) but we prefer to test for \(n=1\).

\[\begin{split}L(1)&=1 \\ \\ R(1)&=\frac{1(1+1)}{2}=1\end{split}\]

So, \(L(1)=R(1)\).

Step 2#

This is a simple and quick step. We only have to state that for an arbritrary \(n=k\) the expression \(L(k)=R(k)\) is true; in other words:

\[1+2+\ldots +k = \frac{k(k+1)}{2}\]
Step 3#

Here we use the next number up from the previous step. In Step 2 we looked at \(n=k\). The next number up is \(k+1\). The question we must answer in this step now is if \(L(k+1)\) equals \(R(k+1)\).

\[L(k+1) = 1+2+\ldots +k + (k+1)\]

Notice that \(L(k+1)=L(k)+k+1\). Step 2 empowers us to replace \(L(k)\) with \(R(k)\), therefore

\[\begin{split}L(k+1) &= \underbrace{1+2+\ldots +k}_{=L(k)=R(k)} + (k+1) \\ \\ &= R(k)+(k+1) \\ \\ &= \frac{k(k+1)}{2} + (k+1)\\ \\ &= \frac{(k+1)(k+2)}{2} \\ \\ &= R(k+1)\end{split}\]

We just proved that given \(L(k)=R(k)\) the equation holds for the successor of \(k\) as well, \(L(k+1)=R(k+1)\), and thefore the original expression

\[1+2+\ldots + n = \frac{n(n+1)}{2}\]

is true for every natural number.

The stamps problems#

Show that any postage amount greater than $0.17 can be formed with $0.03 and $0.10 stamps. For example, $0.22 worth of postage comprises one $0.10 stamp and four $0.03 stamps.

Step 1#

Problems like this one do not have a readily available expression of the form \(L(n)=R(n)\). We have to derive the formula by restating the problem. Basically, the problem says that any number greater than 17 can be written as the sum of multiples of 3 and multiples of 10:

\[ \begin{align}\begin{aligned}n&=3a+10b\\n&\geq 18\end{aligned}\end{align} \]

Here \(L(n)=n\) but what about \(R(n)\)? The right side of the question does not contain \(n\). Or does it? We can always write \(3b+10b=3a+10b+0n\), and this will be our \(R(n)\). So the problem is restated as follows:

\[\underbrace{n}_{L(n)} = \underbrace{3a+10b+0n}_{R(n)}\]

Now that we have established \(L(n)\) and \(R(n)\) we have to test that they hold true. We cannot test for \(n=1\) because the problem states that the property applies only to numbers \(n\geq 18\). So we should try for \(L(18)=R(18)\), in other words, can we write 18 as a sum of multiples of 3 and 10? Indeed we can:

\[ \begin{align}\begin{aligned}18 =3a+10b\\\text{when}\ a=6, b=0\end{aligned}\end{align} \]
Step 2#

This is the easiest step of the proof. We assume that the property holds for an arbitrary integer \(k\), i.e., \(L(k)=R(k)\).

Step 3#

Can we now prove that the property works for \(S(k)\), by working our way from \(L(k+1)\) to \(R(k+1)\). Just remember that for this problem, \(R\) simply means a sum of multiples of 3 and 10.

\[ \begin{align}\begin{aligned}L(k+1) &= k+1\ \ \ \ (\text{and from step 2,}\ k=3a+10b)\\ &=3a+10b+1\ \ \ \ (\text{rewrite}\ 1=10-9)\\ &=3a+10b+10-9\\ &=3(a-3)+10(b+1)\ \ \ \ (\text{substituting}\ a'=a-3,\ b'=b+1)\\ &=3a'+10b'\end{aligned}\end{align} \]

What the expression above says is that \(k+1\) is also a sum of multiples of 3 and 10, and therefore \(L(k+1)=R(k+1)\).