Skip main navigation

New offer! Get 30% off your first 2 months of Unlimited Monthly. Start your subscription for just £29.99 £19.99. New subscribers only. T&Cs apply

Find out more

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

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now