00:00

[Music] have you ever wondered how someone proves something is true

for all natural numbers have you ever been curious

how mathematicians prove some of the most beautiful theorems

in this video i discuss a powerful method of proof

called mathematical induction hi i’m dave welcome back to my channel

in this episode i’m going to work through several examples of how to use

mathematical induction i’ll also talk about the well ordering axiom and strong

induction after working through several more examples i then prove

that the well ordering axiom the principle mathematical induction

and strong induction are all equivalent to each other

so this video is for anyone who’s looking to learn how to write a proof

00:01

by mathematical induction [Music] okay let’s get started let’s look at

what the mathematical induction actually is as a sentence and then we’ll do our

first two examples here and see what we’re going to do after

that so mathematical induction here it starts off by saying if p is a subset

of the positive integers so you have to know what positive

integers are so we’re talking about 1 2 3 4 and so on and we’re going to say

if p is a subset so notice the structure of this sentence here is an

if and then so the part that comes after the if

before then this is the hypothesis and then and now this is the conclusion

of this statement here so let’s look at the hypothesis so the hypothesis says

p is a subset of the positive integers with the following properties

so we have a subset p it’s made up of positive integers

00:02

and it has to have these two properties here so if p has both of these two

properties if p has both of these two properties then p

is the subset the whole subset of positive integers

so we start off by taking a subset of positive integers

we check these two conditions and then p has to be the entire set okay so

it’s a way of starting with a s a subset of positive integers

and you’re hoping this subset is actually all positive integers

but to prove that you have to go and check these two properties

once you check these two properties then you can claim p

is the whole set of positive integers so what are these two properties

property number one you check that one is in p so if you

have a subset of positive integers remember positive integers are 1 2 3 4

and so on you could have infinitely many numbers

in your subset but if you don’t have one well it can’t be the entire set of

00:03

positive integers so it has to have one now property number one here is usually

called the base case let’s write that down the base case

property number two is often called the induction step so

we’ll write that down later but property number two is called the induction step

now notice property number two contains an implication which means we have an

hypothesis and a conclusion so this is what makes mathematical induction

interesting it’s because we have an if then

right here inside of an if then and so we have to keep

everything straight when i’m referring to the hypothesis which hypothesis am i

referring to am i referring to this one or am i referring to

all of this so we actually give a name to this hypothesis right here

00:04

and this is called the induction hypothesis so that that right there is

important so basically what this is saying is that

if you take if you take an arbitrary positive integer

and if you know that’s in there and then you prove that k

plus 1 also must be in there then you know that we have the entire set of

positive integers so that’s the statement of mathematical induction now

the state statement by itself um needs needs lots of practice so we’re going to

do lots of examples here’s our first two examples

so we have the summation from 1 to n of i i is our index here i equals 1 to n of

i and we’re going to prove that it’s equal to this formula right here

so a little quick note about summation notation right here i’m not

going to go through it in detail but just a real quick

refresher so the summation from i equals 1 to 100 of i

00:05

so here i’m using n is 100 over here this is just scratch work this isn’t

really part of our example i’m just want to refresh your memory

what summation notation is so this will be one plus summation means add up

so we we start with the one here and we plug in one

we plug in two we plug in three we plug in the last one we go to is a

hundred so the second to last one would be like well the third to last and then

ninety-nine and then the last one where we stop is one hundred

now you might be wondering where we get this formula from well

if we try to add up all these numbers right here the better way to do it than

to just add them up in order that they’re written down here

would be to put them in pairs so i have 101 i have another 101

i have another hundred and one in fact if you think about this you will have

00:06

fifty a hundred and ones and another way to think about that

fifty is a hundred over two so this is kind of where this formula is

coming from here but we’re not just using this 100 over here

this example right here is for all for all positive integers here

in it’s not not only a hundred but it has to work for one

and two and n equals three and n equals four how can we prove that it works

for infinitely many ends not just one particular

end is a hundred so let’s go over here now

and see how this works and this was just scratch work here

so i’ll get rid of that here in a second prove that for all positive integers

that the sum from 1 to n is more quickly found or is equal to

n times n plus one over two so here we go proof

00:07

so the first thing is i’m going to identify what my subset here p is so let p

be the subset of positive integers for which this equation is true

okay so identified my my set set here in fact this scratch work over here

already shows that 100 is in my set p here because we prove the formula is true

for 100 we have 100 we have 100 so we we worked

and we understood how 100 is in p but we don’t need to say that

we just need to identify what the set p is

p is a subset of positive integers those ends that this equation is true

00:08

now at this point we don’t know it’s true for any except for our scratch work

but that’s not in our proof so in our proof we don’t really know

that it’s true for any so the base case is going to remove that

problem we’re going to show there’s at least

one is in here so does this formula work for one

so let’s check if i substitute in here one so let’s check the base case the base

case so i’m going to substitute in here one so what is the summation

from i equals one to one of i so this means we start at one and we end

at one and we just have a one and what about the right hand side here

if n is one so this is two over two times one this is also one

so the base case so the base case holds so we’ve checked that our subset that we

defined p one is in p so we’ve checked the base

00:09

case we’ve checked property number one now we need to check property number two

here to check property number two here i need to move this out of the way

and i’ll get rid of the scratch work also and let’s do that real quick

okay so now let’s do the second step here let’s check the sec if

the second step uh second property holds so to do that i need to make my

hypothesis so let’s assume k is in p and i have no restriction upon k at all

in other words k is arbitrary assume k is p

