## Lecture 10: Mathematical Induction

Lecture 10: Mathematical Induction
• Currently 4.0/5 Stars.
11849 views, 1 rating - 01:19:47
Part of video series ArsDigita Discrete Math Course
Taught by ArsDigita
A formal lecture explaining in depth what mathematical induction is and how to use it.
• 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?
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.
• Currently 4.0/5 Stars.
Reviewed by MathVids Staff on April 16, 2009.  