Checking a formula for n = 1, 2 and 3 is not a proof. A claim about every whole number needs a method that reaches all of them.
Step 1: Let's Learn
Read it, or press Listen and follow the words.
The domino picture
Knock over the first domino, and show that each one topples the next. Every domino falls, however many there are.
The base case
Verify the statement for the smallest value, usually n = 1. This is the first domino.
The inductive step
Assume the statement holds for n = k, then prove it holds for n = k + 1. This is the toppling rule.
The assumption is not cheating
You never assume what you are proving. You assume one case and derive the next, which is a conditional statement.
Both parts are required
Without a base case, a false formula can still satisfy the step. Without the step, one true case proves nothing.
Two steps prove infinitely many cases
Show the statement holds for the first value, then show that whenever it holds for k it holds for k + 1. Together these force it for every whole number, like dominoes falling.
The base case is not a formality
Without a first domino, nothing falls. There are statements whose inductive step works perfectly and which are false because no base case holds. Verifying the base case is a genuine part of the proof.
Assuming the case you are proving is allowed
The inductive hypothesis assumes the statement for k in order to prove it for k + 1. That is not circular: you are proving an implication, not the statement itself, and the base case supplies the starting truth.
What it proves
Summation formulas, divisibility claims, inequalities, and properties of recursive definitions. Any statement indexed by the whole numbers is a candidate, which covers a large part of discrete mathematics.
Step 2: Try It Yourself
Tap and try it out.
Step 3: Watch an Example
One step at a time.
Watch Yusuf Prove 1 + 2 + ... + n = n(n+1)/2
Yusuf must show this holds for every whole number n.
- Step 1
For the base case n = 1, the left side is 1 and the right side is 1(2)/2 = 1, so they agree.
Step 4: Your Turn
Practice makes it stick.
The Base
Problem 1 of 2
For 1 + 2 + ... + n = n(n+1)/2, what does the right side give when n = 4?
The Missing Part
Problem 2 of 2
A proof verifies n = 1 but never proves the step from k to k + 1. Is it complete? Enter 1 for yes, 0 for no.
Build the Proof
1 of 8
n(n+1)/2 at n = 6?
2 of 8
n(n+1)/2 at n = 10?
3 of 8
The sum of the first n odd numbers is n². What is it for n = 5?
4 of 8
How many parts does a proof by induction have?
5 of 8
In the inductive step, which case do you assume? Enter the value as a number of steps past k, so 0 means k itself.
6 of 8
The sum of the first n odd numbers at n = 8?
7 of 8
Put a proof by induction in order.
- 1Verify the base case, usually n = 1.
- 2Assume the formula holds for n = k.
- 3Derive the formula for n = k + 1.
- 4State the formula to be proved.
8 of 8
n(n+1)/2 at n = 100?
Step 5: Quick Check
Show what you know.
Question 1 of 2
n(n+1)/2 at n = 8?
Question 2 of 2
Why is a base case necessary?
What You Learned
- Induction proves a statement for every whole number using two parts.
- The base case starts the chain; the inductive step passes it along.
- Assuming n = k to prove n = k + 1 is a conditional argument, not circular reasoning.