so what that means is that this formula is holding for k

that’s our hypothesis we’re assuming that this k the formula holds for k

and we want to show the formula holds for k plus 1 that’s what this right here

means we want because p is a subset for which this equation is true

so we want to show that k that the formula holds for k plus 1 is true

00:10

so here’s how we do that so we have the summation from i equals 1 to k plus 1

and if i look at the summation right here i’m going to break it up into two

pieces i’m going to sum from 1 to k and then the last term will be all by itself

so in other words i wrote out the sum here starting at one and two and three

all the way to the left second to last term would be

a k and then the last term would be k plus one

where i left all of those k’s here this is still 1 plus 2 plus 3 plus 4

plus all the way to k and then i still have the plus k

plus 1. now the reason why i wrote this sum into two terms here is because we’re

assuming k’s and p in other words we know information about the k

part here so this part right here i can replace it with k’s and p that

that means that the equation is true for k

00:11

so for this right here if i put a k here it’s the same thing as putting a k over

here so for this part right here i have a k times the k plus 1 over 2

and then i still have a plus and then a k plus 1 here

so i replace this part right here by that right there

i still have plus and then the k plus 1. but this right here is the

induction hypothesis we’re assuming k’s and p

what this right here assumption means is that the formula is true for k

if the formula is true for k that means these are equal to each other

okay so now the next step is to get a common denominator here

and so this will be plus and then i’ll say 2 k plus 1. so i’m getting a common

dominant in other words i’m multiplying by top and bottom by

two but i’ll just multiply the k by two i multiply the whole k

00:12

plus one all over two over two so this will give us the same thing back

again now i’m going to factor out the k plus one here so i have k plus 1

and then i have a k left and then i have a 2 left

and so we’re done we’re done in the following sense we’ve showed the

conclusion holes we’ve started here and we end up here and

in the way in the why and the reason why we end up here is because we show the

formula works now for k plus one so what does the formula look like for k

plus one we have k plus one here and we have a k plus 1 here and we have

a k plus 1 plus 1 and then all over 2. so this equality right here this

equation right here shows that k plus 1 is in p so hence k plus 1 is in p and so

00:13

by mathematical induction hence k plus 1 is in p and so by

mathematical induction p is the entire set of positive integers

in other words we proved this formula right here holds for all positive integers

we said p is the set for which it is true

and we just show p is the entire set not only does it have one in it

but if it has a k in it then the next one also has to be in it

if k is in it then k plus one has to be in it

and there’s no restriction upon k so this holds for all k

any k that’s in it the next one has to also be in it

so p is the entire subset of positive integers here

00:14

so that’s our first example and let’s look at a second example now

okay for our second example we’re going to prove that for all positive integers

in the summation from i equals one to n of i squared so this time we’re adding

up a bunch of squares like one square plus two squared plus three squared plus

all the way to n squared so that’s going to be n times n plus 1 times 2n plus 1

all over 6. so there’s a very nice formula so instead of adding up all

these numbers i can just take n and plug it in and get

a number out very quickly instead of adding up all those numbers

so this is actually a useful formula and so this formula is often used in a

00:15

calculus one class to find to work with riemann sums

but for here we’re just trying to prove this formula is true

and we’re trying to prove it’s true for all positive integers in other words

this formula works for n equals one for n equals two for n equals 3 for n equals

any positive integer so that’s infinitely many

ends how can we prove it we’re going to use mathematical induction to prove this

statement is true so the first thing i want to do is identify my set here p

so here we go proof let p be the subset let p be the subset of positive integers

for which this equation holds so i’m only talking about one equation

00:16

so there’s no ambiguity in terms of this so does this equation hold for any

positive integers i just gave it i just wrote it down

so how do we know it works for any so the first step is to check that it works

for one and then we’ll check the induction step

here so let p be the subset of positive integers for which this equation holds

so let’s check the base case when n equals 1. so for the base case

for the base case so here we go let’s use a 1 up in here so the summation

from i equals 1 to 1 of i squared so 1 to 1 that’s just a 1 squared

which is just a 1. so when n equals 1 the left side says 1 what does the right

side say well the right side i’m putting an equals here

as a hopeful person here i don’t know yet i have to plug in

00:17

n equals one so n equals one and then we have a 2 and n equals 1 we

get a 3 out of here and this is all over 6. so this is 6

over 6. so this is in fact an equal sign here i didn’t know that at first well

actually i’ve solved this problem so many times i knew it but technically

speaking when you’re writing the proof you don’t know if the left-hand side is

equal to the right-hand side you have to check

and everything here checks out for the base case we check this

right so the base case holds or a better way to say that would be so so

one is in p that means the base case holds in other words the formula is true

for for one n equals one now it’s time for the induction step so let’s assume

that k is in p so we have some positive integer here

00:18

we’re not specifying anything about it we’re just assuming that holds

so we we know this formula works for this k here whatever k it is

we’re not assuming that this works for all positive integers that’s what we’re

trying to prove but we are assuming it it does hold for some k

we now have to go prove that that it must hold for k

plus 1. so if i put a k plus 1 here i have to get the formula where i have a

k plus 1 and a k plus 1 and a k plus 1 here so let’s see if we can do that

so then all right so let’s look at what the cape formula is for k plus 1

so 1 i equals 1 to k plus 1 of i squared i’m going to do the same

trick i did before i’m going to write the summation out here

which is going from 1 to k plus 1 i’m going to write it out as 1 plus 2

00:19

plus 3 squared plus 4 squared all the way to the second to the last one which

