Калифорнийский университет в Сан-Диего

What is a Proof?

113 ratings

Course 1 of 5 in the Specialization Introduction to Discrete Mathematics for Computer Science

There is a perceived barrier to mathematics: proofs. In this course we will try to convince you that this barrier is more frightening than prohibitive: most proofs are easy to understand if explained correctly, and often they are even fun. We provide an accompanied excursion in the “proof zoo” showing you examples of techniques of different kind applied to different topics. We use some puzzles as examples, not because they are “practical”, but because discussing them we learn important reasoning and problem solving techniques that are useful. We hope you enjoy playing with the puzzles and inventing/understandings the proofs. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

From the lesson

Recursion and Induction

We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to prove complex things by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Recursion9:45

Coin Problem4:45

Hanoi Towers7:25

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Now, consider the following coin problem.

So our goal is to prove that any integer amount starting from 8 can

be paid using coins of denominations 3 and 5.

Okay?

So this is our problem, and let's try to investigate.

So first of all, let's check whether 8 and 9 and 10 and 11 can be indeed paid.

So this looks reasonable because 8 is 3 + 5,

9 is 3 + 3 + 3, 10 is 5 + 5,

11 is 3 + 3 + 5, so it seems to be possible.

However, it is still not at all clear whether it is possible for all values.

It is also not at all clear

why are we talking about this problem in the lesson called recursion.

Because recursion was about programs or about definitions.

At the same time, what we are going to do

is to prove that this is possible using recursion.

And in fact, we are going to implement the program that is going

to change any such amount into coins of denominations 3 and 5.

So for this, as usual, let's think about these problems.

So we know already that we can pay 8.

But this immediately that we can also pay 11, right?

Because 11 is just 8 + 3.

So in a sense, we reduce the problem of change in 11

into coins to the problem of changing 8 into coins.

But for 8, we that this is possible which means that for 8, for 11,

it is also possible.

Moreover, if you know how to change 8 then by adding just one single coin,

you had a change for 11, right?

And also 11 in terms, gives 14 then 17 then 20 and then so on.

So an infinite number of amounts can be changed into points 3 and

5 just because 8 can be changed into 3 and 5, right?

Then we would do the same trick with 9.

So it seems we know how to change 9 then we know how to change 12,

15, 21 and so on.

And 10 gives us 13, 16, 19, 22 and so on.

Right?

So this gives us the possibility to implement the following

recursive procedure.

We call the change, and it is given an amount that we need to change.

And the first thing to do,

we check whether the given amount is indeed greater than 8, right?

Then if it is equal to 8 then we just return the representation of 8,

the sum of 3 and 5.

So we just return a list of two points.

If it is equal to 9, we return three coins, 3, 3 and 3.

If it is equal to 10, we return two coins, 5 and 5.

On the other hand, if it is greater, then we do the following.

We first subtract 3 from the amount.

Then we make a recursive call which returns us the set of

points needed to change the amount- 3, right?

So we make a recursive call.

We solve the same permutational problem.

So with this point, we have some subset of coins,

some list of coins that sum up to amount- 3.

So if we add just one single coin with denomination 3

then we have a change for the whole amount, right?

And this is exactly what we do here.

We append 3 to coins, and we return the result in.

Okay, so this is a recursive program, which changes any amount.

And the fact that it changes any amount is guaranteed by the fact that if you get any

number, which is greater than 8.

And you start and you keep subtracting 3 from it,

then at some point, you will reach either 8 or 9 or 10, right?

So for this reason, this algorithm actually proves, this problem proves

that any amount can be changed using coins with denominations 3 and 5.

And it actually proves this constructively.

Meaning that it not only proves that it is possible,

it actually produces the answer for each possible amount.