Back to the on-screen lesson ·
The base case, the hypothesis for one particular k, the step that carries k to k+1, and the formula whose step works perfectly and is false everywhere.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write an induction in its parts — state the claim as a statement about one n, check the base case by arithmetic, assume the claim for one particular k, and write the quantity at k+1 so that the quantity at k appears inside it — and finish by naming the principle of induction. You will also be able to say what the base case is for, having seen a formula whose inductive step is correct and which is false at every value of n, and to say when strong induction is the form the step needs.
Lesson 9 ended on the gap: forty confirming cases say nothing about the forty-first, because nothing connects them. Induction is the connection. You have also met it before — sequences and series in precalculus use it — and what is new here is the insistence that the hypothesis is about one $k$ and that the last line names the principle.
The base case is the claim checked at the smallest value. The inductive hypothesis is the claim assumed for one particular $k$. The inductive step derives the claim at $k+1$ from it. The principle of induction is the axiom that these two together give the claim for every $n$ at or above the base. Strong induction assumes the claim for every value up to $k$ rather than just at $k$.
To prove $P(n)$ for every $n \ge n_0$:
The hypothesis is the part to be careful with. You assume $P(k)$ for one particular $k$, not for every $n$. Assuming it for every $n$ is assuming the claim, and a proof that does it has proved nothing however correct the rest is.
Why the base case is not a formality. Consider $1 + 2 + \cdots + n = \tfrac{n(n+1)}{2} + 5$. The step goes through perfectly: add $k+1$ to both sides and the $5$ comes along untouched. The formula is false at every value of $n$. The step preserves a difference; only the base case can establish that the difference is zero, and that is the whole of its job.
Checking $n = 1, 2, 3$ establishes the claim for $1$, $2$ and $3$. It is evidence for a conjecture and it is not an argument about every $n$; the whole of induction is the step that turns one case into the next.
Where the step's content is. The step is not bookkeeping. Writing the quantity at $k+1$ so that the quantity at $k$ appears inside it is the creative move, and it is usually one of: split off the last term of a sum, factor out one copy of a base, or add and subtract something. If the hypothesis does not appear somewhere in your step, the step is not an inductive step.
Another way: steps
Another way: picture
A row of dominoes. The base case is knocking the first one over; the step is the fact that each one, when it falls, knocks the next. Neither alone does anything: a row of well-spaced dominoes nobody pushes stays standing, and one pushed domino in a badly spaced row knocks nothing.
| Assumes | Good for | |
|---|---|---|
| Ordinary | $P(k)$ | each case built from the one before |
| Strong | $P(n_0), \ldots, P(k)$ | each case built from a smaller one you cannot name in advance |
Strong induction is what you want when the step reaches back an unpredictable distance. 'Every integer above $1$ has a prime factorisation' is the standard example: a composite $k+1$ factors as $ab$ with $a$ and $b$ somewhere between $2$ and $k$, and which values they take is not known in advance, so $P(k)$ alone is no use.
The two are equally powerful — anything provable by one is provable by the other — and the choice is about which makes the step writable. Recurrences in unit 7 need the strong form for the same reason: $a_n$ depends on $a_{n-1}$ and $a_{n-2}$, so one predecessor is not enough.
Assuming the claim for every $n$. 'Assume $P(n)$ holds for all $n$; then $P(n+1)$ follows' is circular. One $k$, particular, fixed.
Skipping the base case. The $+5$ example above is false everywhere and passes the step.
Not using the hypothesis. If the step's algebra never mentions the claim at $k$, you have proved $P(k+1)$ directly — which is fine, but then the induction was unnecessary and the proof should say so.
Starting at the wrong place. $2^n > n^2$ is false at $n = 2, 3, 4$ and true from $n = 5$ on. The base case is $n = 5$, and the step needs $k \ge 5$ to work — a claim whose step holds only above some point is not a claim about all $n$.
Students often feel that assuming $P(k)$ is assuming what is to be proved, and the discomfort is worth taking seriously because it points at the right question. The answer is that the step never claims $P(k)$; it claims the implication $P(k) \Rightarrow P(k+1)$, which is a statement that can be true whether or not $P(k)$ is. That is exactly why the step can go through for a false formula. What rules that out is the base case, and nothing else.
$P(n)$: $1 + 2 + \cdots + n = \tfrac{n(n+1)}{2}$. Base case $n = 1$: the sum is $1$ and the formula gives $1$.
Arithmetic, once.
Assume $P(k)$ for one particular $k \ge 1$: $1 + \cdots + k = \tfrac{k(k+1)}{2}$.
One $k$, written as an equation.
The sum to $k+1$ is $(1 + \cdots + k) + (k+1) = \tfrac{k(k+1)}{2} + (k+1) = \tfrac{(k+1)(k+2)}{2}$ — which is $P(k+1)$. By induction, $P(n)$ for every $n \ge 1$.
Split off the last term: that is the whole trick.
$P(n)$: $2^n > n$ for $n \ge 1$. Base case: $2^1 = 2 > 1$.
Check the base before anything.
Assume $2^k > k$. Then $2^{k+1} = 2 \cdot 2^k > 2k$.
The hypothesis, used once.
And $2k \ge k+1$ because $k \ge 1$. So $2^{k+1} > k+1$. Note that the step needed a fact about $k$ that has nothing to do with the hypothesis — steps usually do, and noticing which part is the hypothesis and which is separate is how you check one.
Hypothesis plus one extra inequality.
Base case: at $n = 1$, $n^2 + n = 2$, which two divides.
Arithmetic first.
Assume $k^2 + k = 2m$ for one particular $k$. At $k+1$: $(k+1)^2 + (k+1) = k^2 + 3k + 2 = (k^2 + k) + (2k + 2)$.
Write the new quantity so the old one appears inside it.
Substituting, that is $2m + 2(k+1) = 2(m + k + 1)$, so two divides it. By induction the claim holds for every $n \ge 1$. Lesson 9 proved the same thing by cases in half the space, which is worth noticing: induction is not always the shortest road, only the one that always exists for claims about every $n$.
Build the induction that $4^n - 1$ is divisible by $3$ for every $n \ge 1$.
This task has no paper form; do it on a device.
Induction proves $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$. What is the sum when $n = 20$?
Answer:
Induction proves $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$. What is the sum when $n = 4$?
Answer:
Here are the four parts of an induction proving that $n^3 - n$ is divisible by six for every $n \ge 1$. Put them in order.
Number the steps in order (write the number in the box):
Induction proves $6^n - 1$ is divisible by $5$ for every $n \ge 1$. What is $\dfrac{6^2 - 1}{5}$?
Answer:
Somebody claims $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2} + 4$, and their inductive step is correct. Fill in both sides for the first three values of $n$.
| $1 + 2 + \cdots + n$ | $\frac{n(n+1)}{2} + 4$ | |
|---|---|---|
| $n = 1$ | ||
| $n = 2$ | ||
| $n = 3$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Build the induction that $3^n - 1$ is divisible by $2$ for every $n \ge 1$.
This task has no paper form; do it on a device.
You can write an induction with a base case, a hypothesis about one k and a step that uses it. Say in your own words why assuming the claim for every n is circular while assuming it for one k is not, and what goes wrong when the base case is skipped. Next: sets, and the operations that build new ones from old.
10. Your turn: prove that $n^2 + n$ is divisible by two for every $n \ge 1$, step 3