You may want to download the Lecture 4 slides (PDF).
1. The Principle of Mathematical Induction
Here, we give a formal definition of the Principle of Mathematical Induction. Then, we look at a connection to programs with loops and recurrences. (12:22)
2. Example of Mathematical Induction
In this video we apply induction to show that the sum of the first n odd integers is n2. Then, we return to discussing how to be precise with summations involving “…” (9:38)
3. More Examples of Mathematical Induction
Here, we use induction to find an equality for the sum of the first n squares. Then, we use induction to show an expression is divisible by 9 for all n. (9:24)
4. An Exercise in Math Induction
See if you can use induction to show that, for n ≥ 2, that 1-1/2+2-1/2+ … + n-1/2 > n1/2. (1:08)
5. The Base Case for an Exercise in Math Induction
In this video we solve the base case for the inequality 1-1/2+2-1/2+ … + n-1/2 > n1/2. The last video of this lecture solves the rest of this problem. (2:35)
6. Basis for Long Division & Greatest Common Divisors
Here we revisit long division, and prove a statement about long division by using induction. Then, we introduce greatest common divisors (GCDs), and look at a naïve way of computing them. (9:01)
7. The Euclidean Algorithm
This video defines the Euclidean Algorithm and implements it by using a while loop. (2:52)
8. A Concrete Example and Back-Tracking
This video explores a concrete example of calculating the GCD using the Euclidean Algorithm. Then, we look at how to find integers a and b such that an + bm = gcd(n, m), by using back-tracking. (10:44)
9. Avoiding Recursive Calls
A practical method for calculating the gcd of two integers by using a loop instead of recursive calls is described in this video. The code that is mentioned is here. (3:08)
10. The Inequality 1-1/2+2-1/2+ … + n-1/2 > n1/2
We complete our proof that, for n ≥ 2, that 1-1/2+2-1/2+ … + n-1/2 > n1/2. (9:20)