Lecture notes · Math for Computer Science · Lecture 2

Induction

MIT 6.042J Mathematics for Computer Science, lecture 2, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part teaches proof by contradiction, a way to prove something is true by assuming it is false and showing that leads to an impossible result.

Key ideas

A proof by contradiction starts by assuming the opposite of what you want to prove. You then make logical steps forward until you reach a contradiction, which is something that cannot be true. 1:56
If your assumption leads to a contradiction, the assumption must have been wrong. So the thing you wanted to prove must be true. 2:18
To show that the square root of 2 is irrational, you assume it is rational, so it can be written as a fraction a over b in lowest terms. Squaring and rearranging shows that a and b are both even. 6:23
But a fraction in lowest terms cannot have both a and b even, since they would share a common factor of 2. That contradiction shows the square root of 2 is not rational, so it must be irrational. 8:46

Words to know

contradiction: A statement that cannot be true, such as saying something is both true and false at the same time.
irrational: A number that cannot be written as a fraction of two whole numbers.
lowest terms: A fraction that has been simplified so the top and bottom numbers share no common factors except 1.
divides: One number divides another if the second number can be split into equal whole groups of the first, like 2 dividing 8.

Example

Think of checking a receipt. If the receipt's total only adds up correctly when you assume two different prices for the same item, then the receipt must be wrong. In the same way, assuming a claim is false and finding a clear impossibility shows the claim is true.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains how the ancient Greeks' beliefs about numbers ran into trouble with the square root of 2, and how a false proof that 90 is bigger than 92 shows the danger of trusting a drawing.

Key ideas

The ancient Greeks held as a basic belief that irrational numbers did not exist, because they could not be written as a repeating pattern of finite length. They liked finite, neat numbers like one seventh. 10:43
They also believed every line you could draw had a finite length, so every length was rational. Their own geometry theorem said the square root of 2 was rational, but a later proof showed it was irrational. 12:11
The square root of 2 proof made their beliefs contradict each other, which is called inconsistent. Once beliefs contradict each other, every theorem built on them is open to doubt. 12:31
The false proof that 90 is bigger than 92 relied on a drawing that was not to scale. The mistake was in the picture at the very start, and the rest of the steps looked fine. 18:34
Writing a proof out step by step makes it easier to find a bug, because you can go back and check each step. 19:36

Words to know

axiom: a basic belief or rule that you accept without proof and build other proofs on.
rational number: a number that can be written as a fraction, so its decimal form ends or repeats in a pattern of finite length.
irrational number: a number that cannot be written as a fraction, so its decimal goes on forever without a repeating pattern.
inconsistent: when two or more beliefs or rules contradict each other, so they cannot all be true together.

Example

Imagine a subway map drawn with two stops that look far apart on paper, but the map is not to scale. If you plan your trip from the picture, you might make wrong choices, even though every step of your plan seems sensible. The error came from the drawing, not from your reasoning.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part introduces proof by induction, explains why it works as a rule we accept, and shows the first steps of a sample proof about adding up numbers.

Key ideas

Induction is an axiom, meaning a rule we accept without proof. If P(0) is true, and each P(n) being true makes P(n+1) true, then P(n) is true for every natural number n. 21:02
The dominoes picture helps: each domino falling knocks over the next one. Knowing P(0) is true starts the chain, and each step passes the truth along forever. 23:25
The dot-dot-dot notation (1 + 2 + ... + n) is vague and causes mistakes. Sigma notation says the same thing more precisely. 25:08
Edge cases matter. When n is 1, the sum is just 1, because there is no 2 in it. When n is 0 or less, the sum is 0, because nothing is added. 26:16
Every induction proof starts by writing down that you are using induction, then stating the predicate P(n), then checking the base case, and then the inductive step. 28:15

Words to know

