BAM Mr. Tarrou in this math lesson
we're going to be taking a look at a
induction proof that deals with
divisibility now a long time ago
actually I made a video I'm gonna post a
link to it in the description where we
were proving a partial sum formula when
we first got introduced to sequences in
series and indeed that's where you start
to look at induction proofs for the
first time you know if you add so many
numbers you know instead of adding so
many numbers like 10 or 100 or 10,000
numbers is there some kind of partial
sum formula that will work to streamline
or shortcut that process and at the time
I only had a deal with those types of
induction proofs but now we're going to
take a look at some divisible
divisibility and we're going to prove by
mathematical induction that 9 to the N
power minus 1 is a multiple of 8 for all
n such that and as a set of the positive
integers this sort of double Z notation
is a symbol for positive integers that
current textbook I'm using whoops or
teaching from uses chalk down okay well
does this even I mean how can we prove
this you know will it work if n is equal
to 1 well we have 9 to the first power
minus 1 is equal to 8 and 8 is certainly
multiple debate we have n is equal to 2
and I'm not going to do like a 1.2 or
1.3 because we have n as a set of the
positive integers so what if at n is
equal to 2 we have 9 squared is 81 and
81 minus 1 is equal to 80
well that's 8 times 10 so that's a
multiple of 8 and then if we have n is
equal to 3 we have 9 cubed minus 1 well
now 9 cubed is 729 and 720 9 minus 1 is
equal to 728 and if you divide 728 by 8
you get an answer of 91 again another
integer so these three values when n is
you know that we get from letting n
equal 1 2 & 3 are clearly multiples of 8
so I just proved it right no I just did
three examples you know but what happens
when n is equal to 4 and then 10 and
then 10,000 and so on and so on we can
just show as many examples as we would
like and then me as a you know math
teacher can just simply say hey you
showed it worked a bunch of times what
about the next n well that's the idea of
what an induction proof does for us
we're going to prove from well we're
going to start with some P of n
statement which we want to prove true
for all values of n where again and
isn't within that element of positive
integers and we're going to then so I'm
going to start with something like let P
of n equal our statement and then go
from go somewhere we're gonna see that
in a second we're then going to prove
that P of 1 is true and your starting
value we say that n is this within this
set of positive integers but our first
initial value doesn't really necessarily
have to be 1 it might be such that we
have some kind of statement like this
but it starts where n is equal to 3 and
then goes on from there 3 4 5 6 and so
on and so on so our initial value is not
always equal to 1 but it is usually
we're then going to assume that P of K
is true where K is a power a particular
value of n is greater than or equal to 1
and kind of think of this as yes we're
going to try and prove that P of n is
true we're going to let P of n represent
some kind of statement involving 9 to
the N power minus 1 and being some kind
of multiple of 8 and we're going to
assume P of K is true and effectively K
is kind of acting as the same variable
as n but we're kind of differentiating
our work within the proof from the
actual statement which we are trying to
prove true you don't want to make it
seem like in your proof that you're
already assuming what you're trying to
prove true is you don't to make that
assumption that it's true before you
even you know start your proof that's
we're going to try and justify as we
finish this and then we're going to use
the assumption that
if P of K is true to then show that P of
K plus 1 is also true and what does this
notation mean here of P of K and P of K
plus 1 basically here you know let's
make sure that some kind of statement
works at least once and then maybe not
the K has to be equal to 2 it can be any
particular value of n but if we just say
for a second you know think about K
possibly equaling 2 then if we assume
some that this statement is true for
some K then can we use that assumption
hey I mean late the work when n was
equal to 1 let's use that assumption to
see if it works when n is equal to 2 or
if K is equal to 2 well can we use some
kind of statement with K involving some
type of number to then show that it's
true for the next positive integer and
if we can get those dominoes to start
falling like I said hey it worked for 1
well then it might work for 2 then it
might work for 3 then it might work for
4 we're not going to do an infinite
number of examples we're going to let
that to lead to 3 lead to 4 lead to 5
with this general statement of K is any
particular value assume that this
statement is working for that particular
value and let it knock down the next
Domino of K plus 1 or if it works for 2
it works for 3 that it works for 4 and
so on and so on the induction proof
allows those dominoes to fall without
you having to you know do an infinite
number of sort of concrete numerical
examples like we have here so that's
what we're going to do we're going to
get this out of the way and do our
induction proof we're going to let we're
gonna get a full piece of chalk is what
we're gonna do we're going to let
P of n represents or be equal to 9 to
the N power minus 1 we're going to let
that equal 8 times a where and again is
within that set of positive integers and
so is a ok we're again taking that that
value of 9 raising it to some positive
integer and getting an answer which is a
multiple of 8 and this the only pot that
it's only possible to have some kind of
positive multiple of a if we're only
letting n be a positive integer and then
we're going to show or consider N equals
1 and prove that P of 1 is true so for
step 1 P of 1 consider that well we have
9 to the first power minus 1 on the left
hand side let's remember that is equal
to 9 minus 1 which is 8 and on the right
hand side you know we basically have you
know that we have an 8 now I'm not going
to write 8a because saying that 8 is
equal to 8 a is saying that 8 is equal
to 8 times any positive integer that
doesn't make any sense but clearly we
know and can see that 8 is a multiple of
8 the left and right hand sides can be
equal as of course I guess as long as a
is equal to 1 so we've proven that P of
1 is true so therefore P of 1
is true so we've shown like really I
just already didn't yet in the yellow
chalk that this statement works when n
is equal to one so instead of letting
then try in two three four five six and
forever and forever we're just going to
say we're going to assume P of K is true
so ie we have nine to the K power minus
one is equal to a a where K is a set of
positive integers all right assuming
that this is true can that allow us to
prove that's
so with induction proofs you come up
with you know you're given a statement
and just to match the notation on my
book I'm saying let piece of P of n
represent that statement we're going to
show that it works for when N equals 1
or whatever our initial value is if it
works if we can show that that's
actually true then maybe it works for
every positive integer so we're going to
assume that P of K is true ie like I'm
not it's kind of just like a statement
or an example of what I'm representing
here I'm not saying that it's true it's
not like you know therefore we have this
we have nine to the K power minus 1 is
equal to 8 a and that a representing
positive integers therefore representing
them an integer multiple positive
integer multiple of a like you saw or
eight like you saw in our three sort of
arithmetic examples now if we want to
prove therefore that the statement is
still going to be true for the next K
the next positive integer then I'm just
gonna replace anywhere that I have a
variable of K replace it with K plus one
but my B here my eight times B I can't
use the same positive integer variable
because well if I'm taking nine and I'm
raising it to the next consecutive
positive integer power of course I'm not
going to get the same multiple of eight
I'm going to get another multiple of
eight so I need to redefine this as with
my proof that still B is within that set
of all positive integers now that's what
I want to prove this isn't the proof
it's basically like my proof is done if
ice you know if I can get some kind of
statement where I can prove that these
two sides match like this is the end of
my proof this is what I wanted to look
like when I'm done so my proof starts
here my proof starts where a tart I take
one of the two sides of this statement
it's usually going to be the left-hand
side but it doesn't need to be you kind
of just start with the side of the
statement that you think will be the
easiest to start from probably that's
going to include some kind of
simplification
until you get it to match the other side
so we're going to start here with our
proof on the left-hand side which is 9
to the k plus 1 power minus 1 now that
is going to be equal to our left-hand
side that is going to be equal to 9
actually my write this over here 9 to
the K times 9 minus 1 power I'm going to
go ahead and separate the yeah like that
I'm gonna go ahead and separate this
base and write the 9 to the k plus 1
power is 9 to the K times 9 to the
firm's because when you multiply like
bases you add the exponents
now what would even make me want to
write this statement what would make me
think hey I want to take that 9 to the k
plus 1 and write it as 9 to the K times
9 to the first how do I make this really
become 9b well to you know we're going
to try and prove remember that P of the
K plus 1 is true assuming this fact that
9 to the K minus 1 is equal to 8 a like
we're assuming we don't really know that
this is true but we're assuming this is
true and if it's true we can put this
information somehow get information from
our assumed statement into our proof and
if we can get the two sides to match if
I can somehow get an 8 B to come out of
this work by using this assumed
information then the dominoes are
starting to fall and we have you know
shown with the mathematical induction
that you know n of any or 9 to the any
positive integer power minus 1 is that
multiple of 8 or you know gives you an
answer that's divisible by 8 so I'm just
simply looking here and trying to figure
out how am I going to get some
information from this statement into my
proof and well I have a 9 to the K power
so I wouldn't necessarily want a 9 to
the k plus 1 power I need that 9 to the
K power to show up now from here you
know proofs just like who were in
precalculus
with your trig proofs you can go down
multiple back paths now I can manipulate
this to a point where I finally see a
nine to the K minus one show up or since
I already have a nine to the K power in
this next step of my proof I can rewrite
this assumption statement and say well
if I'm assuming this to be true well
then basically I have nine to the K is
equal to eight a minus or plus one now
I'm just taking this in am adding both
sides by one now I'm not trying to prove
this statement I've assumed it to be
true when you work with a proof now I
started with just one side of the proof
I'm not really setting up as an equation
that's like this left-hand side is now
equal to I've rewritten that left-hand
side but in a proof you can't move terms
and factors from the left to the right
hand side of an equation within the
middle of a proof but I'm not trying to
prove this is true I'm assuming it
already is true so we have nine to the K
is equal to eight a minus or eight a
plus one okay so we have this is equal
to nine so the K power is coming out and
then its place I'm going to plug in
eight a plus one times 9 minus one okay
now let's clean this up a little bit
we're gonna distribute the nine through
these parentheses get 72 a plus 9 minus
one simplifying this some more we have
72 a plus eight and the phone excuse me
for that and now here it seems like
we're getting farther and farther away
from this goal of writing 8 B but
actually 72 and 8 are both divisible by
8 so we can factor an 8 out and we have
9 a plus 1 we have 8 times something
if we can justify that this something
being multiplied to eight is an integer
well that's what B is
it's another positive integer just
simply not the same positive integer as
a but that still means it's a multiple
well if a is a set within that set of
positive integers then you know a
positive integer multiplied by a
positive integer plus one is going to
give you another positive integer so
therefore we have we have the ability of
replacing nine a plus one with just the
letter B and so we've shown that you
know nine n minus 1 where N is a
positive integer is a multiple of eight
we showed that it worked when n is equal
to one so instead of doing and is equal
to and as a any query for five and so on
we're going okay maybe the statement
just works and based on that assumption
when we go to the next integer our k
plus one integer and say well then this
has to be equal to another positive
integer multiple of eight and using that
assumed fact within our proof we got
that a B pattern so hmm let's see since
P of one was true and P of K plus one
was proven true
assuming P of K was true then by the
principles principle nope I knew I was
gonna spill that principle of
mathematical induction e sub n is true
and that is how you do an induction
proof for divisibility I miss a true hey
go to your homework
you