is k squared so i’m going to write that sum first

from 1 to k so this is the whole sum right here

except one thing short which is the last one which is k plus 1 squared

so in other words i took the sum from one to k plus one and i broke it up into

two terms the sum from one decay and then the very last term of this one

now the re again the reason why is because assuming this is in k

means the formula works for k which means i have a formula for this part

right here not for the whole thing but for this part right here i have a formula

so for this part right here we can come and say this is a k so we have a k here

and then i’ll write this part last so for this part right here we have a k

because we have a k so we have a k and then k plus one

00:20

and then times two k plus one and this is all over six

and then we still have our plus and then k plus 1 squared

so this step right here is very very similar to the last

example that we did when we were summing just an i

all right so very good so in order to combine these together though

and notice we’re not finished here and why is that well i want this formula

with a k plus 1 in it so that means i need a k plus 1 here

a k plus 1 here and a k plus 1 here that’s when i know i’ll be done

but it all has to be over 6. we don’t have that with this right here we need

to manipulate this a little bit more so to manipulate this a little bit more

i’m going to do 6 over 6 here so 6 over 6 will give me a common denominator

so let’s do that real quick 6 over 6. so here we go

so i’m not going to touch this right now so k k plus 1

00:21

over 2 k plus 1 and then plus and i’m doing 6 over 6. so i have 6

times k plus 1 squared if i do 6 over 6 then the whole thing

will be all over 6 now excellent now in the numerator here

we have the k plus ones here and we can factor those out

let’s do that this is k plus one here let’s factor this out

and i’m still getting all over six so factoring out these k plus one so

what do i have left here i have a k times the two k plus one

and when we factor out the k plus 1 here what do we have left we have a 6

and we still have a k plus 1 left all right we’re getting closer let’s see

if we can do this we factor out a k plus one that’s good

00:22

we have a k plus one and six looks like we’re getting close to what

we want remember the left hand side has a k plus one here

that’s where we started with all this is is the left side with a k plus one

we want to try to end up with a k plus 1 in here

we have a k plus 1 and we have a 6. so far we’re looking good

but you see how this is a factor right here so we need to simplify this and

factor it and then if we get this then it will work so here we go k plus 1

and then let’s multiply this out so let’s see here we got a 2k squared

and then we have a plus k and then we have over here as 6k

so all together i get seven k’s and then i have a k uh i already did

that one and then okay so then last we have a plus six

00:23

so now the question is does this factor so let’s see here this will be 2k

and a k we’re looking at factors of 6 so i’m looking at factors of 6 here so

i’m looking at 2 and 3 or 3 and 2 seem to work

so this will give us a 3k and a 4k that gives us 7k

so that looks like it’s good it’s just that it’s

reversed here so we have k plus 1 and then we have a k plus 1 here we have a k

plus 2 and then we put a k plus 1 here and then we do this out we get a 2k plus

- so we got exactly what we wanted here

the left hand side with the k plus 1 and the right hand side here with the k

plus 1. so once we get this is equal to this

now we know it’s true for k plus 1 also we assumed it was true it was for k

00:24

so now we can say let’s go over here so k plus 1 is in p

hence by mathematical induction hence by mathematical induction p

is the set of all positive integers all right so hence by mathematical

induction p is a set of all positive integers all right very well so we did our

second example there so let’s look at a slightly different version of

mathematical induction now okay so here we have two different

versions of mathematical induction some people claim that this is

mathematical induction and some people claim this is mathematical induction

so it really just depends upon your point of view so if you’re going to talk

00:25

about the set of positive integers and that’s your subject of

interest as positive integers then you could take this to be

your math statement of mathematical induction however if your statement even

if you’re interested in the natural numbers and by natural numbers i am

including zero so this one starts at zero one two three four

whereas this one starts at one two three four and so on so

there’s just a slight statement difference here so since we’re starting

at all natural numbers our base case now changes from ones in p

to zeros in p and then the statement number two

is also slightly changed statement number two says

k is an arbitrary positive integer for all positive integers now here we’re

saying for all natural numbers right here but we still have the same implication

so we still have the same induction hypothesis now you identify some subset

p and then the conclusion is that p is the entire set

00:26

in this case p is the entire set of positive integers and in this case

p is the entire set of natural numbers so this is two different versions of

mathematical induction but they’re very very similar so

in this example here we’re going to use the second version here

in fact our next two examples we’re going to use this version here

prove that for all natural numbers and so

we’re saying here natural numbers so i’m going to use this version here

in other words my base case is going to start at 0.

so we have this formula is is for 0 to n and so

natural numbers n so n is going to be 0 here is the base case

and then it’ll be 0 over here for the base case so let’s look at our proof proof

now in these next two examples here i’m not going to refer to the set p

00:27

here explicitly so in the first two examples we did

we explicitly wrote out what the set p was but that’s actually not necessarily

required so the more proofs you do by mathematical induction the more you want

to streamline it so here we’ll not explicitly say

what the set p is but i will verbally say what p

is here so p is going to be the set of natural the subset of natural numbers

for which this equation is true but i’m actually

not going to write that down on my proof i’m going to start off with just the

base case so i’m going to say since the sum from 0 to 0 of two i plus one which

is plugging in zero here so we get out of one

00:28

and on the right side over here when n is one we’re going to get one squared so

since this is true the base case holds the base case holds

so since this is true the base case hold holds

all right so we’ve checked property number one zeros and p

but we didn’t actually refer to a set p so i’ve checked the equation is true for

