Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

Odd Points: Proof by Induction

Loading...

Mathematical Thinking in Computer Science

Universidade da Califórnia, San Diego

4.5 (567 classificações) | 31K alunos inscritos

Curso 1 de 5 no Introduction to Discrete Mathematics for Computer Science Programa de cursos integrados

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. Do you have technical problems? Write to us: coursera@hse.ru

Visualizar o programa do curso

Habilidades que você aprenderá

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Avaliações

4.5 (567 classificações)

5 stars
369 ratings
4 stars
126 ratings
3 stars
47 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

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

Ministrado por

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

Transcrição

[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.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados