Lines and Triangles: Proof by Induction - Recursion and Induction | Coursera

浏览 Coursera 的全部课程

企业版面向学生

浏览
顶级课程
登录
免费加入

Lines and Triangles: Proof by Induction

Loading...

Mathematical Thinking in Computer Science

加州大学圣地亚哥分校

4.4（1,149 个评分） | 58K 名学生已注册

课程 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

审阅

4.4（1,149 个评分）

5 stars
63%
4 stars
24%
3 stars
8%
2 stars
2%
1 star
3%

YA

May 24, 2020

I have come to know how mathematical proof is fun thing to do, this course transformed me, i highly recommend it to every one. I would like to thank every one involved in providing this course.

MH

Jun 26, 2020

This course will improve your problem solving skills and gives you a rigorous explanation in how to counter various mathematical problems in the real life. You will think like a mathematician.

从本节课中

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 discrete mathematics and computer science. In particular, you will see them frequently in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. For some computational problems (e.g., exploring networks), recursive solutions are the most natural ones. The main idea of recursion and induction is to decompose a given problem into smaller problems of the same type. Being able to see such decompositions is an important skill both in mathematics and in programming. We'll hone this skill by solving various problems together.

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]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

热门在线课程

适用于所有人的人工智能课程
TensorFlow 简介
神经网络与深度学习
算法第 1 部分
算法第 2 部分
机器学习
使用 Python 进行机器学习
使用 SAS Viya 进行机器学习
R 语言程序设计（中文版）
Matlab 编程入门
使用 Python 进行数据分析
AWS 基础知识：走向云原生
Google 云端平台基础知识
网站可靠性工程
英语专业说
幸福科学
选修“如何学习”这门课
金融市场
公共健康领域的假设检验
日常领导基础知识

热门在线专项课程

深度学习
零基础 Python 入门
数据科学
借助 Python 应用数据科学
商务基础
Architecting with Google Cloud Platform
Google 云端平台数据工程
Excel 到 MySQL
高级机器学习
数学在机器学习领域的应用
自动驾驶汽车
企业区块链革命
商业分析
Excel 办公技能
数字化营销
使用 R 进行公共健康领域的统计分析
免疫学基础知识
解剖学
管理创新和设计思维
积极心理学基础知识

在线证书

Google IT 支持
IBM 客户关系专员
IBM 数据科学
应用项目管理
IBM Applied AI 专业证书
用于分析的机器学习
空间数据分析和可视化
建筑工程与管理
教学设计

在线学位课程

数据科学硕士
计算机科学学士学位
计算机科学与工程学位
机器学习硕士
MBA 和商学学位
电气工程硕士
公共健康硕士
信息技术硕士

Coursera

关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园
新冠疫情响应

社区

学生
合作伙伴
开发者
Beta 测试人员
专业译员
博客
技术博客

更多

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

通过 Google Play 获取

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