one for zero and that means zero’s in p where p is the set in which this formula

is true okay so this is a more streamlined

version of the proof here we’ve checked the base case

so now we need an induction hypothesis so now the induction hypothesis is k’s

in p but i’m not going to explicitly refer to the set p here

00:29

so another way of saying k’s in p is i’m going to assume this formula

is true for for some k so i’m going to say assume

for some for some for some natural number k okay so i’m assuming this formula is

valid for some natural number k i’ve not specified anything about k

all right so now we want to show k plus 1 is in p then the sum from

0 to k plus 1 of 2i plus 1. so i need to show k plus 1 is in p in

00:30

other words i need to show now that this formula must also be true for k plus 1.

so i start with the left hand side and my goal is to get the right hand side

but with a k plus 1 here so in other words i needed k plus 1 plus

1 i need a k plus 2 squared so how could i get all of this

as to k plus 2 squared well the idea is to break the sum down

into two terms the first one being the sum from 1 to k

and then the very last one comes in so what will be two times

k plus one all that plus one so we have the sum from one

from zero to k and then we have the last term coming in here

now for this term right here we can we have our induction hypothesis right here

we’re assuming this is equal to k plus 1 squared so i

00:31

have a k plus 1 squared here so k plus 1 squared plus and then we have a 2k

and then we have a two plus one so we have a plus three

so let’s see if we can simplify this here a little bit

because that’s not a k plus two squared or at least we don’t know if it is yet

so here we have a k squared plus two k plus one plus two k plus three

in other words that’s k squared plus four k plus four

and now we can much easier see that that’s k plus two squared

so if we use k plus one on the left side and we work out what it’s equal to

we get a k plus 1 on the right hand side okay

so we assumed k is in p that’s what all this sentence right here means

assume k is in p and we just showed k plus 1 is in p

00:32

so we’ve got this induction step holding now

we checked the first step right here the first sentence we check this part right

here the induction step that’s these two steps these two sentences here

so now we can claim that p is the entire set of natural numbers

so by mathematical induction by mathematical induction the result holds

all right so the result here holds and that’s it and notice here how this

is a little bit more streamlined in the sense that i didn’t explicitly

refer to the underlying subset p some instructors if you’re taking a course

will require you to specify what the set p is

00:33

and some of them will require you to not specify

what the subset p is so here i wanted to do this both ways

here i didn’t explicitly say what the subset here p

was or is so let’s do another example here

and i’ll take this approach again here one more example

in this next example let’s use or let’s look at an

inequality okay in this next example we’re going to prove that for all

natural numbers n 2 to the n is greater than n i hope this makes

sense to you because this is an exponential and it’s going to be greater

than the n okay so in this example we’re also not

going to explicitly say what the underlying subset here is so here we go proof

so the subset p here is going to be the set of all natural numbers for which

this inequality is true and we’re first going to show the zeros in p

in other words we’re going to show that this formula works for zero

00:34

so that’s the base case so let’s check out the base case so since 2 to the 0

is greater than 0 right 2 to the 0 is 1.

so 2 to the 0 is greater than 0 the base case holds

in other words we’ve checked zeros and p that’s that’s called the base case

now we need an induction step so we need to assume this formula is true so

assume 2 to the k is greater than k is greater than k for some natural number k

so 2 to the k is greater than k for some natural number k

then once we make this a hypothesis here’s what we can use it for

00:35

so i’m going to start with my 2 to the k plus 1 here

and that’s 2 to the k times 2 so notice how i start with what i want 2 to the k

but then i write i start with where i need to start with but then i rewrite that

in terms of what i already have so i can try to bring that

into the problem so 2 to the k is greater than k so i can say this is

greater than so that’s greater than k so all of this right here is greater than

2k right so that’s greater than k so in other words i multiply both sides by two

that that preserves it so if you multiply by two multiply by 2. so 2

times 2 to the k is greater than 2k all right and so this is equal to k plus k

00:36

and that is greater than k plus one right k and so these are the same

k is greater than one here so here we have equals perhaps

but we already have strictly greater than right here

so in other words 2 to the k plus 1 is greater than k plus one

so that’s the that’s all we need so we have two to the k is greater than k

by assuming this we now get the k plus one so then this all this holds hence

00:37

the result follows by mathematical induction so we this right here holds for all

natural numbers in by mathematical induction okay in this example here

we’re going to try to prove that n factorial is greater than n

for all n greater than or equal to 3. so in this example our base case here

doesn’t start at 0 or 1 it starts at 3 actually so this is a very interesting

problem here it also involves the factorial so let’s

just briefly mention what the factorial means so i’ll do that down here

so one factorial was equal to one two factorial is one times two which is two

3 factorial is 1 times 2 times 3 which is 6.

00:38

4 factorial is 1 times 2 times 3 times 4 so it’s 4 times the previous one so 24

and so on 5 factorials 1 times 2 times 3 times 4 times 5

and so on so we’re trying to prove that the factorial is greater than

n and so this is you know this factorial right here is growing very quickly so

um it doesn’t work for n equals 1 though

for n equals 1 1 is equal to n factorial is equal to n

so 1 in fact 4 is equal to 1. it doesn’t work for a 2

either but once we get to 3 the 3 factorial is greater than 3

because it’s a 6. and 4 factorial is greater than 4

and so on so as long as we start at 3 and greater then this right here will

always hold and let’s prove that and we’re going to use mathematical induction

00:39

but in this example our base case will start at three so here we go proof

