Skip main navigation

An induction proof in practice

Exercise on an induction proof
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.

The following exercises are solved in this step.

We invite you to try to solve them before watching the video.

In any case, you will find below a PDF file with the solutions.

Exercise 1.

Prove by induction that (1+2+cdots +n=dfrac{n(n+1)}2) for every (ninmathbb N, nge 1).

This article is from the free online

Precalculus: the Mathematics of Numbers, Functions and Equations

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education