An induction proof in practice

Hello. Welcome back to steps in practice. And this is the last step in practice, actually, of week one. We are concerned here with an inductive proof. And we are asked in exercise one to prove the following proposition. Depending on n, the sum of the integers from 1 to n equals n times n plus 1 over 2 for every natural n greater or equal than 1. If you remember, we met this formula in the previous step. Naturally, we proved it with the Gauss method. Here, we are asked to prove it by induction. So in a different way. The first inductive step is to prove it for the first value of n. That is, to prove that P of 1 is true.

We already checked it. You remember? But let us do it again. P of 1 states that 1 is equal to 1 times 1 plus 1 over 2. Well, but this is 1 and this is 1, so of course it is true.

Now let us take a particular natural m greater or equal than 1, and assume that the proposition is true at level m. That is, assume that P of m is true. So notice we didn’t prove P of m, we assumed that it is true, like P of 1. We know that it is true. So we assume that P of m is true. This means that we know for sure that the sum of the integers from 1 to m is equal to m times m plus 1 over 2. Just for this particular m. It may be m equal to 100, to 90. Ok? What we need to prove is that P of m plus 1 is true.

So we prove that P of m plus 1 is true. P m plus 1 says that the sum of the integers from 1 to m plus 1, well, must be equal to that formula with n replaced by m plus 1. That is, m plus 1 times m plus 2 over 2. And we have the question mark here, because we do not know if it is true. We want to prove this. Now you see we have an information about the sum of the integers from 1 to m. And we can use it somewhere.

Well, the associativity of the sum allows us to sum the first m plus 1 natural numbers by summing first the first m natural numbers, and then m plus 1. Now, thanks to P of m, we know that this equals m times m plus 1 over 2. So I make use of the fact that the sum of the first m integers equals m times m plus 1 over 2. And then we add m plus 1. Now, if we write this with 2 on the denominator, it becomes m plus 1 times m plus 2 times m plus 1 over 2, which is exactly m plus 1 times m plus 2.

I use here the distributivity of the product over the sum divided by 2. Well, if you compare what we want to prove with what we proved, Well, you understand that we did it. So the conclusion, thanks to the inductive principle, induction principle, well, tells us that the proposition P of n is true for every n greater or equal than 1. And this ends exercise one. And not only exercise one, also the practice steps of week one. So see you next week.