Odd Points: Proof by Induction

Loading...

Do curso por University of California San Diego

Mathematical Thinking in Computer Science

233 classificações

University of California San Diego

Mathematical Thinking in Computer Science

233 classificações

Curso 1 de 5 em Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Na lição

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 make convincing arguments for arbitrarily large and complex problems 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.

Introduction, Lines and Triangles Problem10:16

Lines and Triangles: Proof by Induction5:59

Connecting Points12:59

Odd Points: Proof by Induction5:29

Sums of Numbers8:52

Bernoulli's Inequality8:01

Coins Problem9:45

Cutting a Triangle8:40

Flawed Induction Proofs9:28

Alternating Sum9:09

Conheça os instrutores

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

[MUSIC]

Now we're ready to proof the whole statement about points that always

regardless of number of points, and number of segments, and which points

are connected, and which are not, the number of odd points is always even.

The proof structure is the following,

first we prove that when there are no segments,

then disregarding number of points, the number of odd points is always even.

Because actually the number of odd points is 0 and 0 is even.

So for 0 segments, we have proven our theorem.

Now we're going to do induction based on number of segments and

we're going to make a step from 0 segments to 1 segments.

We assume that for 0 segments, the number of odd points is always even.

And we prove that in that case, for any one segment, if there

are some number of points and exactly one segment connecting to some pair of points,

the number of odd points is also even.

And to do that, we use the fact that when we add a segment,

the number of odd points if it was even, it stays even.

And we know that it was even with 0 segments.

So after adding this 1 segment, it stays even.

And so we now know that for 1 segment,

our theorem is also true, because we know that for 0 it is true, and

assuming that for 0 it is true, we have proven that for 1 it is also true.

And so 1 we can go from 1 segment to 2, because if we want to do something for

two segments, we can choose one of them to be the first one.

And then we know that if we just add

only this first segment then number odd points will be even.

And then after we add the second segment on top of it, the number of odd points

will stay even, so for any 2 segments the number of odd points is also even.

And then we can make the step from 2 to 3, and so on.

But we want to make all the way to n, and to do that we prove the general thing,

that if for some k, for any case segments connecting some number of points,

number of odd points is always even.

And then for any k + 1 segments and any number of points connected by

those k + 1 segments, the number of odd points will also stay even.

And this step can prove be proven in the same way.

We know that in the general case when we add a new segment,

the number of odd points stay the same or is increased or decreased by 2.

So if it was even, it stays even.

And given this induction step from k to k + 1, we can make the step from 3 to n.

And actually we could skip all those intermediate steps from 0 to 1,

from 1 to 2 and so on.

We could just prove that for 0 segments, our theorem is true.

And the step from k to k k + 1 in the general case.

And that would already allow us to go from 0 to any n.

And actually, we can skip all those intermediate steps and

just prove the induction base for n = 0.

Prove the induction step from n to n + 1.

And we get the profit, we have proven our theorem.

Now let's remember, why did we need this theorem?

We had a problem about 9 points.

We had 9 points and we wanted to connect some of them

with segments in such a way that every point has exactly 5 neighbors.

So let's suppose we succeeded, and then all 9 points would be odd

because each of the 9 points has 5 neighbors.

5 is an odd number and so the point is odd and so all 9 points are odd.

But then, the number of odd points will be 9.

But we know from the theorem that for any configuration of segments,

the number of odd points must be even.

And 9 is not even, so it is impossible.

And indeed, for 9 points it is impossible to find a solution.

So for ten points we have shown an example how to connect

them in a nice symmetric way so that each point has exactly five neighbors.

But for 9 points it isn't possible.

We could try proving it by drawing every possible combination of segments for

9 points and showing that it doesn't satisfy our requirement

that there is at least one point that doesn't have exactly 5 neighbors.

But, instead of doing that, that will take a ton of time.

Instead of doing that, we have proven using mathematical induction some

supportive statement about the number of odd points that it is always even.

And then based on that, we proved that this problem cannot be solved.

And in the next video, we're going to talk about famous mathematician,

and a problem that his teacher gave him in school.

[MUSIC]

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play