Lecture 10: Mathematical Induction
In this lecture on mathematical induction, the Josephus problem is used as an example to explain the concept of recurrence equations. By leveraging the idea that every other person is killed in the first round, the lecture shows how to solve this problem for any number of people in the circle. The lecture then derives recurrence equations for even and odd cases and builds up a table to find the solution for any number of people. This lecture is an excellent resource for anyone looking to understand mathematical induction and recurrence equations.
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/
- 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.
- 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.