so the base case starts at three so the base case let’s say here since um

i’m going to use three here 3 factorial which we know is 6 is greater than 3

the base case n equals 3 holds so here i just wanted

to like be very clear what my base case the base case n equals three holes

all right so we’re done with property number one it’s just that we’re starting

our base case at a three and now we need to ensure the show the

induction step so i need to make my induction hypothesis

so assume that k factorial is greater than k holds or let’s just say for some

00:40

positive for some positive integer greater than or equal to three for some

positive integer um k greater than 3. so assume this holds for

k factorial is greater than k so we got this k and we especially

think about it except it has to be greater than three we already checked

the case for three so here we’ll say greater than three so now we wanna

uh uh show that k plus one factorial has to be greater than k plus 1. so to

do that we need to start looking at what is k plus 1 factorial so we’ll say then

k plus 1 factorial now remember in all the previous examples we’ve done so far

we start with the next case but then we try to bring in the previous case into

00:41

our problem somehow so i’m going to write k plus 1 factorial as

1 times 2 times 3 all the way to k and then times k

plus 1. so this right here is k factorial times k plus 1. k plus 1 factorial

is the product of the previous ones for example 4 factorial is 3 factorial

times 4. so now we have a k factorial in here and we can try to

use this right here so k factorial is greater than k so this

is greater than k here and this will be k plus 1 here so at the moment we have k

factorial is greater than k times k plus 1. but what do we need we need

k factorial is greater than k plus 1 so we don’t need this k here so we can

see that this is just greater than k plus 1 here

00:42

that has a factor of a k in it so k plus 1 is factorial is greater than k plus 1

so the result follows by mathematical induction

so it’s very crucial that in any proof by mathematical induction

you identify what the base case is you identify what the induction hypothesis is

you prove the implication if then and then you some you can summarize it

all up by by stating hey i’m using mathematical induction here

now the question might come to you that if one can be the base case or zero can

00:43

be the base case or three can be the base case um

do we even need a base case that might that might come into your mind is

it seems like step two is doing all the work so do we even need

a base case so let’s look at an example to see that we always need a base case

okay so in this example we’re going to prove that n plus n plus 1 is equal to 2n

for all natural numbers n so here we go we’re going to

make this proof by mathematical induction however in this example

we’re going to choose to try to do mathematical induction

without doing a base case is that even possible

does mathematical induction need a base case

so let’s go straight for step number two

let’s make our induction hypothesis here so let’s assume that k plus k plus 1

00:44

is equal to 2k for sum for some natural number k so we want to

prove the result now we want to show that it has to hold

for k plus one so i’m going to start on my left hand side with the k

plus one so then k plus one plus so this will be k plus one plus one

will have to be equal to 2 times 2 times k plus 1. so

in order to to do this remember we always start with the left hand side and

we write it with k plus one now we’re going to try to use

our induction hypothesis in this problem somewhere

so here we have a k and here we have a k plus one so i can write these two here

uh this k and plus and this k plus one here so i’ll just this is all

00:45

addition here so i’ll just rearrange the terms and say this is a k

and then let’s put these two next and then let’s see here what do we have

left we have a one and we have a one so that’s a two now

that’s just rearranging i still have everything here all i did was combine

these ones into a two but using my induction hypothesis

i can rewrite this right here as a 2k so this would be 2k plus 2 and in fact

you can see that’s 2 times k plus 1. so what we’ve done is we started on the

left hand side with the k plus 1 here plus and the k plus 1 here

plus 1 and we get the right hand side with the 2k

2 times k plus 1. so we assume it’s true for some k

then we get all of this work here then and so now we can say

00:46

by mathematical induction the result follows by mathematical induction

however this is incorrect though because mathematical induction requires both

steps and we only went for number two we showed number two works

we never showed base case so this is actually all false

and in fact if you think about it this isn’t true for any n

there is no base case there is nowhere to start

this does not work for n equals one this does not work for n equals two

you can keep trying all day and night but you’ll never find an n where this

works there is no base case so if you forget the base case you could

mislead yourself into thinking something is true

when it is not it is obvious that this one is not true

00:47

right if you put in n equals 1 you’re not going to get a 2

out over there so i mean this is never true

this is 2n plus 1 is never equal to 2n that’s the same thing as saying an odd

is equal to an even and that never works i mean

so the point is is that this is a incomplete proof and you cannot finish

the proof and this is never equal to each other so the point of this

example right here was to demonstrate to you

that base case is always required in any mathematical induction

whether you start the base case at one or you start the base case at zero

or in our previous example we started the base case at three

and all those examples were great but you have to have a base case

this is what happens when you don’t have a base case so just just remember to

always have a base case okay so let’s look at strong induction now

00:48

so strong induction is very much like conduction it just has one change so

again we’re going to start with p is a subset and in this case we’re going to

look at the natural numbers instead of the positive integers so p is

a subset of the natural numbers so 0 1 2 3 and we check these two properties and

if these two properties holds then p is the entire set of natural numbers

so that’s just like a mathematical induction the first step here

the first property to check zeros and p right

so natural numbers start at zero so we have the first natural number

so that’s just like mathematical induction now the induction step here

step number two is different we still have the same

statement here for all natural numbers k and here’s the main difference right

here here is the induction hypothesis and instead of just assuming k is in p

00:49

now we’re going to assume 0 1 in fact we’re going to assume all of the first

all the first of them are in p now we already checked the zeros in p so

we don’t need this part right here some people have it some people may not

have it but we assume that one through k is in p

