Introduction to Mathematical Induction (Made Easy With Lots of Examples)

Video Series: Mathematical Induction (The Complete Step-By-Step Guide)

(D4M) — Here is the video transcript for this video.

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

  1. 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

  1. 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

About The Author
Dave White Background Blue Shirt Squiggles Smile

David A. Smith (Dave)

Mathematics Educator

David A. Smith is the CEO and founder of Dave4Math. His background is in mathematics (B.S. & M.S. in Mathematics), computer science, and undergraduate teaching (15+ years). With extensive experience in higher education and a passion for learning, his professional and academic careers revolve around advancing knowledge for himself and others. His work helps others learn about subjects that can help them in their personal and professional lives.

Let's do some math together, today!

Contact us today.

Account

Affiliates

About Us

Blog

© 2022 DAVE4MATH.com

Privacy Policy | Terms of Service