Lecture 10: Mathematical Induction
12693 views
|
1
rating
Lesson Description:
A formal lecture explaining in depth what mathematical induction is and how to use it.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 4 - A problem set with some problems from this lecture
- Problem Set 4 Solutions - Solutions to the Problem Set
- Mathematical Induction - An explanation of how to prove a statement by induction.
- Mathematical Induction 2 - Another extensive explanation of induction.
Questions answered by this video:
- What is mathematical induction and how is it used to prove conjectures?
- What is the Josephus problem and how do you solve it and know where to sit to avoid execution?
- If every other person around a circle is killed until just one person remains, how can you determine who will be saved using recursion?
- How do you prove the Josephus problem using induction?
- How do you sum up the nodes of a binary tree?
- What are some example induction conjectures in which the base cases are not true but all other values work?
- How do you prove that a binary tree of height n has less than or equal to 2^n leaves using induction?
- What is the difference between weak and strong induction?
-
Staff Review
An interesting problem called the Josephus problem is explained and analyzed in the first part of this lesson. Recursion turns out to be a central part of this analysis, and induction is used to prove that a conjecture is true. It turns out to be a really cool solution and a cool inductive proof. Then, more problems are done using induction. This is a fun, very useful Discrete Math lecture.
