# Mathematical Induction

## Lecture description

Students will be able to construct proofs using mathematical induction.

## Learn more from the full course

### Discrete Mathematics: Open Doors to Great Careers

Learn the core topics of Discrete Math to open doors to Computer Science, Data Science, Actuarial Science, and more!

04:36:40 of on-demand video • Updated January 2018

Refresh your math knowledge.

Gain a firm foundation in Discrete Mathematics for furthering your career.

Learn one of the mathematical subjects crucial for Computer Science.

Learn one of the mathematical subjects needed for Data Science.

So far we've seen many methods of proof in this lecture we're going to continue our discussion of methods of proof. There is a method of proof which allows us to show that a certain property holds for all integers greater than or equal to a given integer that is there is a method of power which allows us to show for all n p then where the domain of then is the set of all integers and greater than or equal to A. Ok this method is called mathematical induction. For example suppose we added the first few positive odd integers so beginning with 1 and next we add the first two positive odd integers. We get four k. Now add the first three positive odd integers and we get nine k. Now add the first four we get 16 and so on. Now note that the sum of the first positive or integer is one square. And the sum of the first two positive integers is two square the sum of the first three positive integers is three squared and does some of the first four positive integers is four squared etc.. So we can guess that the sum of the first n positive odd integers is and squared. In other words we have 1 plus three plus five plus dot dot dot plus two and minus one that's d and positive odd integer. If we add them all up and square. This is what we guess. And we want to prove that this equation is true for all positive integers and that is we want to prove that for all integers and greater than or equal to 1 when we add up all the positive integers. The first the first and positive integers we get and square. And we want to show this for each and greater than or equal to 1. OK. Now letting people then be the property 1 plus three plus five plus dot dot dot plus two and minus one equals and squared. We want to show that for all. And then where the domain of an is the set of all integers greater than or equal to 1 OK first we'll show that one is true this step is called the basis that k then we'll show for all integers k greater than or equal to 1 of K entails PMK plus 1. This step is called the inductive step OK. If we can show the basic step and the inductive step then we're done. OK. Let me explain why. By the basis that we would have that P of 1 is true. And by the inductive step P of one anthills to OK so p of two is sure. And by the inductive step again. P of 2 entails 3. OK. And since p of 2 is true we get 3 OK. And so on. It's like a domino where P of 1 2 3 etc. are all lined up. And because of one is true. OK one makes pure to true which makes it three true. And so on forever ok. Now let's begin the proof. Have one says that one equals to one square K the sum of the first positive odd integer is just one. OK. And that's equal to one square. Which is true. So the basic step is done now for the inductive step. We need to show for all integers k gritted and or go to one p of K entails K plus one OK. So to show this statement we'll use the method of direct proof. So assume Piercy is true. For some integer k good and good to one OK. This is called the inductive hypothesis. OK. Now show that P. Plus 1 is true. OK. PEF case States one plus three plus five plus dot dot dot plus two minus one is k square P of K plus one state's the same thing except instead of k we plug in K plus one OK. So assuming that this is true P of k we want to show that K plus 1 is true. So that's this equation here. OK so let's start with the left hand side of this equation. Here I just distributed the two and simplified. Now here the odd number that comes right before this last term is going to be to K minus 1 and K so I just wrote it here. Now look at this part one plus three plus plus dot plus two k minus 1. That's this year. And we know that's equal to K squared. This is by the inductive hypothesis. OK so now here we get K square plus two K plus 1 and that's equal to K plus 1 square. OK. And that's the right hand side of this equation. So we do get that. The left hand side here is equal to K plus 1 squared K and that's what we want it to show. So the inductive step is done case since we showed the basis that and the inductive step we're done. K. that's that's the whole process of mathematical induction. OK once we show the basic step and inductive step then we've showed the original statement.