and then we have to get the next ones in b so that’s the

idea there is that you you have a a point where

you assume all the previous ones are in p and then you show and use that as your

hypothesis which is a stronger hypothesis

and then you show that the next one has to also be in p

so that’s strong induction there and we’re going to illustrate that with an

example right now and the example that we’re going to work

on is something called lucas numbers so let’s look

at what lucas numbers are and our goal will be to prove a

result about the lucas numbers and we’ll prove that result

00:50

using strong induction so what are the lucas numbers

so i denote the lucas numbers with a capital l

so capital l sub n is the nth lucas number

for example the first lucas number l1 is just

one the second lucas number is three and then how do you generate all the

rest of them so we got the first two and then you generate the next lucas

number one two and three so you use this formula right

here to generate the third one the fourth one the fifth one

after we’ve already started with the first two here so you cannot change the

first two it’s one and three and now to get the third

lucas number you use the previous two so this is else of n this is the one

that comes right before else of n and this is the one that comes

right before that one so these are the previous two so

00:51

else of three would be one plus three it would be it would be three plus one

so that would be four so let’s look at a couple of them

so l sub three here is the sum of the previous two

three plus one is four what about l sub four

it’s the sum of the previous two so we just got a four from the last one

and the one that came before that was a three so this is seven

how about let’s do two more else of five

some of the previous two seven plus four so the fifth lucas number is eleven

the sixth one what is the sixth lucas number

look at the previous two what’s eleven plus seven

so eighteen so we can keep going and those are the lucas numbers there

so if you fact look at the lucas numbers 1 3 4

00:52

7 11 18 they’re growing pretty quickly so the result that we’re gonna or the

example we’re gonna work on right now is going to say something about how fast

they grow and we’ll prove this statement using strong induction

all right so here’s what the example is okay so here’s what our example says

prove that for all positive integers in else of n is less than 7 4

to the power n so this gives a bound on the growth

of else of n and this bound is given in terms of an exponential

so this isn’t an extremely powerful result

because we’re only bounding the growth by an exponential

but it is a first start in trying to understand this lucas numbers

so let’s prove this result right here using strong induction

and we’ll see how the proof is just a little bit different because we have a

different hypothesis but let’s also see how we can take advantage of that

00:53

so here we go proof okay so what’s my base case going to be um so

the base case this is positive integer so my base case is going to be n equals

- all right so for n equals 1 let’s see here so since l sub one

which is one and um i’m going to put here less than seven

fourths to the one all right so that’s obviously true so this is um

you know four can go into there one plus some remainder so this is

so so the base case holds all right so the base case holds assume the inequality

00:54

holds four one two three all the way to k

and we don’t really need to say one here we already showed it works for one

it doesn’t harm anything assume the inequality holds for the first k of them

now we’re going to show that it has to hold if you have a k plus one here

we’ll have this inequality with the k plus one here also

so let’s do that so l of k plus one remember this is the sum of the previous two

so this will be l of k plus l of k minus 1. so f of k plus 1 is the sum of the

previous two now we can use the induction hypothesis here so to

assume the inequality holds that means for k this inequality holds

00:55

and the previous one that means the inequality holds so i can

replace this right here with 7 4 to the k

and that can replace this one right here

because k minus one is somewhere in here and so we’re when we’re assuming the

inequality also holds for k minus one so seven fourths to the k minus one

all right so that’s not the um what we want though we want 7

4 to the k plus 1 and we don’t have that so we need to manipulate this a little

bit so what i’m going to do is i’m going to factor

7 4 to the k minus 1 out that’s the lower power here

so i’ll have 7 4 to the k minus 1. let’s factor that out so here we still

have 1 7 4 left and here we’ve took the whole thing

out so we’ll just have plus one and this is 7 4 to the k minus 1

00:56

and then this will be 11 fourths okay so this inequality right here is

strict because this was strict and this was strict but

all the rest of these are equals but i don’t want a seven force here i want a

seven fourths to get to the plus one what do we need we need

some squares on on these and we need a seven fourths

so can we replace this by seven fourths k minus one

okay minus one instead of eleven fourths i want here um 49 over 16.

can we replace 11 4 and be strictly less than 49 over 16.

00:57

and the answer is yes this one is under 3 this one is over 3.

so strict inequality will hold here and now once we get this we have 7 4

to the k minus 1 and this is 7 4 squared so this will be

7 4 to the you know adding the exponents k plus 1 here so the k

plus 1 lucas number is less than k plus 7 4 to the k plus 1. so we just

showed the k plus 1 case this right here is less

than if we check everything it’s less than

equals equals equals less than again so this is less than this

and that’s the k plus 1 case and notice how we used

not just the induction hypothesis just assuming it’s true for k

right here that would just be the regular induction

but we also needed another one right here and so then we needed

a stronger induction hypothesis here so i use the induction

00:58

hypothesis here and i use the induction hypothesis here

so we have proved the k plus 1 case so we proved that right there and so now

we can claim so by mathematical induction or by strong induction

strong induction the result holds all right so there’s an example of using

strong induction and a quick introduction to lucas numbers

now in the next video i’m going to cover the fibonacci numbers it’s going to be

the whole video it’s going to be the whole lecture

and we’ll see lots more of examples of using

uh induction and but before we do the fibonacci um lecture let’s look at

00:59

if you have done enough induction that you’re that you’re prepared to look at

this make sure and practice some mathematical induction exercises

before you look at the rest of this video here because

what we’re going to do now is some proofs concerning strong induction and

