Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

Lines and Triangles: Proof by Induction

Loading...

Mathematical Thinking in Computer Science

加州大学圣地亚哥分校

4.5（588 个评分） | 32K 名学生已注册

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

查看授课大纲

您将学习的技能

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

审阅

4.5（588 个评分）

5 stars
382 ratings
4 stars
132 ratings
3 stars
49 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!

从本节课中

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

教学方

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 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司