University of Illinois
Interested in growing your data science career?
Join the next admissions webinar on May 6 and learn more about earning your MCS-DS online.
Macquarie University
Interested in earning an MBA degree online?
Register now for a Global MBA Webinar exploring COVID-19's impact on how we work and learn.

浏览 Coursera 的全部课程

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

Lines and Triangles: Proof by Induction

Loading...

Mathematical Thinking in Computer Science

加州大学圣地亚哥分校

4.4（736 个评分） | 40K 名学生已注册

课程 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（736 个评分）

5 stars
480 ratings
4 stars
161 ratings
3 stars
60 ratings
2 stars
15 ratings
1 star
20 ratings

JV

Oct 16, 2017

I really liked this course, it's a good introduction to mathematical thinking, with plenty of examples and exercises, I also liked the use of other external graphical tools as exercises.

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.

从本节课中

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]

探索我们的目录

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

热门在线课程

适用于所有人的人工智能课程
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.保留所有权利。