mathematical induction and we’re going to see how they’re

related to each other so it’s very important that you actually work on some

exercises doing strong induction doing mathematical induction doing those things

before we look at these proofs these proofs are very enlightening though

so let’s let’s look at these okay let’s look at the following

theorem the following theorem says the following statements are

equivalent to each other so the first statement here is

the well ordering axiom which i label as a w

right so it’s every non-empty set of positive integers has the least element

01:00

now the interesting thing about this theorem is that

the statement of mathematical induction which i denote by

n and the statement of strong induction which i denote by s as you can see

these statements are much more complex than the

first statement here the first statement is very easy to say

and it’s very easy to believe um just intuitively so in every non-empty

set of positive integers so if you take any and it has to be non-empty

and you’re looking at positive integers then using the

usual ordering it has to have a least element so that’s a very nice beautiful

statement and then of course we have mathematical

induction and we have strong induction so those statements are written in such

a way as to use them to solve problems you check this two properties

and then you got the whole set here so we have a difference between

01:01

induction hypothesis here so let’s see that these are all

equivalent to each other and the way i’m going to do this is um

i’m going to show that w implies i i implies s

and then s implies w and so then we’ll have all of them

equivalent to each other so let’s start the proof

this part of the proof right here will be w implies i

all right so we’re assuming w is true and we’re assuming p is a subset of

positive integers and we’re going to assume both of those two properties hold

and then our conclusion will be p is the entire set of positive integers

that’s our goal right there is to get that so i’m going to start off by

assuming p is a subset of positive integers so let p be a subset

01:02

of positive integers such that 1 and 2 hold so one’s in p

and two this property right here holds for all positive integers k if k is in p

that implies k plus 1 is in p okay so i’m assuming we have a set

subset of positive integers with these two properties ones in p and

if you take any positive integer this implication has to hold so this is

positive integer here okay now what we’re going to do is we’re going to assume

p is not the entire set of positive integers

01:03

and we’re going to get a contradiction so assume for a contradiction

that p is not equal to i’m going to denote the set of positive integers

by an n plus right so i’ll just put i’ll just say that to you verbally

n plus here is the natural numbers here but with zero out so this is just the

positive integers here in other words this is just 1 2 3 4 5 6 7 8

is just a set of positive integers so i’m assuming

that p is not the entire set of positive integers so our goal now is to get a

contradiction now to help us with this i’ll draw a

quick little diagram this just kind of helps us understand it

so you know we’re assuming p is not that

01:04

set there so let’s look at that set here so let’s say here we have the set here

of all positive integers this is the box of all positive integers

and p is not equal to it so let’s say p is right here p p has

these two properties one’s in p so i’ll put one right there

and it also has this property if anything’s in there

then the next one has to be in there also so we know two’s in there we know

threes in there and we kind of believe that p is the

whole thing but at this point we don’t know it

because we don’t know that mathematical induction is true is holding yet

so assume for contradiction that p is not the whole thing

and what that means is there’s some element out here

there’s some elements out here and we don’t know what they are

but now here’s where we’re going to use w here so this is a non-empty set it’s

non-empty and it’s made up of positive integers so this set

01:05

right here let’s call this set here s s has to have a least element so by w

so by w the set s which is just the whole thing take away the p

so i’m just defining the set as here is the whole thing

so the set of positive integers take away p

so they’re not equal to each other so s is non-empty so by w the set here s

has a least element and let’s call it s so here’s a little s here little s

is in capital s all right so here’s what we got going on we got the positive

integers here where we got one is in p we’re but we’re assuming that p

is not all of them and we’re trying to get a contradiction because we want p

01:06

to be all of them so if it’s not if p is not all of them

so we have some set out here s that has to have the least elements

okay now let’s consider the positive integer s minus 1. now why is s minus 1 a

positive integer well one’s in here so we know s is not 1. so s is a

the least element is in s so it has to be a positive integer

right so s is a positive integer here um and s is not one

so where is s minus one is s minus 1 in p or is s minus 1 and s

01:07

so notice s minus 1 is not in s because s is the least element

in s s is already the smallest so s minus 1 has to be in p

hence s minus 1 is in p now we’ve used this part of our uh

we’ve used this part in our proof so far that s is not one

but we haven’t used this part right here if you take

anything in p the very next one also has to be in p

so by 2 by this statement here 2 we see that s minus 1 is in here

right here so the next one has to also be in here so s

has to also be in here so s is in p all right so this contradiction right s

01:08

cannot be in p and not p this contradiction shows that

p must be the entire set of positive integers so if you assume that p is not the

entire set of positive integers i get i can get a least element out of here

and that least element will allow us to talk about

the element that came right before it and the element that came right before it

it has to be a positive integer because one’s over here

so the the s minus one here has to be in here

s is the least so it has to be in here which means the s

has to be in here we get a contradiction okay so that’s the idea behind uh the

what ordering axiom implies mathematical induction here

we use this uh hypothesis here we use one and two we assume p is a set

of positive integers we tried to assume the opposite we found a contradiction

so p has to be equal to the entire set of positive integers

01:09

all right so now let’s look at mathematical induction implies

strong induction okay so now let’s look at the part of the theorem

where i implies s mathematical induction implies that strong induction in other

words if mathematical induction is true then strong induction has to also be

true so let’s prove that so proof i implies s

okay so in this proof here now if you notice here

both of them are stated in terms of a subset p

so if i start trying to write a proof here with

uh two sets here and p in it it could get confusing

