Some things are just too hard to prove directly, so in this case, we may need to take a more indirect route. One way in which to do this is a proof by contradiction, whereby we assume something, then do some logical deductions which (hopefully) produce some sort of contradiction. Take a look at the following example, prove that there is an infinite number of prime numbers.
Proof:
We will assume that there is a finite number of prime numbers, the set:
![\[P= \{p_1,p_2,p_3...p_n\}\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-6f1a45336833878eec4ccc22eedac9bf_l3.png "Rendered by QuickLaTeX.com")
Now suppose we take all the elements in the above set and multiply them together, then add 
to that product, we will get some number 
.
Since is obviously much much larger than 
, it cannot be a prime number, and because every number can be expressed as the product of prime numbers, is a product of some of the primes in our list 
above. 
Suppose we try to divide by any of the primes in our set , we will always get a remainder of 1, because we made by multiplying all the primes together and adding 1. This means that is not a product of the primes in the set . 
Now since cannot satisfy both A and B above, we have a contradiction. Therefore, since assuming that there is a finite number of primes led to a contradiction, there must be an infinite number of primes.
You can see that this worked by finding a contradiction between two statements (A and B) which came from an assumption that there were a finite number of primes. So just to recap, to do a proof by contradiction, you have to make some assumption, and then show that this assumption leads to a contradiction.
This second part of finding a contradiction can be quite hard and usually takes a lot of work before you can write out the final clear proof. One proof that I am very fond of, and that I believe illustrates this point well, is proving that 
is irrational using infinite series. So just some background before we delve into this proof, many functions can be expressed as infinite series using the Taylor Series Expansion. For our function 
with 
it looks like the following:
![\[\mathrm{e}= 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \frac{1}{5!} ...\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-b6c6cae7326694861a549a84ffd27f53_l3.png "Rendered by QuickLaTeX.com")
We will assume that is rational and hence it can be written as a fraction, 
, where 
and 
are integers and have the highest common multiple .
![\[\frac{a}{b}=1+1+\frac{1}{2!}+\frac{1}{3!}...\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-4bd890e9dd0f54caa1df8ada91778acf_l3.png "Rendered by QuickLaTeX.com")
Now lets multiply both sides by 
and what we get is:
![\[\textcolor{blue}{a(b-1)!}=\textcolor{red}{b!+b!+\frac{b!}{2!}...\frac{b!}{b!}}+\textcolor{green}{\frac{b!}{b+1!}+\frac{b!}{b+2!}...}\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-9dca00acfe18c60134e674362d84767e_l3.png "Rendered by QuickLaTeX.com")
Obviously the red and blue parts are integers, so since the 
, the green section must be an integer. So lets analyse this green bit further. Firstly lets simplify every one of those fractions a bit.
![\[\frac{b!}{b+1!}+\frac{b!}{b+2!}...=\frac{1}{b+1}+\frac{1}{(b+1)(b+2)}+\frac{1}{(b+1)(b+2)(b+3)...}\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-1b17907bfe2821035ba59c2f9c6b4cd3_l3.png "Rendered by QuickLaTeX.com")
Now to get something that we can work with, let’s replace everything on the bottom of those fractions with 
, so that the right hand side becomes:
![\[\frac{1}{b+1}+\frac{1}{(b+1)(b+1)}+\frac{1}{(b+1)(b+1)(b+1)}...\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-cefe4c2306c4c2007376e339858d12d6_l3.png "Rendered by QuickLaTeX.com")
Doing that also changes the equality side, now because we have change everything on the denominator to something smaller, the whole righthand side of the equation has just gotten larger, because you are essentially dividing by smaller numbers. So now our inequality looks something like this:
![\[\frac{b!}{b+1!}+\frac{b!}{b+2!}...\leq\frac{1}{b+1}+\frac{1}{{(b+1)}^2}++\frac{1}{{(b+1)}^3}...\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-30ab77202f3e79e54c787a86b9580eb2_l3.png "Rendered by QuickLaTeX.com")
, doing that gives: ![\[\frac{b!}{b+1!}+\frac{b!}{b+2!}...\leq\frac{1}{b+1}(1+\frac{1}{{(b+1)}}+\frac{1}{{(b+1)}^2}+\frac{1}{{(b+1)}^3}...)\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-7af9d36a6a4927aeaec07eaf8c430566_l3.png "Rendered by QuickLaTeX.com")
Looking at our second bracket, we have the infinite geometric series with 
. Now for those of you haven’t dealt much with the geometric series, the sum of any geometric series can be found by the following formula:
![\[\frac{1}{1-r}\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-19bd4115bd2be113be8a82c353229c83_l3.png "Rendered by QuickLaTeX.com")
Therefore our inequality becomes:
![\[\frac{b!}{b+1!}+\frac{b!}{b+2!}...\leq(\frac{1}{b+1})(\frac{1}{1-\frac{1}{b+1}})\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-3990f6a78c3acd5d33e9bbd34d2603f1_l3.png "Rendered by QuickLaTeX.com")
This simplifies to:
![\[\frac{b!}{b+1!}+\frac{b!}{b+2!}...\leq(\frac{1}{b+1})(\frac{b+1}{b})\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-584e086446b3f1aeee4da14a228b8f92_l3.png "Rendered by QuickLaTeX.com")
![\[\therefore\frac{b!}{b+1!}+\frac{b!}{b+2!}...\leq\frac{1}{b}\]](http://www.anthonysalib.com/wp-content/ql-cache/quicklatex.com-6fd7e864f24977add7305b93f9b89f57_l3.png "Rendered by QuickLaTeX.com")
Since is not an integer, has to be greater than 1. This is because in our fraction , letting 
, will mean it is a whole number. Therefore 
is less than 1, and is therefore not an integer. Since our green section that we have been analysing is less than , it too is not an integer. This leads to a contradiction, because we know that the blue and red parts are integers, and therefore the difference between them must also be an integer, however we just showed that the green part (the difference) isn’t an integer. Therefore our original assumption that is a rational number is false, and therefore we conclude that is an irrational number!
That is one beautiful proof! It shows just how weird these proofs can get, it isn’t always straightforward and you will usually have to do a lot of abstract thinking and try new and different things to figure out what you need to show is a contradiction, and only then can you go back to the start of your proof and work from there!
Recent Comments