Hi. In this video we're going to study complete induction.

It is also called strong induction.

So what we've learned so far is mathematical induction is actually

sometimes called weak induction because it is not always sufficient.

For some problems, you need a more powerful method of induction.

And it is called strong induction or complete induction.

And we'll apply this method to solve a problem about change and coins.

So the problem is, you have unlimited supply of coins with values 4 cents and 5 cents,

and you need to prove that for any integer n greater than or equal to 12,

you can give change of exactly n cents using only these coins.

Note that answers from 12, this is unusual.

Well, that is because if you think about it for 11 cents,

you cannot actually give 11 cents,

using only coins with values 4 cents and 5 cents.

And you can prove this yourself,

and we're going to concentrate on proving that starting from 12 cents,

you can give any amount of change,

using only coins with letters 4 and 5 cents.

Let's try to prove it by induction as we know it.

So first we need to prove the induction base and it is n equal to 12,

because this is the smallest n for which we need to prove our statement.

And indeed, for n equal 12,

we can represent 12 cents using only coins of value 4 cents.

We just take three coins with value 4 cents and that's all.

Now, we want to prove the induction step,

that if we can make change of amount n with coins of 4 cents and 5 cents value,

then we can make change of n plus 1 cents.

But it is actually unclear how to do that.

How can we prove that if change of exactly n cents is possible,

than we can get from it to somehow giving change of n plus 1 cents?

To do that, we would need to do something like, okay,

here is the way to give change of n point n cents.

And we know that it is possible.

And now we should somehow change

this solution into giving change of exactly n plus 1 cents.

But to do that,

we would need to give 1 cent,

using coins with various 4 cents and 5 cents,

and that is obviously not possible.

So it is unclear how to move from n to n plus 1 here.

And this is why the regular weak induction doesn't work in this case,

and we need to do a little bit more work.

So more work is first bigger induction base.

Instead of proving our induction base just for n equals 12,

we will prove it for n equals 12,

13, 14, and 15.

So for all these numbers,

we will prove manually that these amounts of change can be given exactly,

using only coins of values 4 and 5 cents.

And to get 12 cents,

we already now that we just need to take 3 coins of value 4.

To get 13, we get 2 coins of value 4 and 1 coin of value 5.

To get 14, we get 2 coins of value 5 and 1 coin of value 4.

And to get 15, we just get 3 coins of value 5.

So we've proven the induction base,

that for n from 12 to 15 it is possible to give the change.

Now we're going to prove induction step,

but this induction step will be more complex than usual.

This induction step will say that if for some n,

we know that n cents, n minus 1 cents,

and n minus 2 cents,

and n minus 3 cents,

any of these amounts can be given as change using only 4 cents and 5 cents coins,

then we can also give change of exactly n plus 1 cents.

How to prove this step?

Well, in particular, from the assumption we know that exactly n

minus 3 cents can be given using only coins with 4 and 5 cents,

so that n minus 3 can be given as a coins of value 4 cents and b coins of value 5 cents.

Then n plus 1 can also be given

with the coins because n plus 1 is equal to n_minus_3 plus 4.

And so, basically we get the representation for n minus 3,

we get a coins of value 4,

b coins of value 5,

and we add one more coin of value 4,

and we get the change of exactly n plus 1.

So this is our induction step.

Now, how does it actually lead us to proving everything?

Previously we moved from 0 to 1,

from 1 to 2 and so on.

And here, we cannot just move from 12 to 13,

from 13 to 14 and so on,

we need to do something else.

So let's see the structure of the proof in this case.

So we get this change amount which starts with

12 because this is the smallest amount for which we need to prove it.

And we actually prove manually for 12,

and for 13, and for 14, and for 15.

And now, we also prove the general thing that if for all amounts k, k minus 1, k minus 2,

and k minus 3 it is possible to give change with these coins,

then it is also possible for k plus one.

How we can use this induction step to prove for every n?

Well, first we can take the values for which we've already proven the statement 15,

14, 13, and 12 and use them as k, k minus 1, k minus 2, k minus 3.

And then k plus 1 on the right part will be 16.

And so, from this induction step we get that for 16 it is also possible to give 16 cents,

using coins of 4 cents and 5 cents.

Now, we can add 16 to our knowledge base and we can use 16, 15,

14 and 13 as k, k minus 1, k minus 2,

and k minus 3, and then k plus 1 would be 17.

And so, using our induction step,

we can prove that for 17 cents,

it is also possible to give change using only coins of values 4 cents and 5 cents.

And this way, we can go to 17,

to 18, to 19 and so on,

we can get to any n. And so after proving our induction base for 12, 13, 14,

and 15 and proving

this complex step from k, k minus one, k minus 2, k minus 3 to k plus 1,

we can move to any integer

n. And we have actually proven that for any n that is greater or equal to 12,

it is possible to give the change.

And so, the complete induction comes in one of the two forms.

The first form we've just used with you was we first

prove the induction base manually for the first k values of n,

where k is some parameter that you just choose,

so usually, in the previous videos it was just one.

But in this video k was equal to 4,

so we take first 4 values of n,

12, 13, 14, and 15,

and prove manually the base case.

And then the induction step is that if the statement is

true for n and also n minus 1 and also n minus 2 and so on,

up to n minus k plus 1. so for k integers which go in succession,

then we prove it for n plus 1.

If we get this,

then we can do the same we did with the coins.

So we have the first k values,

and from these k values,

we can move to the k plus first using the induction step.

And then we take the last k values of these and

from them we can go to the k plus second value, and so on and so on.

So if we have proven base for k values of n which are

successive values of n and we have proven

an induction step from k successive values of n to n plus 1,

then we have proven the whole statement.

Another way is, again,

we have the same base for some k values of n,

but the induction step is even more general.

It says that if the statement is true for all previous n,

from the smallest to this n,

then we're going to prove it for N plus 1.

The [inaudible] is if we explicitly assume in the proof of the induction step, for example,

that the statement is true for n minus 10,

if we use this fact to prove for n plus 1,

then we need k to be at least 10.

And this is why in this particular coins problem,

we needed to prove for 4 values manually,

because for proving induction step for n plus 1,

we used explicitly that the statement is true for n minus 3.

So we needed to get four points to prove that.

And this is what complete induction or strong induction means.

And this is actually a more powerful method.

And later you are going to also solve some problems based on complete induction.

Coins Problem

What is a Proof?

Meet the Instructors