Proving things: a mathematician’s favourite hobby
What would you do if your teacher or a friend were to ask you to add together all the numbers from 1 to 100? Would you start with 1+2=3, adding 3 makes 6, adding 4 makes 10, adding 5 is 15, and suddenly realise how likely it is that you will make a mistake in your calculations on your way to 100? Also, how long do you think it would take you? Even with a calculator at hand, the task seems extremely cumbersome: you might forget to add a number, add one twice by mistake but whatever the case, it will certainly take you a fair amount of time to get to the final answer.
When Johann Carl Friedrich Gauss was faced with this task by his primary school teacher, it took the young student merely seconds to recall the answer, without the use of a calculator. So what did Gauss know that we don’t yet know about?
Let’s think about it again. What would happen if we, instead of summing up the numbers from left to right, added up the numbers alternately from both sides?
Looking at the image above reveals that 1 + 100 equals 101, 2 + 99 equals 101, 3 + 98 equals 101, 4 + 97 equals 101, and so on until we reach 50 + 51 = 101. So, if we do this for all fifty pairs from 1 to 100, then the sum of these numbers equals 50 multiplied by 101. This is a much easier task to solve and calculating this mentally, or using your calculator, you’ll see that all the numbers from 1 to 100 add up to 5,050.
Now we all know that mathematicians like their formulas, so let’s try to find a formula with which we can express the above example. Say the number 100 is now any natural number, n. The final step in the above example was to multiply 50 (which is 100/2) by 101 (which is 100+1). Replacing 100 with any number n, we get to the formula below.
But how can we be sure that this formula is indeed correct for any natural number? it is certainly not enough to test this using just a handful of examples. In maths, especially once you reach university level, we always need to prove that things are true. It’s a very rewarding way to give grounding to your assumptions and reassures both you and everyone else that what you suspected is indeed the truth.
One very common and powerful way to prove statements about natural numbers is using proof by induction. You may see this method as early as during your A-level preparations, and you will certainly learn more about it in your first term at university, whether it be in an introduction to mathematics, or your Calculus 1 course.
When we prove a statement about the natural numbers using proof by induction, we start off by testing it for an example of the statement (just as we did above). Usually, and you will see why in a moment, we start with the smallest natural number, which is 1. In our example, this means we will test whether all natural numbers up until 1 add up to the result of the right hand side of our formula, which in this case is 1*(1+1)/2 = 1. So in fact, the formula holds for n=1. In the language of the proof of induction, we have just proven that the base case holds for this statement.
Now the question is how can we extend the base case to ALL natural numbers? Going through each one of them would certainly not be efficient, and we would never reach the end.
The way proof by induction works is that we now prove that whenever the statement holds for a natural number, n (yes, that’s right, you should be able to pick ANY natural number), the statement also holds for n+1. Digest this for a moment: basically, what this induction step is saying is that if we know the statement holds for a number (this number could be 1 or 100 or 765 or any other natural number), then it follows that this statement is also true for 2, 101, 766 and so on. Now watch out: as we have proved the statement for n=1, this would mean that if we can prove the induction step, the statement would also be true for n=2. Applying the induction step again, the statement would thus also be true for 3, which follows after 2, and for 4, and for 5, and so on! The beauty of proof by induction is that we create a tool that helps us prove a statement for every natural number.
So let’s prove the induction step for our example. The maths can be seen below, and I will now guide you through the steps. Firstly, we assume that the formula is true for some natural number n (note that this is different from assuming it is valid for all natural numbers). Now we would like to show that the formula also holds if we replace n with n+1. We start at the left-hand side of the equation. For those of you who are familiar with sums, you know that we can write the sum until n+1 as the sum until n plus the last term of the sum added individually. Now you see that the sum formula is the same as what we assumed to equal n(n+1)/2, so by assumption, we can replace this term. Everything from here is merely basic reorganisation of mathematical terms, including fractions. And as you can see, in the end we reach the right hand side of the equation!
You can basically choose any similar addition task to practice proof by induction, they can be more complex than this one. Here is one to get you started:
Try and find a formula which calculates the sum of all cubes up to a certain number, e.g. the sum of all cubes up to the cube of the number 3 is 1+8+27, which is 36, which reminds us of the square of 6, which is 1+2+3.
Dig a little deeper, look at more examples, and you will soon be able to use proof by induction to prove the formula you have found. Good luck!