### 1 video in "Mathematical Induction"

## Lecture 10: Mathematical Induction

Lecture 10: Mathematical Induction

8822 views, 1 rating - 01:19:47

Part of video series ArsDigita Discrete Math Course

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/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

A formal lecture explaining in depth what mathematical induction is and how to use it.

- 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?

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.