Lecture 10: Mathematical Induction

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
12659 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:
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

    • Currently 4.0/5 Stars.
    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.