axiom: A basic rule that we accept as true without proving it first.
predicate: A statement with a letter in it, like P(n), that is true or false depending on the value of n.
base case: The first step of an induction proof, where you check that the statement is true for the starting value, such as n = 0.
sigma notation: A short way to write a sum using the capital Greek letter sigma, so you do not have to write out every number with dots.

Example

Imagine a ladder that goes up forever. If you can step onto the first rung, and you know that any time you stand on one rung you can step to the next, then you can reach every rung. Induction works the same way: the base case gets you on the first rung, and the step from one case to the next gets you to all the others.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how to prove a statement holds for every whole number n by checking a starting case and then showing that each case leads to the next, using a sum formula and a divisibility-by-3 example.

Key ideas

The base case is the first check: you show the statement is true for n equals 0. Students often forget this step, but the proof needs it. 30:00
The inductive step shows that if the statement is true for n, it must also be true for n plus 1. You only need to worry about the case where the statement for n is true, because an implication is automatically true when its first part is false. 31:09
In the inductive step you assume the statement for n, which is called the inductive hypothesis, and then use that assumption to show the statement for n plus 1. This is a valid method even though it can look like you are assuming what you want to prove. 31:32
Induction proves that a formula is right, but it often does not help you find the formula. You usually need a good guess first, and then induction confirms it. 35:32
In the second example, you must show that 3 divides n cubed minus n for every whole number n. After expanding the n plus 1 case, the remaining job is to show that n cubed plus 3n squared plus 2n is a multiple of 3. 39:59

Words to know

base case: The first check in a proof, where you show the statement is true for the starting value, usually n equals 0.
inductive step: The part of the proof where you show that if the statement is true for one value, it is also true for the next value.
inductive hypothesis: The statement you assume is true for some value n, so you can use it to show it is true for n plus 1.
implication: A statement of the form 'if this, then that.' It is only false in the single case where the first part is true and the second part is false.

Example

Think of a row of dominoes. If the first domino falls (base case), and every domino that falls knocks over the next one (inductive step), then every domino in the row falls. Induction works the same way: one starting check plus one reliable link between each step covers every case.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part shows the standard steps of a proof by induction, how to start one at a number other than 0, and why a flawed proof (about horses) fails.

Key ideas

A proof by induction always follows the same steps: write down "proof by induction," name your predicate, do the base case, then do the inductive step. 41:50
The predicate must depend on a number n, so you can plug in values. The statement "all horses are the same color" has no number to plug in, so it cannot be the predicate. 43:57
The base case is usually n equals 0, but you can start at any integer b. Then you check the starting point and the step for every n from b onward. 42:16
In the inductive step, you assume pn is true and use that assumption to show that pn plus 1 is true. 46:08
A warning sign of a weak proof is not using the inductive hypothesis, the fact you assumed. If you don't use it, you aren't really using induction. 40:21

Words to know

predicate: A statement that has a number n in it, so it can be true for some values of n and false for others. For example, "n cubed minus n is a multiple of 3" is a predicate.
base case: The first step of an induction proof, where you check that the statement is true at the starting value, usually n equals 0.
inductive step: The main step of an induction proof, where you show that if the statement is true for n, it must also be true for n plus 1.
inductive hypothesis: The statement you assume is true for some n during the inductive step. The lesson says it is another name for pn.

Example

Think of a line of dominoes. The base case is knocking over the first domino. The inductive step is the rule that any domino falling knocks over the next one. If both are true, every domino falls. (This is an everyday comparison I am adding to help the idea click, not something from the lesson.)

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how a proof by induction can go wrong when its steps are not checked carefully, using a famous horse-color example.

Key ideas

The horse claim says every set of horses is one color. The professor says that in a proof, you must check the claim for any set you pick, not just one set. 50:20
The inductive step shows that if the claim is true for n horses, it is true for n plus 1 horses. You do this by splitting a set of n plus 1 horses into two overlapping sets of n horses. 50:41
The mistake hides in the dot-dot-dot notation. When n equals 1, the overlap between the two smaller sets is empty, so there is no link to compare, and the step from one horse to two horses was never proven. 54:46
A proof by induction needs two parts: a base case that is true, and an inductive step that works for every case from the base case upward. Missing either part breaks the proof. 56:15
The base case fails for two horses, because a pair of horses can have different colors. So the base case is the check that catches the false claim, and you should always check it. 57:44

