1.1 Proofs
A proof is a sequence of steps of deductive reasoning, starting from a premise and leading to a conclusion.
A premise is a logical statement, or collection of logical statements, that we accept as true without requiring any validation.
A conclusion is a logical statement that we can assert is true after discovering a proof.
Suppose for example that we wanted to prove the assertion that
The first thing we need to do is decide what “basic truths” we have at our disposal for this particular problem. In other words, what is the premise on which the proof is based.
In this case, we know that we have a number \(x\) that is even and a number \(y\) that is odd. In other words, there are numbers \(a\) and \(b\) such that
\[ x = 2a\text{ and }y=2b+1. \]
So our premise is that \(x=2a, y=2b+1\) for some numbers \(a\) and \(b\).
Now it can be helpful to think about what our conclusion might look like in terms of the premise.
The conclusion is that \(xy = 2c\) for some number \(c\).
Here is a valid proof.
Proof. Let \(x=2a\) and \(y=2b+1\) for some numbers \(a\) and \(b\).
Then \(xy = 2a(2b+1) = 2(a(2b+1))\) and so \(xy\) is even.
Here is another, very famous, example of a proof.
Given a right angled triangle
with side lengths \(a\), \(b\) and \(c\) as shown, prove that \(a^2+b^2 = c^2\).
This is known as Pythagoras Theorem and there are thousands of different proofs of this result. The proof we will look at here is very simple and elegant.
Proof The premise of this proof is that we have a right angled triangle with side lengths \(a\), \(b\) and \(c\).
The conclusion is that \(a^2+b^2 = c^2\).
Here is a geometric argument to get from the premise to the conclusion.
Start by arranging four copies of the right angles triangle in the following way.
Then rearrange them as in the following picture.
Notice that the area of the green square on the left is \(c^2\), while the green squares on the right have area \(a^2\) and \(b^2\).
Proofs such as this were known to the ancient Chinese and ancient Indian Mathematicians and there is even evidence from clay tablets that the Babylonians knew of Pythagoras Theorem.
Direct Proofs
Many of the statements that we shall want to prove can written in the form \[ \text{If }P\text{ then }Q. \] When is such a statement true?
The statement can be written symbolically as \(P\implies Q\).
We shall see some examples of this later in the course.
Notice that \(P\implies Q\) is only false when \(P\) is true and \(Q\) is false. So to prove that \(P\implies Q\) is true, we need only ensure that this exceptional case never happens.
In other words to show \(P\implies Q\) is true we need only assume that \(P\) is true and then deduce that \(Q\) is also true.
The previous two examples of proof are often referred to as direct proofs. We start with the premises given and put forward an argument to manipulate the information to arrive at new true statements until we get to the desired conclusion.
Contradiction and Contrapositive
There are other methods of proof that we shall meet in the course and we briefly mention here two others that are commonly used. We shall include some examples when we meet them in the number theory part of the course.
Proof by contradiction. The idea here is to essentially prove that the negation is false. If we start with a statement \(A\) and apply a valid logical argument to that, we should expect the resultant statement \(B\), say, to be a true statement. If we actually find out that \(B\) is false, then \(A\) must have been false in the first place. So the idea behind proving \(P\) by contradiction is to start with \(\lnot P\), and perform a sequence of valid logical deductions until we arrive at a statement \(F\), say, that is clearly false (a contradiction). We then deduce that \(\lnot P\) is actually false and hence \(P\) is true. Symbolically, we are trying to prove the truth of the implication \(\lnot P\implies F\), which is logically equivalent to \(\lnot(\lnot P)\lor F \equiv P\lor F\equiv P\).
Proof by contrapositive. Recall that the contrapositive of \(P\implies Q\) is \((\lnot Q)\implies(\lnot P)\). So if we can prove that the contrapositive is actually true, then the original statement is also true.
Proof. We use proof by contrapositive. The statement can be written as \[ x^2\text{ is even }\implies x\text{ is even} \] and the contrapositive is \[ x\text{ is odd }\implies x^2\text{ is odd}. \]
So we prove thatTo prove this we assume that \(x\) is odd and try to deduce that \(x^2\) is also odd.
Here is a very simple proof.
If \(x\) is odd then \(x=2a+1\) for some number \(a\).
Then \(x^2 = (2a+1)^2 = 4a^2 + 4a + 1 = 2(2a^2+2a)+1\) and so \(x^2\) is also odd.
Let \(x\) and \(y\) be integers. Prove that \[ x^2-4y\ne 2. \]
Proof. We use proof by contradiction.
The negation of the statement is \[ x^2 - 4y=2. \]
So we start with this premise and try to deduce something that we know to be false.
Assume \(x^2-4y=2\).
Then \(x^2 = 2+4y\) and so \(x^2\) is even.
From the previous proof that means that \(x\) is even and so \(x = 2z\) for some number \(z\). Hence \(2 = x^2-4y = (2z)^2 - 4y = 4z^2 - 4y = 4(z^2-y)\).
Dividing by \(2\) we see that \(1 = 2(z^2-y)\) and so \(1\) must be an even number.
This is clearly false and so \(x^2-4y\ne2\).
We mentioned earlier that proof by contradiction can be represented symbolically as \(\lnot P\implies F\) where \(F\) is any (in practice a suitable) contradiction. If we denote \(\lnot F\) by \(T\), which is then a tautology, then the contrapositive of this implication is \(T\implies P\), and so is also logically equivalent to \(P\). This signifies that, in order to prove \(P\), we may start with a suitable tautology \(T\) and use that to deduce the truth of the statement \(P\).
In practice, these suitable tautologies are either theorems which we have earlier proved, or logical statements which are self-evidently true, in the sense that we do not require any justification of them. Statements of this kind are referred to as axioms.
In Chapter 2, we shall learn more of Euclid, who, whilst being famous for many things, his most important contribution to mathematics was the formulation of the axiomatic method.
In all of his writings he carefully sets out his assumptions and his rules for reasoning and then develops mathematical theory relying only on those rules or axioms.
Each part of mathematics has its own axioms; in planar geometry they include statements like: through every distinct pair of points \(x,y\) there lies a unique line. In number theory the axioms concern the structure and operation of a particular set, the set of integers. These rules allow us to carefully check statements about the integers to see if they are true or not.
We denote the set of integers by \(\mathbb{Z}\). This set contains two special elements \(0\) and \(1\). The integers satisfy the following axioms:
- [A1] We may add, subtract or multiply integers. These operations are denoted by the symbols \(+, -, .\) respectively.
- [A2] For any integer \(m\), \(m+0=0+m=m\) and \(m.1=1.m=m\).
- [A3] For any integer \(m\), \(m-m=0\)
- [A4] Addition and multiplication are commutative, i.e. \(m+n=n+m\) and \(m.n=n.m\) for all \(m,n\in \mathbb{Z}\)
- [A5] Addition and multiplication are associative, i.e. \((m+n)+p=m+(n+p)\) and \(m.(n.p)=(m.n).p\) for all \(m,n,p\in \mathbb{Z}\)
- [A6] Multiplication distributes over addition, i.e, \(m.(n+p)=m.n + m.p\) for all \(m,n,p\in \mathbb{Z}\).
- [A7] If \(m.n=0\) then either \(m=0\) or \(n=0\).
As well as the algebraic structure the integers have an ordering, by size, which interacts with the algebra. If \(m\) is less than or equal to \(n\) we write \(m\le n\). The main properties are characterised by the following:
- [A8] Given two integers \(m,n\) either \(m\le n\) or \(n\le m\). In addition, \(m=n\) if and only if \(m\le n\) and \(n\le m\).
- [A9] If \(m,n,p\) are integers with \(m\le n\), then \(m+p\le n+p\), and if \(0\le p\) then \(m.p\le n.p\). If \(p\le 0\) then \(n.p\le m.p\).
- [A10] The well ordering principle - any non-empty subset of non-negative integers has a unique least element.
We accept these axioms as being true without requiring any justification of them. We will however justify almost ALL other results in this course.
It is worth noting that the expression \(a-b\) is meant to be short-hand for \(a+(-b)\).
Note also that if \(m=n\) then by axiom A8, \(m\le n\) and \(n\le m\), and so by axiom A9, \(m+p\le n+p\) and \(n+p\le m+p\). Hence by axiom A8 again, \(m+p=n+p\).
Show that if \(x\) is a non-zero integer, then the sequence \[ x, 2x, 3x, \ldots \] contains no repetition.
Solution. The example is asking us to show that if \(a\) and \(b\) are distinct positive integers then \(ax\ne bx\). We use a proof by contradiction together with some of our axioms.
Suppose then, by way of contradiction, that \(ax=bx\). Then subtracting \(bx\) from both sides we deduce that \(ax-bx = bx - bx\). Now the right hand side of this equation is equal to \(0\) by axiom A3. For the left hand side, we shall see in one of our tutorial sheets, that we can use the axioms to deduce that \(-(bx) = (-b)x\) (this isn’t one of our axioms, but we shall be able to deduce it as a consequence of the axioms). Hence the left hand side becomes \(ax+(-b)x\), which by axiom A6 becomes \((a+(-b))x\), or in other words, \((a-b)x=0\). From axiom A7, we can now deduce that either \(a-b=0\) or \(x=0\). By our original assumption, \(x\ne0\) and so we conclude that \(a-b=0\). We can now add \(b\) to both sides of this equation to deduce that \((a-b)+b = 0+b\), and by using axiom A5 on the left hand side and A2 on the right hand side, we deduce that \(a+(-b+b) = b\). But axiom A4 tells us that \(-b+b=b+(-b) = b-b\) and axiom A3 then tells us that \(b-b=0\). Consequently we deduce that \(a+0=b\) and so \(a = b\) by axiom A2.
This is the contradiction that we are seeking and so we conclude that the terms in the sequence are all distinct.
We shall see a number of other examples of using the axioms to prove basic results in number theory later in the course. For now, we conclude by introducing a final method of proof, that many of you will have seen before.
Proof by Induction
This method is referred to as Proof by Induction and concerns proving statements of the form \[ \forall n\ge 1\ P(n). \] The method of proof uses the Principle of Mathematical Induction, which can be expressed in a familiar form as
The statement \(\forall n\ge1\ P(n)\) is logically equivalent to \[ P(1)\land \left[\forall n\ge 1\ P(n)\implies P(n+1)\right]. \]
So to prove a statement of the form \[ \forall n\ge1\ P(n) \] we prove
- \(P(1)\) is true
- \(\forall n\ge 1\ P(n)\implies P(n+1)\).
The first step is often referred to as the anchoring step, while the second step is referred to as the inductive step. We shall prove this theorem shortly but it is helpful to look at a simple example first.
The principle relies on the fact that if a statement about the positive integers is false for some positive integers, then there is a first one at which it fails to be true, so if we want to prove that a statement is true for all positive integers we just have to show it can’t fail for the first time.
There are two strategies, weak induction (normally just called induction) and strong induction.
Let \(P\) denote some statement about positive integers, and \(P(n)\) denote the statement applied to the number \(n\). So \(P(n)\) might denote the statement \(n< 6\). In this example \(P(1), P(2), P(3), P(4), P(5)\) are all true, whereas \(P(6)\) is false, and, indeed \(P(n)\) is false for any \(n\geq 6\).
On the other hand the statement \(\displaystyle\sum\limits_{i=1}^n 2i = n.(n+1)\) seems to be true for all values of \(n\). How would we prove this?
Clearly \(P(1)\), the statement that \(2.1=1.2\), is true.
Suppose that \(P(n)\) is true. So \(\displaystyle\sum\limits_{i=1}^n 2i = n.(n+1)\). Then \[\sum\limits_{i=1}^{n+1} 2i = 2(n+1) + \sum\limits_{i=1}^n 2i = 2(n+1) + n.(n+1) = (n+1)(n+2)\]
But the equation \(\displaystyle\sum\limits_{i=1}^{n+1} 2i = (n+1)(n+2)\) tells us that \(P(n+1)\) is true! This is a contradiction so there is no first place at which the statement becomes false and it must be true for all values of \(n\).
Here is a formal proof of Theorem 1.17. Don’t try to memorise it, but do try to understand it!
Proof. \[ \begin{array}{rlr} &(\forall n\ge 1) P(n)\text{ is true}\\ \equiv&\lnot[\lnot[(\forall n\ge 1) P(n)\text{ is true}]]\\ \equiv&\lnot[(\exists n\ge 1) \lnot[P(n)\text{ is true}]]\\ \equiv&\lnot[(\exists n\ge1)(P(n)\text{ is false})]\\ \equiv&\lnot[\{n\ge1|P(n)\text{ is false}\}\ne\emptyset]\\ \equiv&\lnot[\{n\ge1|P(n)\text{ is false}\}\text{ contains a smallest value}]&\text{A10}\\ \equiv&\lnot[(P(1)\text{ is false})\lor((\exists n\ge2)[(P(n-1)\text{ is true})\land(P(n)\text{ is false})])]\\ \equiv&\lnot(P(1)\text{ is false})\land\lnot((\exists n\ge2)[(P(n-1)\text{ is true})\land(P(n)\text{ is false})])\\ \equiv&(P(1)\text{ is true})\land((\forall n\ge2)\lnot[(P(n-1)\text{ is true})\land(P(n)\text{ is false})])\\ \equiv&(P(1)\text{ is true})\land((\forall n\ge2)[\lnot(P(n-1)\text{ is true})\lor\lnot(P(n)\text{ is false})])\\ \equiv&(P(1)\text{ is true})\land((\forall n\ge2)[\lnot(P(n-1)\text{ is true})\lor(P(n)\text{ is true})])\\ \equiv&(P(1)\text{ is true})\land((\forall n\ge2)[(P(n-1)\text{ is true})\implies(P(n)\text{ is true})])\\ \end{array} \]
Note that in the final line, we are using the variable \(n-1\) rather than \(n\), but this is just cosmetic.
Notice also that there is nothing special about the value 1. If we wish to prove the statement \(\forall n\ge m\ P(n)\) we do so by proving
- \(P(m)\) is true
- \(\forall n\ge m\ P(n)\implies P(n+1)\).
Show that for all \(n\ge 1\) \[ n!\le n^n \]
Solution. The anchoring step is to prove the statement \[ P(1): 1!\le 1^1 \] This is quite obvious, as both sides are equal to 1.
The inductive step is to prove the statement \[ \forall n\ge 1\ P(n)\implies P(n+1), \] or in other words \[ \forall n\ge 1\ n!\le n^n\implies (n+1)!\le (n+1)^{n+1}. \] The best strategy with this kind of example is to take one side of the inequality in the statement \(P(n+1)\) and replace it with the corresponding expression from the statement \(P(n)\). So \[ \begin{array}{rcl} (n+1)!&=&(n+1)n!\\ &\le&(n+1)n^n\qquad\text{since }P(n)\text{ is assumed true}\\ &<&(n+1)(n+1)^n\\ &=&(n+1)^{n+1}. \end{array} \] Hence the result follows by mathematical induction.
Show that for all \(n\ge1\) \[ 1 + 3 + \ldots + (2n-1) = n^2 \]
Show that for all \(n\ge1\) \[ (1+a)^n \ge 1+na \] where \(a\) is any real number greater than -1.
Strong Induction
Sometime weak induction is not strong enough to prove the results we want. To carry out a weak induction argument one needs to reduce a statement concerning the integer \(n+1\) to the same statement concerning the integer \(n\).
In certain circumstances (like the proof of the fundamental theorem of arithmetic, Theorem 3.3) we will only be able to reduce the truth of \(P(n+1)\) to the truth of \(P(m)\) for some \(m<n+1\), where we don’t know which \(m\) we get.
In these circumstances we use strong induction to show that if \(P(m)\) is true for every positive integer \(m<n+1\) then \(P(n+1)\) is also true.
Let \(f_n\) be the \(n^{th}\) Fibonacci number and let \(\alpha = (1+\sqrt{5})/2\). Show that for \(n\ge3\) \[ f_n > \alpha^{n-2}. \]
Solution. The anchoring step in this case, involves proving the statement for \(n=3\) and \(n=4\). Since \(\alpha <2 = f_3\) and \(\alpha^2 = (3+\sqrt{5})/2 < 3 = f_4\), the result is true for \(n=3\) and \(n=4\).
Suppose then that the result is true for all \(k\le n\) and consider the case \(k = n+1\). It is easy to check that \(\alpha^2 = \alpha + 1\). Hence \[ \alpha^{n-1} = \alpha^2\alpha^{n-3} = (\alpha+1)\alpha^{n-3} = \alpha^{n-2}+\alpha^{n-3}. \] By the inductive hypothesis we have \(\alpha^{n-2}< f_n\) and \(\alpha^{n-3}< f_{n-1}\) and so \[ \alpha^{n-1}<f_n+f_{n-1} = f_{n+1} \] and the result follows by (strong) induction.