Loading...

Lines and Triangles: Proof by Induction

Course video 31 of 68

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.

Mathematical Thinking in Computer Science

加州大学圣地亚哥分校

课程 1（共 5 门，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.

查看授课大纲

您将学习的技能

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

教学方

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

脚本

[SOUND] Now we're ready to prove with the induction the following theorem.

For any n greater or equal to 3 and any n straight lines on a plane, if every two of

them intersect, and all the intersection points are different, then there is

a triangular piece among the pieces into which these lines cut the plane.

So let's see the structure of the proof.

First, we prove that for

any three lines that satisfy our requirements, there will be a triangle.

Then, we can make a step from three lines to four lines.

We note, that to get any four lines from the plane,

we can actually first get some three of them on the plane.

And then adds the fourth on top of it.

And we assume that for any three lines on the plane, there will be a triangle.

Given that, we prove that for any four lines there will be triangle.

To do that, we remember that when we add a new line,

either a new triangle appears or the same triangle stays.

So we can prove that if, for n equals 3 our statement is true,

then it is true for n equals 4.

And we already know, because we've proved it separately,

that for n equals 3 the statement is true.

So now we can make the step from 3 to 4, and

we know that for any four lines there will be a triangle.

Now we want to make the next step and prove that for

any five lines, there will be a triangle.

To do that, we prove a step from 4 to 5 that if we assume that for

any four lines there is a triangle, then we can prove that for

any five lines there will be a triangle also.

To do that, we say that any five lines you can get by first selecting some

four of them, drawing them, and then adding the fifth one on top.

By the assumption of our induction for

those four lines, there will be some triangular piece.

And when we add the fifth line on top,

either the same triangle remains or a new triangle appears.

So for those five lines there will also be a triangle.

And so, we know that if for four n equals 4,

our statement is true, then it is also true for n equals 5.

And we actually already know that for n equals 4 the statement is true, so

now we know that it is also true for n equals 5.

And we can make the same step from 5 to 6, but

what we want to do is to make all the steps at the same time.

One to go from 6 to n for any integer n, which is greater or equal than 3.

To do that, instead of doing one step at a time, which would take for

us infinite time, we prove a more general thing.

That if for some k,

we have proven that any for any k lines on the plane there is a triangle.

Then for any k + 1 lines there will also be a triangle.

And to do that, we'll say that to get any k + 1 lines, we can first select some k of

them, draw them on a plane, and then add the k plus first one on top of it.

We know that for those k lines there will be a triangle, and

we know that when we add the k plus first line,

either this triangle remains or a new triangle appears.

So if for k, the statement's true, then it is also true for k + 1.

And as soon as we have proven that in the general case from k to k + 1,

we can actually make the step from 6 to n.

And actually, we didn't need to prove the intermediate steps from 3 to 4,

from 4 to 5, from 5 to 6.

We could just go directly from 3 to n,

as soon as we have proven this general case from k to k + 1.

And this is how mathematical induction works.

So our proof as a whole consists of the following parts,

first we'll prove what is called induction base.

This is the basic statement for

some smallest value of n for which we need our statement.

In this case n equals 3 and three lines.

We prove that there will be a triangle for three lines.

Then, we prove that if our statement true for n equals 3,

then it is true for n equals 4.

After that we prove that if it is true for n equals 4,

then it's also true for n equals 5, and so on.

And then we prove the more general thing which is called induction

step from n to n + 1.

We proved that in the general case, if for any n lines there is a triangle,

then for any n + 1 lines, there is a triangle.

And then after we've proven both the induction base and

induction step, we actually have the profit we needed.

We have proven the whole theorem, the whole statement, and

actually we can shorten this path a little bit.

And what we'll get is that, we actually need to do only two things,

prove the induction base in this case n equals 3,

and prove the induction step from n to n + 1 in the general case.

We don't need these intermediate steps from three to four,

from four to five, and so on.

Just prove the general induction step.

And if we have proven those two things, then we have proven our theorem.

And we will see more examples of that in the next videos.

[SOUND]

[MUSIC]

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取