so what i’m going to do is i’m going to change the set here in s and let it read

01:10

with a p prime so if p prime is a subset of positive integers with the property

one is in p prime um and for all positive integers k

if one through k is in p prime that implies that k plus one is in p

prime then p prime is the set of positive integers

okay so re-labeling the set is calling it p prime it’s still the same strong

induction statement i’m just using a different letter or in this case

two symbols so this way when i’m making my proof right here i

can distinguish between the set here p and p prime here okay so

in order to show that strong induction holds we need to start off with this

induction uh we need to start off with this hypothesis here

and then we need to get p is the entire set of positive integers

so right now i’m just going to take an arbitrary set here so let p prime

01:11

be a subset be a subset of the positive integers with the properties

that one is in p prime and the second property for any for any integer k

that 1 through k is in p this implies that k plus 1 is in p these

are primes here okay so i’m taking an arbitrary p

prime p prime is any subset that has these two properties here

so i’m not putting any restriction upon p prime [Music]

except it has to have those two properties one and two

so the fact that i named it a p prime instead of a p

01:12

isn’t going to lose anything so we have p prime just any subset of positive

integers that has those two properties now we’re trying to

show induction implies strong induction so i need to use induction on this proof

to prove this statement is true now to use induction we need to define a subset

of positive integers so i’m going to define the subset of positive integers now

and i’m going to show it has these two properties and then i’ll be able to

then i’ll be able to say oh that’s the set of positive integers

so here we go let p be the subset of positive integers for which

1 2 all the way to k is in p prime is true

01:13

so p is the subset of positive integers for which 1 through k is in p is true

so let’s notice if these two things hold right here for p is one in p

well for for one to be in p we need to know that

one through one is in p prime but we know 1 is in p

prime so we know 1 is in p so notice 1 is in p because

1 is in p prime all right we know one is in p prime so one is in p also

okay so now let’s see um let’s make our induction hypothesis here

assume k is in p so what does it mean to be in p it means

1 through k 1 through k is in p prime so 1 2 all the way to k is in p prime

01:14

is true now remember we’re assuming p prime has

both of these properties not just ones in p

but if all of these are in p prime then that must imply that k plus 1 is in

prime so hence or let’s just say by 2 k k plus 1 is in p prime

so what do we have thus one two all the way to k is in p but so is k plus one

these are all in p prime so thus these are in p prime which means

for all of these to be in p prime that means that k plus 1 is in p

because remember to be in p means 1 through all of these

01:15

are in p prime so that means that k plus 1 is in p hence

p by mathematical induction is the entire set of positive integers

is the set of positive integers all right good now we know we know that

p is the set of positive integers and is the entire set of positive integers

so if you look at what p is that means that any

any natural number that you can pick all of those will be in p

prime right so by definition of what p is p prime also has to be the entire set

01:16

so by definition of p we see that p prime is also the entire set

of positive integers we don’t need the word entire here

it’s a set of positive integers okay so that’s how i implies s goes

and now for the last part of the proof okay in this last part of the proof

we’re going to show that strong induction implies the well ordering axiom so

this is strong induction where we have the strong induction hypothesis here

and we’re going to show that if strong induction holds

that every subset non-empty a positive integers has to have the least element

all right so let’s see that proof proof so s implies uh w

01:17

s implies w all right so let’s suppose that we

don’t have the every here what if we have a non-empty set of positive

integers and it doesn’t have a least element so let’s suppose that let’s assume

that t is a non-empty set non-empty set of positive integers

that has no least element i cannot find the least element in that set

so t is a subset of positive integers so let’s think about this here let’s get

a little diagram here to see if that can help us so here’s the

set of positive integers here 1 2 3 4 and so on and we’re assuming

01:18

that we have a non-empty set of positive integers that has no least element so

it’s not empty so let’s see here’s t right here here’s the set t now this set t

here is non-empty set of positive integer and t has

no least element now we know t cannot be the whole thing

because this one right here does have a least element the positive integers does

have at least elements one one is the least element so t is this

non-empty set here and it has no least element

now in order to use strong induction to to in our proof here

we need to define a subset of the positive integers

and show that it has these two properties here so let’s do that let p be the set

01:19

the set of positive integers for which n is not in t so p is set out here

so let p be the set of positive integers that are not in t

so what do we know about p what can we say about p notice one is in p because

t has no least elements one is the least element

so one has to be in here so because one is the least positive integer

so 1 is in here now to use strong induction i make my

01:20

strong induction hypothesis assume that all of these here

are in p now we need to show that the k plus one must be in p okay so hence

one through k are not in t so you know just by the definition of what p

is so what about k plus 1 is k plus 1 and p or is k plus 1 and t

so if k plus 1 is in t then k plus 1 is the least element of t which

01:21

thus k plus 1 is not in t right because t has no least element so

k plus 1 is not in t so that k plus 1 is in p

so we assumed all these are in p and we just showed that

k plus 1 has to be in p now so by strong induction p is the entire set of

so by in strong induction by s p is the entire set of positive integers

hence t cannot exist so therefore t cannot exist so w must hold

so every non-empty set if you think you have one that doesn’t have a least

element you’re wrong every non-empty set of positive integers

has to have the least element and so now that we know that strong

01:22

induction implies the well ordering axiom now we know they’re all equivalent to

each other thanks for watching if you like this video please press this button

and subscribe to my channel now i want to turn it over to you

math can be difficult because it requires time and energy to become

skills i want you to tell everyone what you do to succeed in your studies

either way let us know what you think in the comments