Words to know

proposition: a statement that is either true or false.
base case: the starting point of an induction proof, where you show the claim is true for the first number.
inductive step: the part of the proof that shows if the claim is true for one number, it is also true for the next number.
empty set: a group with no members at all, like a box with nothing inside it.

Example

Think of a chain of linked paper clips where each clip is hooked to the next. If you show that any clip hooked to the next one is connected, you still need the first clip to be attached to something, or the whole chain never starts. The base case is like that first clip, and the inductive step is like the hooks between clips.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

The lecture starts proving, by induction, that a courtyard of size 2 to the n by 2 to the n can be tiled with L-shaped tiles and one center square left for a statue, and finds that the first try does not work.

Key ideas

The puzzle: cover a courtyard that is 2 to the n by 2 to the n with L-shaped tiles, leaving only the center square empty for the statue. For n equals 2, the lecture shows it can be done. 1:01:15
Induction is a proof method with two parts. First you show the claim is true for the smallest case (the base case). Then you assume it is true for some size n and show it must also be true for n plus 1. 1:02:50
The base case is n equals 0. The courtyard is then just one square, which is the spot for Bill, so there are no tiles to place and the claim holds. 1:04:14
To use the assumption for n, the lecturer splits the bigger courtyard into four smaller blocks. Each block needs a missing corner so one L tile can fill the middle, but the leftover block does not have its missing square in the center, so the assumption does not apply yet. 1:07:26
The proof as written has a gap, so the lecturer says the induction hypothesis (the statement assumed to be true) must be changed. 1:09:40

Words to know

induction: A way to prove something for every size. You prove the first case, then prove that if one case works, the next one works too.
base case: The first, simplest case you check by hand. Everything else builds on it.
inductive hypothesis: The statement you assume is true for some size n, so you can use it to prove the statement for the next size.
predicate: A statement that depends on a number, such as P(n), which is either true or false for each n.

Example

Think of a row of dominoes. If the first one falls, and every domino is set up so that it knocks over the next one, then all of them fall, even though you never checked each one by hand. Induction works the same way: the base case starts the fall, and the inductive step passes it on.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:19:22

The professor shows that to prove a harder claim with induction, you can state a stronger assumption, which often makes the proof easier.

Key ideas

The inductive step splits a big square into four smaller regions and places one L-shaped tile in the middle. Each smaller region already has one missing square, so the assumption can be applied to each region. 1:10:19
Proving that Bill can sit in a corner was not enough, because the goal was to put Bill in the center. The team tried a helper result, called a lemma, to get closer to the goal. 1:11:05
The better move was a stronger assumption: any square could be missing, not just a corner. This sounds harder to prove, but it gives more to work with in the inductive step. 1:15:40
When the big square grows, the missing square can move to a different spot, and that is fine because the stronger assumption covers any spot. 1:17:37
The general rule is that if a proof does not work at first, try a harder, stronger claim. Choosing the right assumption is the key skill in induction. 1:18:41

Words to know

inductive hypothesis: The assumption you make about a smaller case, which you use to prove the next, bigger case.
base case: Checking that the claim is true for the smallest case, such as a 1 by 1 square, to get the chain started.
lemma: A helper result you prove first so that it can be used to prove a bigger result.
tile: To cover a floor or area completely with flat shapes, with no gaps and no overlaps.

Example

Think of a line of dominoes. If you know that each domino knocks over the next one, and you have knocked over the first one, then every domino falls. Induction works the same way: prove the first case, then prove that each case leads to the next.

3 checked practice questions for this part are in the app.

← Lecture 1: Introduction and Proofs · Lecture 6: Graph Theory and Coloring →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York