In this video, we're going to talk about
a proof by mathematical induction
and we're going to critique it.
We're going to try to identify some of the mistakes that are made in this proof.
This proof at some point was a midterm question
and most of these mistakes are ones that I found on
papers from students.
So here's our problem: we're going to use
mathematical induction to prove
that the sum from i equals 1 to n of
i over 3 to the power of i,
is equal to 3/4 minus
2n plus 3 all divided by 4 times 3 to the power of n
for all natural numbers n.
If you haven't done so I would suggest pausing the video and actually trying to see how many of
the errors that you can find in this proof.
Hopefully you're done and I'll now discuss them.
So first, we start off with the proof. "We prove
P n is true for all natural numbers n by induction". Well
one thing that we haven't done yet is we haven't identified
what P n is yet.
You should...
you should state what the P n that you're trying to prove is.
I know that here it might seem very clear but
even still, for proper writing technique, you should
tell the reader what P n is. You shouldn't introduce variables
without letting the reader know what they are.
So even straight out the gate we're off to a bad start.
"The base case when i equals 1" well that's not true, right?
I mean the base case really is when n is equal to 1.
i is just the indexing variable that has nothing to do with the
statement that we're trying to prove.
I could have called i something else and
nothing would have really changed
as long as I made sure that the other instances of i matched it.
So that's a problem. So this needs to be an n instead of an i.
Now in line 1 - we're already up to 2 mistakes and we're only on line 2…
line 1, what do we have? Well we have the sum from i equals 1 to 1
of i over 3 to the i, that's okay.
But then now we say that is equal to 3/4 minus 2, times 1, plus 3 over 4, times 3
but this is what we wanted to prove. This equal sign right here
is the statement when n equals 1 is plugged in.
So this equal sign isn't really what we want.
We want to show that this thing, after we do a whole bunch of work
and get it down to 1/3, is actually equal to the sum.
So this equal sign is actually a mistake. Right?
We should just start with this side get down to 1/3
and then claim that 1/3 is equal to this, which is true.
So another mistake there.
The induction hypothesis, there are
several mistakes here so let's talk about this.
"Assume P k is true
for all natural numbers between...
from 1 less than or equal to i is less than or equal to k,
k greater than or equal to 2. Okay...
lots of mistakes. For one,
i is the indexing variable right, so we
definitely don't want to say this.
Okay? This 1 is less than or equal to i is less than or equal to k. This doesn't make any sense.
i is the indexing variable of my summation.
It has nothing to do with the induction hypothesis.
The next thing: the person wrote,
"for all natural numbers". Well
you don't want to assume that P k is true for all natural numbers,
that doesn't make any sense, right? You're trying to prove that
P n is true for all natural numbers
so assuming that P k is true for all natural numbers k
means that you're assuming what you want to prove is true.
What you really want to do is take one instance. So for some value
of k, you want to assume that P k is true
and because that value is arbitrary, that's where
the induction sort of makes sense.
You take an arbitrary value to show that P k implies P k plus 1
and because that k was arbitrary, you can prove that
P n must always be true by the Principle of Mathematical Induction.
Remember that's the idea, right?
Third mistake is we have k is greater than or equal to 2, so even if you had written
for some natural number
k with k greater than or equal to 2, we're still wrong.
Why is that now?
The reason why were wrong now is because the k,
the base case for the induction…
the smallest case in the induction hypothesis
should overlap with the largest base case in your base cases.
This is true for strong induction, this is true for just regular inductions as well.
So again, what's happening here? Well you have
k is greater than or equal to 2
and what this is sort of saying is that if you ended up proving that this was true,
you would have proved that P 2 implies P 3 and
P 3 implies P 4 and P 4 implies P 5
where P is your statement of course,
and so on and so forth. Right? That's what you've proved,
but you haven't actually proved that P 2 is true;
so in some sense, you have this long, long
string of implications, but you don't know that the
first one is true so you don't know that all the other ones are true.
And again, if you think about it like a domino analogy, right,
you know that the second domino will knock down the third one, and the
third one will knock down the fourth one, and the fourth one will knock down the fifth one
and so on and so forth, but you don't know that the second domino falls down.
This is why you need that overlap, right? If you
say here instead "k is greater than or equal to 1"
and then go through the proof and prove it, you proved that
if P 1 falls, then P 2 falls, if P 2 falls, then P 3 falls,
and if P 3 falls then P 4 falls and so on and so forth.
And we know that P 1 falls because that was our base case.
The combination of all of these things gives you the proof that you want.
All that being said, let's see if the next line is right: "That is, assume…"
well we're off to a bad start again.
"P k equals" well P k is a statement,
so P k can't equal a value
which is what this says, so this equals sign doesn't make any sense.
This P k probably just shouldn't be here at all in the induction hypothesis.
Now we have this sum from i equals 1 to k but
for some reason we've also substituted the k in
for the index variable i, that's not right.
Remember the index variable depends on the index here. It doesn't depend on
the index at the top it just depends on the one at the bottom. So when you're replacing the one,
you're replacing the n in the index variable in the statement,
you really do want just the n to become a k
and you want to leave the i's alone because the i's belong to the
index variable in your summation notation.
The right-hand side is correct so we did one out of three things correct there.
The induction conclusion: so for P k plus 1
what do we have? The first line...so
this is actually a reasonable start to our proof.
We start with the left-hand side of the thing we're trying to prove
but instead of n we have a k plus 1,
and now we're trying to go through and get to the end. So this is actually okay.
Some people probably leave the n here and that's technically wrong
you really do want a k plus 1 here.
Unless you tell the reader that you're making n k plus 1 but
I wouldn't do it like that, I would do it like this. So that's okay.
We've broken off the last term and it looks like we've done it correctly. So you're
taking the sum from 1 to k of i over 3 to the i, you leave that alone,
and now you're plugging in the last term k plus 1 over 3 to the power of k plus 1.
The next line: this is a line that you really should explain.
This is not immediately clear.
What's happening here though is that you're using the induction hypothesis.
You really should sell the reader "Hey I'm using the induction hypothesis at this point".
Okay now this is fine.
The next line we attempted to find a common denominator but
we've left our denominator the same.
So we really should have 4 times 3k plus 1 on this fraction…
that's a mistake…
Here's another mistake that a lot of people made. So this is, you know,
these two fractions, we're taking 3/4
minus 6k plus 9
plus 4k plus 4.
Really, this negative goes to both of the terms in the numerator.
The next line you've just written the sum of the
things on the top however both of these terms should have been negative from this negative.
When you write the fraction like this, the negative is actually going to all four terms.
So now you're going to get, you know, you're going to get
negative 10k minus 13 as opposed to
minus 6k minus 9 plus 4k plus 4.
This is a very bad mistake to make. Remember that when you're doing this, you
really want to bring the negative in first and then add the numerators.
Down here we've clearly cheated.
There's no way to make negative 10k plus 13 look like
negative 2 times k plus 1 plus 3.
Don't cheat like this, it's very obvious that there's steps missing.
"Therefore P k plus 1 is true."
It's good that you have a start of a concluding statement
but that's not really what... we're not done yet, right?
Why can we conclude, therefore, that P n is true for all natural numbers n?
That's because of the Principle of Mathematical Induction.
So we really should have a full concluding statement that says,
“therefore P n is true
for all natural numbers n by the Principle of Mathematical Induction."
Okay...
So...
I think I found all mistakes in this
proof. At least all the ones I intentionally made, I found.
Now, let's try to write this up a little bit better, a little bit cleaner, a little bit nicer.
By the way, grading this would be very difficult because
realistically no step is correct.
Everything looks like it's good, but
your base case has errors, your statement at the beginning is unclear,
your induction hypothesis is a disaster,
your induction conclusion has right elements like
you broke it up but I mean other than that,
much of this is incorrect in terms of manipulations,
and you don't have a concluding statement. this would be a tough proof to mark
and giving it 0 would probably not be that unreasonable despite the fact that
many of the ideas that you need are here.
Let's go to an actual proof.
Okay, so same question.
I'm going to try to give you a proof that I've written. Hopefully it's correct, we'll see.
So proof, we're going to start off a little bit better. Let P n be the statement,
the sum from i equals 1 to n of i over 3 to the i
is equal to 3/4 minus 2n plus 3 all divided by 4 times 3 to the n."
We prove that the statement is true for all natural numbers n by induction.
So the base case when n equals 1, I have a "right-hand side to left-hand side" proof
and I'm starting with the right-hand side.
Notice, by the way, in this case this statement is true.
The right-hand side is equal to this
difference of fractions.
This difference of fractions is equal to this
and this thing is equal to this difference of fractions here.
Again, arguably maybe I should have written it with the
equal sign in a column down, like I did down here.
The only reason why I didn't is because I wanted it to fit on one page.
So that's fine. Hopefully the "math grammar people" won't get too mad at me.
Anyway, this is equal to 3/4 minus 5/12. Just plug it in,
do a little bit of arithmetic, get down to 1/3 and 1/3 is this summation:
the sum from 1 to 1 of i over 3 to the power of i,
and that is the left-hand side. So now I've started with the right-hand side
and gotten to the left-hand side. That is a complete and valid proof.
So therefore, P 1 is true.
Now my induction hypothesis, I've written it out
a little bit different than I probably normally would, but there's a reason why.
"Assume P k is true for some..."
integer," remember we're only assuming that this is true for a single case. A lot of
students wrote "for some natural numbers",
"for some integers”, no, it's really just
for some single integer
k greater than or equal to 1.
That is, we are assuming that
the sum from 1 to k of i over 3 to the power of i is
3/4 minus 2k plus 3 all divided by 4 times 3 to the power of k.
Can you write just for some natural number k?
You absolutely can, but I wanted to make it clear that
k is greater than or equal to 1, and why the 1 here? Because
the last base case we proved was n equals 1. You want that overlap,
right, for the same reason that we talked about earlier.
So now in my induction conclusion, we now prove that
P at k plus 1 is true. That is, we'd like to prove this statement...
that probably should be a period here...
so we want to prove that the sum from 1 to k plus 1
of our fraction is equal to this right-hand side.
This is the statement that we want to prove. So it's very
clear what we want to prove, and now I'm going to take the left-hand side and
derive the right-hand side, which is what I say next.
We do the fraction break off as normal,
I cite when I use the induction hypothesis, which is from step one to step two.
From here now,
I'm finding my common denominator, so 4 times 3 to the k plus 1,
and I'm bringing the negative sign in so that now when I add my fractions
I actually get the correct value.
I break up the 5 as minus 2 minus 3.
All these terms are negative so I remove the fraction once again.
I factor out my 2 and I get the exact thing I want on the right.
So therefore, P(k) plus 1 is true, and now your formal concluding statement:
"Thus by the Principle of Mathematical Induction, P n is true for all natural numbers n.”
That's it, this is a complete proof. I think it is
correct and would earn full marks and everything is good.
But that is it. So hopefully,
I've given you a little bit of insight as to some
common mistakes that people make when writing an induction proof,
and hopefully this helps you to frame future induction proofs properly.
One final piece of advice: again, whenever...
whenever a student comes to me and says that they're stuck with an induction proof,
one of the first things I ask them is, "Well did you write down the statement P at n?"
and many of the times students will tell me, "No I haven't" and I find that
just the act of writing this statement down
often gives students a really big push as to
how to start your induction proof and how to frame it properly and how to finish it off.
So if I can give you one piece of advice with an induction proof
that would be the piece I'd give you. Write down P of n explicitly.
Thank you very much, hopefully this helped.