How induction works: base case, hypothesis and step
A claim about every whole number is an endless list of claims. How can two finite pieces of work, one of which assumes a case it has not proved, settle all of them?
Where you are 3 in Proof by induction
Why this exists
A claim about every whole number is an endless list of claims in disguise. “The sum of the first n positive whole numbers is \displaystyle \frac{n(n+1)}{2}” is really P(1), P(2), P(3), and so on without end, and no amount of checking reaches the end of a list like that. Checking cases is how such a claim is usually found, which is inductive reasoning, and a claim that has held for every case checked so far can still fail at the next one, as why a pattern is not a proof shows. Something other than checking has to finish the job.
What makes it possible is that the cases often come in a chain, each built from the one before. The total of {k+1} terms is the total of k terms with one more added. A collection of {k+1} objects is a collection of k objects with one more thrown in. If something is already known about the case for k, the case for {k+1} may need only a small piece of extra work.
Proof by induction turns that into a method with three named parts, and this lesson is about all three.
- The base case proves the first statement on the list outright.
- The inductive hypothesis is the assumption that one statement, P(k), is true.
- The inductive step is the argument that leads from P(k) to the next statement, {P(k+1)}.
The step is written once and used for ever. Take the claim that the first n even numbers add up to n(n+1). To go from six of them to seven: the six add to 6 \cdot 7 = 42, the seventh even number is 14, and 42 + 14 = 56 = 7 \cdot 8. To go from seven to eight: 56 + 16 = 72 = 8 \cdot 9. These are the same argument with different numbers in it, and so would be the argument from 99 to 100. Nobody can write out all of them, so the argument is written once, with a letter in place of the number:
Read with {k = 6} it is the first calculation, and with {k = 7} it is the second. The hypothesis is the “suppose the first k add to k(k+1)” that this line starts from.
The step is an “if ... then”, and it never says that any statement is true, only that truth gets passed along. A rule for passing truth along produces nothing until something true is put in at the start, and putting it in is all the base case does. It is the only part of the proof that is not conditional. Leaving it out is not a small gap. Let P(n) be the claim {n = n + 1}. Suppose P(k) holds, so {k = k + 1}. Add 1 to both sides and you get {k + 1 = k + 2}, which is {P(k + 1)}. That step is flawless, and the claim is false for every n. Nothing in the step can see that. Only the base case can: P(1) says {1 = 2}.
The base case is usually the shortest part of a proof, and short is not the same as optional. The step is the part where an induction is won or lost. The base case is one statement checked by hand. The step is a proof about an unnamed number, and finding how case {k+1} is tied to case k is where the ideas are. A formula, a divisibility fact, an inequality, a count of objects and a tiling of a board are all proved inside the same three-part frame, and they differ almost only in how the step is found. The commonest of them all, a formula for a running total, has its own section below: induction on a sum formula.
Definition
Let P(n) be a statement about a whole number n, to be proved for every {n \ge n_0}, where n_0 is the first value the claim is about (often 1 or 0). A proof by induction has a base case and an inductive step, and the step starts from the inductive hypothesis.
The base case
The base case is the proof of P(n_0), the very first statement on the list. To write it, replace every n in the claim by n_0. Three things make something a base case.
- It is proved directly. It uses definitions, arithmetic and known facts, and nothing else. No assumption about any other value of n goes into it.
- The first value is where the claim begins. It is often 1 or 0, but the claim decides, not habit. A claim that only starts to be true at {n = 5} has {n_0 = 5}.
- It is a proof, not a sentence. Writing out P(n_0) and moving on proves nothing. For an equation, work out each side separately and show the two agree. For an inequality, work out both sides and compare them. For a statement about divisibility, produce the multiple.
The inductive hypothesis
The inductive hypothesis is the statement P(k) for a number {k \ge n_0} that is arbitrary but fixed. Any value from n_0 on could be the one, and we keep it as a letter, so nothing special about a particular value may be used. It is assumed true at the start of the inductive step, and then used as a given to prove the next case, {P(k+1)}.
- One case. The hypothesis is P(k) alone. It is not P(n) for every n, and it is not {P(k+1)}.
- Arbitrary but fixed. n is the variable inside the statement. k names one chosen value of it, so that P(k) is a single definite claim, even though we have not said which number k is.
- Assumed for the sake of an implication. The job of the step is to prove “if P(k) then {P(k+1)}”. The hypothesis is the “if” half of that sentence.
The inductive step
The inductive step is the proof of the implication
It is carried out by taking an arbitrary whole number {k \ge n_0}, assuming P(k), and reasoning until {P(k+1)} has been reached. Four things are packed into that.
- It proves an implication. What is established is “if P(k), then {P(k+1)}”. The step never says that {P(k+1)} is true, only that it follows from P(k).
- It is written once, for an arbitrary k. The argument may use that k is a whole number with {k \ge n_0}, and nothing else about k. Then it is correct for every such k at once.
- Its first line and its last line are fixed before any work is done. The first is P(k) and the last is {P(k+1)}, each found by putting k or {k+1} in place of n in the claim. Writing both out first is what points the argument at its target. The work then runs from one side of {P(k+1)} to the other, using P(k) on the way. It never begins with {P(k+1)} and simplifies until something true appears, which would assume the goal.
- It uses P(k). If the assumption is never used, the argument has proved {P(k+1)} on its own and the assumption did nothing.
Induction on a sum formula
The commonest induction of all proves a closed formula for a running total, a partial sum:
where a_i is the ith term and f(n) is the proposed formula, such as the formula for an arithmetic series. The three parts take a fixed shape here, and each move has a reason.
- Base case. The sum from n_0 to n_0 has a single term, a_{n_0}. So the base case is the check {a_{n_0} = f(n_0)}, with each side worked out on its own.
- Hypothesis and goal. Write P(k) and {P(k+1)} in full, and on the right of {P(k+1)} simplify {(k+1)+1} to {k+2} and so on, so that the target is in plain sight. Find the term that joins, a_{k+1}, by putting {k+1} in place of i in the term, sign and all.
- Step. Begin with the left side of {P(k+1)} and split off its last term: \sum_{i=n_0}^{k+1} a_i = \left(\sum_{i=n_0}^{k} a_i\right) + a_{k+1}. This is allowed because a sum of {k+1} terms is the sum of the first k of them plus the last one. The bracket is exactly the left side of P(k), so the hypothesis lets it be replaced by f(k). What is left is algebra: show that {f(k) + a_{k+1}} equals {f(k+1)}, the right side of {P(k+1)}.
That last piece of algebra does not involve the sum at all, which leads to the sum rule in the results below.
Intuition
Think of a row of dominoes. The step is the spacing: it says each domino, once it falls, knocks over the next. The base case is the push on the first one. Dominoes that are perfectly spaced still stand there for ever if nobody pushes the first, and a first domino that falls, with gaps after it, takes nothing else with it.
The figure shows the three possibilities. With a base case and a step, the truth starts somewhere and travels all the way. With only a step, every link is sound and nothing is known: the claim may turn out true or false, and the step cannot tell you which. With only a base case, exactly one statement is settled and the rest stay open.
The base case does a second job that is easy to miss: it says where the list starts. The chain of statements has a left end and no right end. The step carries truth to the right for ever, but it cannot carry it to the left, so the base case names the first statement the proof is allowed to claim.
Now the hypothesis. Think of a staircase that goes up for ever. To show you can reach every step you need two things: you can stand on the first step, and from any step you can get to the next one. While working on the second thing you say “suppose I am standing on step k”. You are not claiming that you are. You are describing the situation in which the rule you are about to prove applies.
It is the same move as in any direct proof of an if-then statement. To prove “if it is raining, the pavement is wet”, you begin “suppose it is raining”, and from there you argue that the pavement is wet. Nobody objects that you have assumed rain. The conditional says what follows if it rains, and that is all you set out to show.
The argument would be circular if you assumed what you are trying to prove, which is P(n) for every n. The hypothesis assumes something much smaller, one case, in order to reach a different case. What is actually proved is the implication {P(k) \Rightarrow P(k+1)}, and that implication stands on its own, true or false, whether or not P(k) happens to be true. It is the base case that finally supplies one true statement. With {k = n_0} the implication then delivers {P(n_0 + 1)} by modus ponens, with {k = n_0 + 1} it delivers {P(n_0 + 2)}, and each use is a separate, ordinary application of one fact.
Last, the step. Think of it as a machine. What goes in is whatever makes case k true: an equation, a way of making an amount of postage, a covering of a board. What comes out is the same kind of thing for case {k+1}. The step is the set of instructions inside, and they are correct or not before anything has been fed in.
In nearly every step, case {k+1} is case k with something extra. The figure shows the picture.
The shaded part is what the assumed statement already describes, and only the new piece is left to handle. What “extra” means changes from claim to claim, and four shapes turn up most.
- One more piece. A sum gains a term, a set gains an element, a polygon gains a corner. The hypothesis covers everything before the new piece, and the step adds the new piece in.
- The rule applied once more. A power 7^{k+1} is 7 \cdot 7^k. A term of a sequence is built from the one before it by the same rule each time. The step feeds the hypothesis through the rule.
- A rearrangement. The hypothesis hands over an object, such as a way of paying an amount, and the step reshuffles it into an object for the next case.
- Several smaller copies. The larger case is cut into pieces that are each a smaller case. The hypothesis is used on every piece, and a little extra joins the pieces together. This is the shape of the tiling in Example 17.
In every shape the work is the same. Find case k inside case {k+1}, replace it by what the hypothesis says, and deal with whatever is left over.
Results
The principle of induction
Let P(n) be a statement about a whole number n, and let n_0 be a whole number. If the two lines above the bar hold, the line below it holds.
The first line is the base case and the second is the step. Together they are the whole proof.
What the base case must be, and how many
What it must be. The base case is the claim at the smallest value the proof covers. It is proved directly, without assuming anything about other values. It settles only the values {n \ge n_0}: nothing is learned about {n < n_0}.
How many. The step must be valid at the value where the chain starts, and everywhere after it. If proving {P(k+1)} uses the r statements just before it, namely {P(k), P(k-1), \dots, P(k-r+1)}, then the first r statements are all base cases:
and the step runs for {k \ge n_0 + r - 1}. A step that looks back one statement needs one base case, and a step that looks back two needs two. Looking back further than one is the subject of strong induction.
Where the hypothesis enters
In the step, assume P(k) for an arbitrary fixed {k \ge n_0}, and prove {P(k+1)}. The hypothesis enters wherever the smaller case sits inside the larger. The usual shapes:
- A sum. Split off the last term, as in induction on a sum formula above. What is left is the left side of P(k), which the hypothesis replaces.
- A divisibility statement. The hypothesis says some expression N_k equals d times an integer, say {N_k = dm}. Write N_{k+1} in terms of N_k or of m.
- An inequality. The hypothesis gives {A_k \ge B_k}. Combine it with other true facts to reach {A_{k+1} \ge B_{k+1}}.
- A sequence defined by a rule. Feed the hypothesis about a_k into the rule that produces a_{k+1}.
What a step may use, and where it starts
What it may use. Only three things: that {k \ge n_0} is a whole number, the assumption P(k), and facts already known.
Where it has to start. If the base case is P(n_0), the step has to be valid for every {k \ge n_0}. An argument that needs k to be larger leaves the cases in between to be checked as further base cases.
The sum rule
Suppose the claim is that \sum_{i=n_0}^{n} a_i = f(n) for every {n \ge n_0}. If
then {P(k) \Rightarrow P(k+1)} for every {k \ge n_0}. Together with the base case {f(n_0) = a_{n_0}} this proves the claim. This is induction on a sum formula with the hypothesis already used up: what is left to check is one identity about f and the terms.
The multiple rule
Suppose the claim is that d divides N_n for every {n \ge n_0}. If d divides {N_{k+1} - N_k} for every {k \ge n_0}, then {P(k) \Rightarrow P(k+1)} for every {k \ge n_0}.
In the sum rule and the multiple rule the assumption has been used up by the time the identity is written, so the identity can be checked on its own. The sum rule can also be run backwards to find a formula, which Example 14 does.
Why it is true
Assuming P(k) is legitimate
To prove an implication “A \Rightarrow B” you assume A, reason to B using only A and facts already known, and stop. If that reasoning is correct, then in every situation where A holds, B holds as well, which is exactly what the implication says. Nothing has been assumed about the world, only about the situation the implication talks about. Here A is P(k) and B is {P(k+1)}.
One argument covers every k
The argument for the step used nothing about k except that {k \ge n_0} is a whole number. So every line of it stays true whichever value from n_0 upward is put in place of k, and the implication {P(k) \Rightarrow P(k+1)} is proved for all of them at once. If one line leaned on a further fact, say that k is even, the argument would cover only even k.
Every n is reached
The idea in one line: if the two conditions hold, follow the chain. P(n_0) is true. The step at {k = n_0} turns that into {P(n_0 + 1)}, the step at {k = n_0 + 1} turns that into {P(n_0 + 2)}, and each use of the step moves one statement further along. Any {N \ge n_0} is reached after {N - n_0} uses.
That is convincing but it ends with “and so on”. The tight version asks where a failure could hide, and shows the base case is exactly what removes the last hiding place.
Suppose both conditions hold and yet P(n) is false for some {n \ge n_0}. Among the values where it is false there is a smallest one, because every non-empty collection of whole numbers has a smallest member (this is the well-ordering principle, treated with strong induction). Call it m.
- {m \ne n_0}, because P(n_0) is true by the base case. This is the one place the base case is used.
- So {m > n_0}, which means {m - 1 \ge n_0}, and {m - 1} is a value the claim covers.
- m is the smallest value where the claim fails, so the claim does not fail at {m - 1}: {P(m - 1)} is true.
- The step at {k = m - 1} says {P(m - 1) \Rightarrow P(m)}. With {P(m - 1)} true, P(m) is true.
That contradicts the choice of m, so no failing value exists. Take the base case away and item 1 has nothing behind it: the smallest failure could be n_0 itself, where there is no earlier true statement for the step to use, and nothing contradicts that.
The sum rule
Suppose {f(k+1) - f(k) = a_{k+1}} and suppose P(k), which says \sum_{i=n_0}^{k} a_i = f(k). Then
which is {P(k+1)}. The assumption is used once, in the second line, and the identity does the rest. The sum from n_0 to n_0 is the single term a_{n_0}, so the base case {f(n_0) = a_{n_0}} is exactly P(n_0).
The multiple rule
Suppose {N_k = dm} and {N_{k+1} - N_k = dj} for whole numbers m and j. Then
which is a multiple of d.
Worked examples
All three parts in one proof
Prove that \displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2} for every whole number {n \ge 1}.
SolutionLet P(n) be the claim. It is made for {n \ge 1}, so the first value is {n_0 = 1}. Before doing any work, write the hypothesis and the goal, by putting k and then {k+1} in place of n:
On the right of {P(k+1)}, {(k+1)+1} has been written as {k+2}.
Base case. Replace n by 1. The left side is the sum of the first one positive whole number, which is just 1. The right side is \displaystyle \frac{1(1+1)}{2} = \frac{2}{2} = 1. Each side was worked out on its own, and they agree, so P(1) is true. Nothing was assumed to get here.
Hypothesis. Take a fixed but arbitrary {k \ge 1} and assume P(k). This is not a claim that P(k) is true; it is the “if” of the implication the step proves.
Step. Begin with the left side of {P(k+1)} and split off its last term, which is {k+1}:
The bracket is the left side of P(k), and the hypothesis says it equals \displaystyle \frac{k(k+1)}{2}. Replace it and simplify:
That is the right side of {P(k+1)}. Notice that the work started from one side of {P(k+1)} and arrived at the other. It never started from the claim itself and “simplified” it, which would be assuming what is to be proved.
So {P(k) \Rightarrow P(k+1)} for every {k \ge 1}, and by the principle of induction the claim holds for all {n \ge 1}.
Check. For {n = 4}: 1 + 2 + 3 + 4 = 10 and \displaystyle \frac{4 \cdot 5}{2} = 10. The step itself can be watched at {k = 3}: the hypothesis says {1 + 2 + 3 = 6}, and adding the next term gives {6 + 4 = 10}.
A sum that starts at zero
Prove that for every whole number {n \ge 0},
Here the first case is {n_0 = 0}, so the hypothesis is assumed for {k \ge 0}. Write the statement as \sum_{i=0}^{n} 2^i = 2^{n+1} - 1.
Base case. For {n = 0} the left side is the single term {2^0 = 1}, and the right side is {2^1 - 1 = 1}.
Step. Assume \sum_{i=0}^{k} 2^i = 2^{k+1} - 1 for some fixed {k \ge 0}. The left side of {P(k+1)} is this sum with one more term, 2^{k+1}, added. Use the hypothesis on the part that is already there:
Since {2^{k+2} - 1 = 2^{(k+1)+1} - 1}, this is the right side of {P(k+1)}.
So P(n) holds for every {n \ge 0}.
A step written out in full
Prove that 1^3 + 2^3 + \cdots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2 for every whole number {n \ge 1}.
SolutionCall the statement P(n). Before doing any work, write the two lines the step connects, by putting k and then {k+1} in place of n:
Base case. For {n = 1} the left side is {1^3 = 1} and the right side is \displaystyle \left(\frac{1 \cdot 2}{2}\right)^2 = 1.
Step. Take an arbitrary {k \ge 1} and assume P(k). Begin with the left side of {P(k+1)}. It is the sum up to k with one more term, which is the shape “one more piece”:
The bracket is the left side of P(k), so the hypothesis lets us replace it by \displaystyle \left(\frac{k(k+1)}{2}\right)^2. Then
The second line takes out the common factor {(k+1)^2}, since {(k+1)^3 = (k+1)^2(k+1)}. The third line uses {k^2 + 4k + 4 = (k+2)^2}. The last line is the right side of {P(k+1)}, so the work began at one side of {P(k+1)} and ended at the other.
So {P(k) \Rightarrow P(k+1)} for every {k \ge 1}, and with the base case the claim holds for all {n \ge 1}.
Check. For {n = 4}: {1 + 8 + 27 + 64 = 100}, and {10^2 = 100} where 10 is {4 \cdot 5/2}. The number {n(n+1)/2} is the nth triangular number, which is {1 + 2 + \cdots + n} by Example 1, so the claim says that the sum of the first n cubes is the square of the sum of the first n numbers.
A sum formula with alternating signs
Prove that for every whole number {n \ge 1},
The signs alternate, plus on the odd squares and minus on the even ones, and the factor {(-1)^{i+1}} carries the sign of the ith term: it is +1 when i is odd and -1 when i is even. So the left side is \sum_{i=1}^{n} (-1)^{i+1} i^2. Write the hypothesis and the goal:
The term that joins is found by putting {k+1} in place of i, and its sign comes with it: it is {(-1)^{k+2}(k+1)^2}.
Base case. For {n = 1} the left side is the single term 1, and the right side is \displaystyle {(-1)^2 \cdot \frac{1 \cdot 2}{2} = 1}.
Step. Assume P(k) for some fixed {k \ge 1}. Split off the last term and replace the rest using the hypothesis:
The two signs are opposite, because {(-1)^{k+1} = -(-1)^{k+2}}. So take out the common factor {(-1)^{k+2}(k+1)}:
since \displaystyle {(k+1) - \frac{k}{2} = \frac{2k + 2 - k}{2} = \frac{k+2}{2}}. That is the right side of {P(k+1)}, so the claim holds for every {n \ge 1}.
Check. For {n = 3}: {1 - 4 + 9 = 6} and {(-1)^4 \cdot 3 \cdot 4/2 = 6}. For {n = 4}: {6 - 16 = -10} and {(-1)^5 \cdot 4 \cdot 5/2 = -10}. The formula says that the size of the sum is the triangular number {n(n+1)/2} and that its sign is the sign of the last term. Both facts would be easy to guess from the table of values; the step is what proves them.
Turning “divides” into an equation
Prove that 6 \mid 7^n - 1, read “6 divides 7^n - 1”, for every whole number {n \ge 1}.
SolutionBase case, {n_0 = 1}. {7^1 - 1 = 6 = 6 \cdot 1}. Divisible means equal to 6 times a whole number, and here the whole number is 1. So P(1) is true. (The claim also holds at {n = 0}, since {7^0 - 1 = 0 = 6 \cdot 0}. A claim that is true one value earlier can start one value earlier, as long as the step still works there, and it does.)
Step. The hypothesis is that 6 divides {7^k - 1}. A sentence about dividing is hard to compute with, so restate it as an equation, in the way set out in proving statements about divisibility: there is a whole number m with
The goal is to show {7^{k+1} - 1} is 6 times a whole number. Write 7^{k+1} as {7 \cdot 7^k}, which brings in the smaller case, and replace 7^k using the hypothesis:
Since {7m + 1} is a whole number, 6 divides {7^{k+1} - 1}. This proves {P(k) \Rightarrow P(k+1)}, and the claim follows for all {n \ge 1}.
A multiple, two ways
Prove that 3 divides n^3 + 2n for every whole number {n \ge 1}.
SolutionP(k) says that 3 divides {k^3 + 2k}, and {P(k+1)} says that 3 divides {(k+1)^3 + 2(k+1)}.
Base case. For {n = 1}, {1^3 + 2 \cdot 1 = 3 = 3 \cdot 1}.
Step. Assume P(k), written as an equation: {k^3 + 2k = 3m} for some whole number m. Now expand the expression for {k+1} and look for the expression for k inside it:
The bracket {k^3 + 2k} was replaced by 3m, which is the use of the hypothesis. Since {m + k^2 + k + 1} is a whole number, 3 divides {(k+1)^3 + 2(k+1)}. So {P(k) \Rightarrow P(k+1)} for every {k \ge 1}.
The same step by the multiple rule. Let {N_n = n^3 + 2n}. The expansion above already shows the difference,
which is a multiple of 3 for every k. By the multiple rule the step holds, and nothing needed the letter m. With the base case, 3 divides {n^3 + 2n} for every {n \ge 1}.
A claim that starts late
For which whole numbers {n \ge 1} is {2^n \ge n^2} true? Prove it for every n from the point where it holds for good.
SolutionStart by looking, because the base case is wherever the claim begins to hold for good.
| n | 2^n | n^2 | is 2^n \ge n^2? |
|---|---|---|---|
| 1 | 2 | 1 | yes |
| 2 | 4 | 4 | yes |
| 3 | 8 | 9 | no |
| 4 | 16 | 16 | yes |
| 5 | 32 | 25 | yes |
| 6 | 64 | 36 | yes |
It is true at {n = 1} and 2, false at 3, since {2^3 = 8} is less than {3^2 = 9}, and true again from 4. A base case at {n = 1} would be useless, because the chain would have to pass through the false statement P(3). The claim to prove is {2^n \ge n^2} for {n \ge 4}, with {n_0 = 4}.
Base case. For {n = 4}, {2^4 = 16} and {4^2 = 16}, so {2^4 \ge 4^2}.
Step. Assume {2^k \ge k^2} for some fixed {k \ge 4}. The goal is {2^{k+1} \ge (k+1)^2}. Multiply both sides of the hypothesis by 2, which is positive and so keeps the direction of the inequality:
The hypothesis has now done its work. To finish we need {2k^2 \ge (k+1)^2}, and that is a fact about k alone, not about powers of 2. Subtract:
Because {k \ge 4} we have {k - 1 \ge 3}, so {(k-1)^2 - 2 \ge 9 - 2 > 0}. Hence {2k^2 \ge (k+1)^2}, and joining the two inequalities,
So {2^n \ge n^2} for every {n \ge 4}. The hypothesis did one job, the first inequality; the condition on k did the other, making {(k-1)^2} large enough.
The strict claim {2^n > n^2} starts later still. The table shows it true at 1, false at 2, 3 and 4, and true from 5. The base case {2^5 = 32 > 25 = 5^2} and the same step, with > in its first link, prove it for every {n \ge 5}. The two claims differ only in where truth begins, and that is decided by the base case, not by the step.
Feeding the hypothesis into a rule
A sequence is defined by {a_1 = 1} and {a_{n+1} = 2a_n + 1}. The first few terms are 1, 3, 7, 15, which look like {2^n - 1}. Prove that {a_n = 2^n - 1} for every {n \ge 1}.
SolutionThe pattern in four terms is only a hint. To prove it, use the rule.
Base case. {a_1 = 1} and {2^1 - 1 = 1}.
Step. Assume {a_k = 2^k - 1} for some fixed {k \ge 1}. The only way the sequence reaches a_{k+1} is through its rule, {a_{k+1} = 2a_k + 1}, and that rule takes a_k as its input. The hypothesis tells us what a_k is, so put it in:
That is the formula for {n = k + 1}.
So {a_n = 2^n - 1} for every {n \ge 1}. More on proving a formula against a recursive definition is in checking a closed form by induction and closed form versus recursive form.
When the rule looks back two terms
A sequence has {b_0 = 1}, {b_1 = 4}, and {b_n = 4b_{n-1} - 4b_{n-2}} for {n \ge 2}. Prove that {b_n = (n+1)2^n} for every {n \ge 0}.
SolutionThe rule builds each term from the two before it. So the step will build {P(k+1)} from P(k) and {P(k-1)}, and it can only run when {k - 1 \ge 0}, which is {k \ge 1}. Starting from P(0) alone would need a term b_{-1} that does not exist. Two statements must be settled outright, so there are two base cases.
Base cases. {n = 0}: {(0+1)2^0 = 1 = b_0}. {n = 1}: {(1+1)2^1 = 4 = b_1}. Both are true directly, from the two given values.
Step. Suppose {k \ge 1} and that the formula holds for both k and {k - 1}: {b_k = (k+1)2^k} and {b_{k-1} = k \cdot 2^{k-1}}. Then
which is the formula for {n = k + 1}. So from the two base cases the step reaches {n = 2}, then {n = 3}, and on for ever.
Check. The rule gives {b_2 = 4 \cdot 4 - 4 \cdot 1 = 12}, and the formula gives {(2+1)2^2 = 12}.
With only P(0) checked, nothing would reach P(1): the only step that could produce it is the one at {k = 0}, and that needs b_{-1}. Without P(1) the step at {k = 1} cannot run either, since it needs both P(1) and P(0).
A base case that looks like nothing
Prove that a set with n elements has exactly 2^n subsets, for every {n \ge 0}.
SolutionBase case, {n_0 = 0}. The only set with no elements is the empty set \varnothing. A subset of \varnothing is a set all of whose members lie in \varnothing. Every set is a subset of itself, so \varnothing is a subset of \varnothing, and no set with a member can be a subset of something with none. So \varnothing has exactly one subset. And {2^0 = 1}. So P(0) is true.
It is tempting to wave this case through because it seems to say nothing. It is a real statement, it has a definite answer, and the answer has to be worked out.
Step. Suppose every set with k elements has 2^k subsets, and let S be a set with {k + 1} elements. Pick one element x of S, and let T be S with x removed, so T has k elements. Every subset of S is of exactly one of two kinds.
- It does not contain x. Then it is a subset of T, and by the hypothesis there are 2^k of these.
- It contains x. Take x out and you get a subset of T, and putting x back undoes that, so these subsets match up one for one with the subsets of T. There are 2^k of these too.
In all, S has {2^k + 2^k = 2 \cdot 2^k = 2^{k+1}} subsets, which is {P(k+1)}.
The step works from {k = 0} on: if {S = \{x\}} then {T = \varnothing}, and the two subsets of S are \varnothing and \{x\}. Starting at 0 rather than 1 proves the claim for one more case and costs nothing extra.
The same step, two different base cases
A student claims that {n^2 + n} is odd for every whole number {n \ge 1}, and gives this step. Suppose {k^2 + k} is odd. Then
That is an odd number plus an even number, which is odd. Is the step right? Is the claim?
SolutionThe step is right: the algebra is correct and an odd number plus an even number is odd. So {P(k) \Rightarrow P(k+1)} holds for every k.
The claim is wrong. {n^2 + n = n(n+1)} is a product of two consecutive whole numbers, and one of them is even, so the product is always even.
What is missing is the base case. P(1) says {1^2 + 1 = 2} is odd, and it is not. Since the list has no true statement to start from, the step carries nothing, and in fact every statement on the list is false.
Now run the very same algebra with a different first line. The identity {(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)} also says: if {k^2 + k} is even, so is {(k+1)^2 + (k+1)}, because an even number plus an even number is even. The base case P(1) is now “{1^2 + 1 = 2} is even”, and that is true. The same step, with a true base case, proves that {n^2 + n} is even for every {n \ge 1}.
The step only says what kind of statement gets passed along. The base case decides which statement that is.
When the hypothesis says too little
Prove that for every {n \ge 1},
Call the left side S_n and try the statement as it stands. The hypothesis is {S_k < 1}, and the step needs a bound for
The hypothesis gives \displaystyle {S_{k+1} < 1 + \frac{1}{(k+1)(k+2)}}, but that bound is larger than 1, so it does not give {S_{k+1} < 1}. The trouble is that “{S_k < 1}” does not say how far below 1 the sum is, and the next term could push it over as far as this argument can tell. Knowing only that {S_k < 1}, no amount of algebra will repair that, because the hypothesis does not contain the information.
The remedy is to prove something stronger, with a hypothesis that says exactly where the sum is. Claim Q(n): \displaystyle {S_n = \frac{n}{n+1}}. This is a sum formula, and it implies the original statement, because \displaystyle {\frac{n}{n+1} < 1}.
Base case. \displaystyle {S_1 = \frac{1}{1 \cdot 2} = \frac{1}{2}}, and \displaystyle {\frac{1}{1+1} = \frac{1}{2}}.
Step. Assume \displaystyle {S_k = \frac{k}{k+1}} for some fixed {k \ge 1}. Then
which is {Q(k+1)}, since \displaystyle {\frac{k+1}{(k+1)+1} = \frac{k+1}{k+2}}.
So \displaystyle {S_n = \frac{n}{n+1} < 1} for every {n \ge 1}. A stronger goal is harder to reach, but it also arms the step with a stronger hypothesis, and here that trade is a good one.
A step that takes a piece off as well as adding
Prove that for every whole number {n \ge 1},
Call the left side S_n: it has n fractions, with denominators from {n+1} up to 2n. Write out the two cases the step connects:
Case {k+1} is not case k with a piece added. The first fraction of S_k has dropped off and two new ones have been put on the end. Still, S_k is inside S_{k+1}, and the difference can be written down exactly:
Since 2k+2 is twice {k+1}, the first and last fractions combine:
and so
Base case. \displaystyle S_1 = \frac{1}{2}, which is at least \displaystyle \frac{1}{2}.
Step. Assume {S_k \ge 1/2} for some {k \ge 1}. The fraction {1/((2k+1)(2k+2))} is positive, so
That is {P(k+1)}. So the claim holds for every {n \ge 1}.
Check. For {n = 2} the sum is
and the formula gives {S_1 + 1/(3 \cdot 4)}, which is {1/2 + 1/12}, also {7/12}.
Using the step to find a formula
The first few sums of triangular numbers are 1, {1 + 3 = 4}, {1 + 3 + 6 = 10} and {1 + 3 + 6 + 10 = 20}. Find a formula for \displaystyle \sum_{i=1}^{n} \frac{i(i+1)}{2}, and prove it.
SolutionThe sum rule turns the step into an identity that involves only the formula and the terms. That identity can be used the other way round: ask which f makes it true. Write {a_i = i(i+1)/2}, so the term that joins at the step is {a_{k+1} = (k+1)(k+2)/2}. Adding a quadratic term each time should give a cubic, so try
with numbers p, q, r and s still to be found. The step will hold if {f(k+1) - f(k) = a_{k+1}} for every {k \ge 1}. Using {(k+1)^3 - k^3 = 3k^2 + 3k + 1} and {(k+1)^2 - k^2 = 2k + 1}, the left side is
and the right side is
Two polynomials in k that agree for every {k \ge 1} have the same coefficients, so
The first equation gives p, putting p into the second gives q, and putting both into the third gives r:
The letter s canceled in the difference, so the step says nothing about it. The base case does: f(1) must equal {a_1 = 1}, and {f(1) = p + q + r + s = 1 + s}, so {s = 0}. Therefore
where the second line uses {n^3 + 3n^2 + 2n = n(n+1)(n+2)}.
Proof. The coefficients were chosen so that {f(k+1) - f(k) = a_{k+1}} for every {k \ge 1}, and {f(1) = 1 = a_1}. By the sum rule the claim holds for every {n \ge 1}.
Check. For {n = 3} the formula gives {60 \div 6 = 10}, and {1 + 3 + 6 = 10}. For {n = 4} it gives {120 \div 6 = 20}, and {10 + 10 = 20}. The cubic was a guess about size, not a proof. The proof is the step together with the base case, whatever led to the formula.
A step that rearranges
Stamps come in two values, 3 cents and 5 cents. Prove that every postage amount of 8 cents or more can be made exactly, using only these stamps.
SolutionLet P(n) say that n cents can be made with 3-cent and 5-cent stamps. The claim starts at 8, because 7 cannot be made: using no 5-cent stamp leaves 7 and using one leaves 2, and neither is a multiple of 3. Below 8 the same test shows that 3, 5 and 6 can be made and 1, 2, 4 and 7 cannot, so 7 is the largest amount that cannot be made.
Base case, {n_0 = 8}. {8 = 3 + 5}.
Step. Let {k \ge 8} and assume P(k): there are whole numbers a and b, both at least 0, with {k = 3a + 5b}. That is a stamps of 3 cents and b stamps of 5 cents. There is no formula to simplify here. The step has to turn this payment into a payment of {k+1} cents by exchanging some stamps, and there are two cases, which between them cover every possible payment, since b is either at least 1 or equal to 0.
- {b \ge 1}, so there is at least one 5-cent stamp. Replace one 5-cent stamp by two 3-cent stamps. That swaps 5 cents for 6, so the total goes up by 1. The new payment is worth {3(a+2) + 5(b-1)}, which is {3a + 5b + 1}, and that is {k+1}.
- {b = 0}, so {k = 3a}. Since {k \ge 8}, {3a \ge 8}, which forces {a \ge 3} (for {a = 2} we would have 6). So there are three 3-cent stamps to take away. Replace them, 9 cents, by two 5-cent stamps, 10 cents. The new payment is worth {3(a-3) + 5 \cdot 2}, which is {3a + 1}, and that is {k+1}.
In both cases {k+1} cents can be made, so {P(k) \Rightarrow P(k+1)} for every {k \ge 8}, and with the base case the claim holds for every {n \ge 8}.
The condition {k \ge 8} was used once, in the second case. At {k = 6} the payment is two 3-cent stamps, there is no 5-cent stamp to swap and only two 3-cent stamps to take away, and in fact {P(6)} is true while {P(7)} is false, so no argument could work there. That is the reason the claim starts at 8.
Using the hypothesis on any collection of the right size
Different lines in the plane are in general position if no two of them are parallel and no three of them pass through one point. Prove that n lines in general position cut the plane into \displaystyle \frac{n^2 + n + 2}{2} regions, for every {n \ge 1}.
SolutionWrite \displaystyle {R(n) = \frac{n^2 + n + 2}{2}}.
Base case. One line cuts the plane into 2 regions, and \displaystyle {R(1) = \frac{1 + 1 + 2}{2} = 2}.
Step. The hypothesis is about every collection of k lines in general position: each such collection makes R(k) regions. Now take any {k + 1} lines in general position and set one of them aside. The k lines that remain are still in general position, since taking a line away cannot create a parallel pair or a triple crossing. So the hypothesis applies to them, and they make R(k) regions.
Now lay the set-aside line back down, as in the figure, where {k = 2}.
It is not parallel to any of the others, so it crosses each of the k lines once, and because no three lines meet at a point, it crosses them at k different points. Those k points cut the new line into {k + 1} pieces. Each piece lies inside one existing region, because it meets no other line along the way, and it cuts that region in two, because a region bounded by straight lines is convex and a line across a convex region divides it into exactly two parts. No two pieces lie in the same region, since a line meets a convex region in one unbroken stretch, while any two pieces are separated by a crossing point on an old line. So the new line adds {k + 1} regions:
and {(k+1)^2 + (k+1) + 2 = k^2 + 3k + 4}, so this is \displaystyle \frac{(k+1)^2 + (k+1) + 2}{2}, the formula for {k + 1} lines.
So the formula holds for every {n \ge 1}. The hypothesis had to be a statement about every collection of k lines in general position, not one particular collection, or it could not have been applied to the lines left over after one was set aside.
A step made of smaller copies
An L-shaped tile covers three squares of a board that form a 2 \times 2 block with one square missing, and it may be turned to any of its four positions. Prove that for every {n \ge 1}, if any one square is removed from a 2^n \times 2^n board of squares, the rest of the board can be covered exactly by L-shaped tiles, with no overlap and nothing sticking out.
SolutionA count gives a first check. The board has {4^n - 1} squares left and each tile covers three, so {4^n - 1} has to be a multiple of 3, and it is: 3, 15, 63, and so on. That is only a necessary condition. The step is what shows that a covering exists.
Let P(n) be the claim for boards of side 2^n, with any one square removed.
Base case, {n = 1}. The board is {2 \times 2}. Whichever square is removed, the three that remain form an L, which is exactly one tile.
Step. Assume P(k): every 2^k \times 2^k board with any one square removed can be covered. Take a board of side 2^{k+1} with any one square removed, and cut it into four quadrants, each of side 2^k.
The removed square lies in exactly one quadrant. The four squares at the very center of the board, one in each quadrant, form a {2 \times 2} block. Lay one tile on the three of them that are not in the quadrant holding the removed square, as in the figure. Now look at the four quadrants. Each is a 2^k \times 2^k board with exactly one square taken: in the first quadrant it is the removed square, and in each of the other three it is the square under the new tile. The hypothesis is about every 2^k \times 2^k board with any one square removed, so each of the four can be covered. Together with the center tile, these four coverings cover the large board apart from the removed square, and no square twice.
So {P(k) \Rightarrow P(k+1)} for every {k \ge 1}, and the claim holds for every {n \ge 1}.
The hypothesis was used four times, on four different boards, with the missing square in a different place each time. That is why P(n) says “any one square”. A claim about one fixed position, say the top-left corner, would not reach the quadrants: the squares under the tile sit at three different corners, and the original missing square can be anywhere. The proof also builds a covering, not only proves that one exists: it says how to lay one tile, then do the same on each quadrant.
Boundaries
The base case proves one statement. P(n_0) settles n_0 and nothing else. Verifying P(1) through P(100) settles those hundred statements and only those: what carries the truth past 100 is still a step. Claims that hold for a long run and then fail are the subject of why a pattern is not a proof.
A step proves an implication and nothing more. A correct step does not make the claim true without a start: the step for {n = n + 1} is valid and every statement of it is false. The two parts do different jobs. The base case makes one statement true, and the step passes truth along.
The step has to hold at every k from n_0 on, including the first and the awkward one. If P(k) is true and {P(k+1)} is false for some k, the implication is false there and no argument can prove it. In Example 15, {P(6)} is true and {P(7)} is false, so a step for the 3- and 5-cent stamps can only begin after 7. A claim that is true for a long while and then stops, such as {n < 100}, has such a k too (Exercise 54). And a base case at n_0 pairs only with a step valid for every {k \ge n_0}. If the step needs {k \ge 3} and the base case sits at {n_0 = 1}, the links from 1 to 2 and from 2 to 3 are missing, and the chain breaks. Either the base case moves to 3 (and the claim is only proved from 3), or the early values are checked one by one and P(3) is the last base case before the step takes over.
The hypothesis is the case just below the one being proved, and no other. Assuming {P(k+1)} in order to prove {P(k+1)} is circular. Assuming P(n) for every n is circular too. If proving {P(k+1)} needs {P(k-1)} as well, the number of base cases grows, as in Example 9. If it needs every earlier case, the tool is strong induction, whose hypothesis is {P(n_0), P(n_0+1), \dots, P(k)} together. The hypothesis must also not be used outside its range: {P(k-1)} is available only if {k - 1 \ge n_0}.
The number of base cases follows the step, not the sequence. A recurrence that begins with two given values does not by itself force two base cases: a proof whose step uses only P(k) needs only one (Exercise 24).
k cannot be replaced by a particular number. Writing “let {k = 5}” turns the hypothesis into the single statement P(5), and the step then proves only P(6). The value of k stays a letter throughout.
The hypothesis can be too weak. It says no more than the statement does. In Example 12 the step cannot be finished from the hypothesis the statement supplies, and it can once the statement is strengthened, because a stronger statement carries a stronger hypothesis with it.
A step is not always algebra. Examples 15 and 17 contain no formula. The assumption is whatever the claim is about: an equation, a payment in stamps, a covering of a board. What the step has to do is always to turn the object for case k into the object for case {k+1}.
The cases have to come in a list. Induction covers whole numbers from n_0 upward. It says nothing about values below n_0, and a claim about every real number in an interval has no “next” value to step to, so the method does not apply to it as it stands. Despite the name, induction is deduction: it proves. The guessing from examples that proposes a claim in the first place is inductive reasoning, a different thing.
Where this goes next
The base case, the hypothesis and the step together are proof by induction. The base case is also a direct proof, a short one. Each common kind of claim has its own version of all three. For a running total the base case is one term added up and the step adds one more term, which is induction on a sum formula, set out above. For a multiple the base case is one value shown to be a multiple and the step writes the next expression in terms of the last (induction on a divisibility statement, which leans on proving statements about divisibility). For a comparison the base case is the first value where the larger side has pulled ahead, and the step carries an inequality from one case to the next (induction on an inequality). When a proposed formula has to be checked against a rule that builds the terms, the step is the check that the formula obeys the rule (checking a closed form by induction).
When one earlier case is not enough, the hypothesis widens to all the earlier ones and the number of base cases can grow, and the tool is strong induction. The reason the whole method is sound, that there is no first number that can fail, is the well-ordering principle used in the argument above, which is treated there too. And a step has a mirror in definitions. A recursive formula builds term {k+1} from term k by one rule, in the same way that a step builds the proof for {k+1} from the proof for k. That is why inductions and recursions turn up together so often (closed form versus recursive form).
Exercises
Writing a base case
For Exercises 1 to 6, state the base case P(n_0) for the first value given, and show it is true.
- {1 + 3 + 5 + \cdots + (2n - 1) = n^2}, for {n \ge 1}.
- \displaystyle \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}, for {n \ge 1}. (The symbol \sum means “add up the terms as i runs from 1 to n”.)
- {3^n \ge 2n + 1}, for {n \ge 1}.
- {5^n - 1} is divisible by 4, for {n \ge 1}.
- \displaystyle 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}, for {n \ge 0} and {r \ne 1}.
- A set with n elements has \displaystyle \frac{n(n-1)}{2} subsets with exactly two elements, for {n \ge 2}.
Where does the claim begin?
- The claim {n! > 2^n} is false at {n = 1}, 2 and 3. Find the first value n_0 from which it is true, and show that it is true there. (Here n! means {1 \cdot 2 \cdots n}; see factorial.)
- The claim {2^n > n^3} is true at {n = 1} but false for every n from 2 to 9. Find the base case n_0 for proving it for all {n \ge n_0}, and say why {n = 1} cannot be used.
- Stamps come in 4-cent and 7-cent values. Every amount from 18 cents up can be made exactly, but 17 cents cannot. Write the base case P(18), and show that 17 cannot be the start.
Writing the hypothesis and the goal
- Let P(n) be the statement \sum_{i=1}^{n} i \cdot i! = (n+1)! - 1, for {n \ge 1}. Write P(k) and {P(k+1)}, and say which term of the left side of {P(k+1)} is not in the left side of P(k).
- Let P(n) be the statement “8 divides 9^n + 7”, for {n \ge 1}. Write the hypothesis as an equation involving a whole number m, and say what has to be shown about {9^{k+1} + 7}.
- Let P(n) be the statement {3^n \ge 2^n + n}, for {n \ge 1}. Write P(k) and {P(k+1)}. Then multiply both sides of the hypothesis by 3 and say what each side becomes.
- Let P(n) be the statement \displaystyle \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}. Write the inductive hypothesis P(k), and write the statement {P(k+1)} that has to be proved, simplifying the factors on its right side.
- In the inductive step for the statement in Exercise 13, the left side of {P(k+1)} is split as \left(\sum_{i=1}^{k} i^2\right) + (k+1)^2. Which part is replaced using the hypothesis, and by what?
Induction on a sum formula
- Finish the proof of the statement in Exercise 10: prove the base case and the step.
- Complete the step for Exercise 13. Show that {k(k+1)(2k+1)/6 + (k+1)^2} is equal to {(k+1)(k+2)(2k+3)/6}, and check the base case.
- Prove that \displaystyle \sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1} for every {n \ge 1}.
- Prove that \displaystyle \sum_{i=1}^{n} (3i - 2) = \frac{n(3n-1)}{2} for every {n \ge 1}.
- Prove that \displaystyle \sum_{i=1}^{n} 3^{i-1} = \frac{3^n - 1}{2} for every {n \ge 1}.
- Prove that \sum_{i=1}^{n} i \cdot 2^i = (n-1)\,2^{n+1} + 2 for every {n \ge 1}.
- Let a and d be fixed numbers. Prove the formula for an arithmetic series: the n terms a, {a + d}, {a + 2d}, and so on up to {a + (n-1)d}, add up to \displaystyle \frac{n\bigl(2a + (n-1)d\bigr)}{2}, for every {n \ge 1}. Say which term joins at the step.
- Finish the proof of the statement in Exercise 5: prove that \displaystyle 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1} for every {n \ge 0}, where {r \ne 1} is fixed.
- Use the sum rule, as in Example 14, to find a formula of the form {pn^3 + qn^2 + rn + s} for 1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2, and prove it for every {n \ge 1}.
- The Fibonacci numbers are {F_1 = 1}, {F_2 = 1} and {F_{n+2} = F_{n+1} + F_n}. Prove that {F_1 + F_2 + \cdots + F_n = F_{n+2} - 1} for every {n \ge 1}. How many base cases does your proof need? Explain why one is enough although the sequence has two starting values.
Multiples
- Use the multiple rule to prove that 6 divides {n(n+1)(n+2)} for every {n \ge 1}. You may use the fact that the product of two consecutive whole numbers is even.
- Prove that 5 divides n^5 - n for every {n \ge 1}.
- Prove that 13 divides 4^{2n+1} + 3^{n+2} for every whole number {n \ge 0}. (The first case is {n_0 = 0}.)
- Prove that 5 divides 7^n - 2^n for every {n \ge 1}.
- Prove that {8^n - 1} is divisible by 7 for every {n \ge 1}.
Inequalities
- Finish the proof of the statement in Exercise 12: prove that {3^n \ge 2^n + n} for every {n \ge 1}.
- Prove that {n! > 2^n} for every {n \ge 4}. (Exercise 7 found where this claim begins.)
- Let {x > -1} be a fixed real number. Prove that {(1+x)^n \ge 1 + nx} for every {n \ge 1}.
- Prove that \displaystyle \frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} \le 2 - \frac{1}{n} for every {n \ge 1}.
- Prove that \displaystyle \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} \ge \sqrt{n} for every {n \ge 1}.
Sequences
- A sequence has {a_1 = 2} and {a_{n+1} = 2a_n + 1} for {n \ge 1}. A formula is proposed: {a_n = 3 \cdot 2^{n-1} - 1}. Check the base case, then use the rule to find a_2 and a_3 and confirm that the formula agrees.
- A sequence has {c_1 = 1} and {c_{n+1} = c_n + 6n} for {n \ge 1}. Prove that {c_n = 3n^2 - 3n + 1} for every {n \ge 1}.
- A sequence has {b_1 = 2} and {b_{n+1} = 3b_n - 2}. Prove that {b_n = 3^{n-1} + 1} for every {n \ge 1}.
- A sequence has {d_1 = 1} and {d_{n+1} = 2d_n + n} for {n \ge 1}. Prove that {d_n = 3 \cdot 2^{n-1} - n - 1} for every {n \ge 1}.
- A sequence has {u_0 = 2}, {u_1 = 3} and {u_n = 3u_{n-1} - 2u_{n-2}} for {n \ge 2}. A proof that {u_n = 2^n + 1} for all {n \ge 0} has a step that builds u_{k+1} from u_k and u_{k-1}. How many base cases does it need? Check them all.
Counting and building
- Prove that n different books can be arranged in a row in exactly n! ways, for every {n \ge 1}. Say what the step does with the extra book.
- At a party of n people, everyone shakes hands once with everyone else. Prove that the number of handshakes is \displaystyle \frac{n(n-1)}{2}, for every {n \ge 1}.
- A diagonal of a convex polygon joins two corners that are not neighbors. Prove that a convex polygon with n corners has \displaystyle \frac{n(n-3)}{2} diagonals, for every {n \ge 3}.
- Stamps come in 5-cent and 7-cent values. Prove that every amount of 24 cents or more can be made exactly. (The amount 23 cannot be made, which is why the claim starts at 24.)
A step without a base case
- A student claims that {6^n + 1} is divisible by 5 for every {n \ge 1}. Show that the step works: if {6^k + 1} is divisible by 5, so is {6^{k+1} + 1}. Then show the claim is false.
- Let P(n) be the statement “2n + 1 is even”. Show that {P(k) \Rightarrow P(k+1)} holds for every {k \ge 1}, and then say what this shows about a step that is proved without a base case.
Reasoning
- The step in Example 1 begins “assume P(k)”, although we do not know that P(k) is true. Explain why that is allowed and why it does not make the argument circular.
- A classmate proves a step and says the claim is therefore true for every n. Give a claim whose step can be proved but whose every statement is false, and say what the classmate left out.
- In the sum rule, suppose the identity {f(k+1) - f(k) = a_{k+1}} holds for every {k \ge 1}, but f(1) is not equal to a_1. Is the claim \sum_{i=1}^{n} a_i = f(n) true for any n? Explain.
- A proof checks P(1) and proves {P(k) \Rightarrow P(k+1)} only for {k \ge 2}. Which statements does it actually establish?
- The algebra in a step is valid only when {k \ge 3}, but the base case is checked at {n_0 = 1}. Explain why the proof has a gap, and give two ways to repair it.
- A student checks {P(1), P(2), \dots, P(100)} directly and then proves the step for every {k \ge 100}. Is P(n) proved for all {n \ge 1}? Why might the student have needed so many checks?
- A claim is made for every {n \ge 1}, and its step proves {P(k+1)} from P(k) and {P(k-1)}, for {k \ge 2}. Explain why the single base case P(1) is not enough, and say which base cases are.
- In Example 7 the step needed {2k^2 \ge (k+1)^2}, which is the same as {(k-1)^2 - 2 \ge 0}. For which whole numbers {k \ge 1} is that true? Use your answer to explain why the proof cannot start at {n_0 = 2} or at {n_0 = 3}, although {2^2 \ge 2^2} is true.
- Let P(n) be the claim {n < 100}. Find the one value of k at which {P(k) \Rightarrow P(k+1)} is false, and say what the step “add 1 to both sides of {k < 100}” actually proves.
- In the argument about the smallest false value, which sentence fails if the base case is left out? Explain what could then go wrong.
- Suppose an argument for the step never uses the assumption P(k). What has it shown about {P(k+1)} for each {k \ge n_0}, and what does that say about the claim?
- In Example 16 the hypothesis is applied to the k lines left after one line is set aside. Why is that legitimate? What would go wrong if the hypothesis were only about one particular set of k lines?
- In Example 17 the center tile covers one square in each of the three quadrants that do not hold the removed square. Explain why it has to be placed this way for the hypothesis to apply to all four quadrants.
- The expression {n^2 - n + 41} is a prime number for {n = 1, 2, \dots, 40}. Check the base case {n = 1}. Does it follow by induction that the expression is prime for every {n \ge 1}? Find the smallest n for which it is not prime, and say which implication of the induction breaks.
Answers
- P(1) is {1 = 1^2}. The left side has one term, {2 \cdot 1 - 1 = 1}, and the right side is {1^2 = 1}. True.
- P(1) is \displaystyle 1^2 = \frac{1 \cdot 2 \cdot 3}{6}. The left side is 1 and the right side is \displaystyle \frac{6}{6} = 1. True.
- P(1) is {3^1 \ge 2 \cdot 1 + 1}, that is {3 \ge 3}. True, since equality counts for \ge.
- P(1): {5^1 - 1 = 4 = 4 \cdot 1}, a whole-number multiple of 4. True.
- P(0): the left side is the single term {r^0 = 1}, and the right side is \displaystyle \frac{r^1 - 1}{r - 1} = \frac{r - 1}{r - 1} = 1, which is allowed because {r \ne 1}. True.
- P(2): a set \{a, b\} has exactly one two-element subset, namely itself, and \displaystyle \frac{2 \cdot 1}{2} = 1. True.
- {n_0 = 4}. The first three fail: {1! = 1 < 2}, {2! = 2 < 4}, {3! = 6 < 8}. At 4: {4! = 24 > 16 = 2^4}, so P(4) is true.
- {n_0 = 10}. At 9, {2^9 = 512 < 729 = 9^3}. At 10, {2^{10} = 1024 > 1000 = 10^3}. The base case {n = 1} cannot be used because the chain would have to cross {n = 2} to 9, where the claim is false, so no step could carry it across.
- {18 = 4 + 7 + 7}, so P(18) holds. And 17 cannot be made: {17 - 7a} for {a = 0, 1, 2} gives 17, 10, 3, and none of them is a multiple of 4. So the claim is false at 17 and the list cannot start there.
- P(k) is {\sum_{i=1}^{k} i \cdot i! = (k+1)! - 1}, and {P(k+1)} is {\sum_{i=1}^{k+1} i \cdot i! = (k+2)! - 1}, since {((k+1)+1)! = (k+2)!}. The term that is new on the left of {P(k+1)} is the last one, {(k+1)\cdot(k+1)!}.
- The hypothesis is {9^k + 7 = 8m} for some whole number m, so {9^k = 8m - 7}. What has to be shown is that {9^{k+1} + 7} is 8 times a whole number.
- P(k) is {3^k \ge 2^k + k}, and {P(k+1)} is {3^{k+1} \ge 2^{k+1} + (k+1)}. Multiplying the hypothesis by 3, which is positive and so keeps the direction, gives {3^{k+1} \ge 3 \cdot 2^k + 3k}.
- P(k) is \sum_{i=1}^{k} i^2 = k(k+1)(2k+1)/6, and {P(k+1)} is \sum_{i=1}^{k+1} i^2 = (k+1)(k+2)(2k+3)/6. Put {k+1} for n to get {(k+1)((k+1)+1)(2(k+1)+1)/6}, then simplify {(k+1)+1 = k+2} and {2(k+1)+1 = 2k+3}.
- The bracket \sum_{i=1}^{k} i^2 is the left side of P(k), so it is replaced by \displaystyle \frac{k(k+1)(2k+1)}{6}, which is what the hypothesis says it equals.
- Base case. {1 \cdot 1! = 1} and {2! - 1 = 1}. Step. Assume P(k). The sum up to {k+1} is the sum up to k plus the term {(k+1)(k+1)!}. By the hypothesis that is {(k+1)! - 1 + (k+1)(k+1)!}. Taking out {(k+1)!} gives {(k+1)!\,(k+2) - 1}, which is {(k+2)! - 1}, and that is {P(k+1)}.
- Put everything over 6 and factor out {k+1}. The sum {k(k+1)(2k+1)/6 + (k+1)^2} equals {(k+1)[k(2k+1) + 6(k+1)]/6}, and that equals {(k+1)(2k^2 + 7k + 6)/6}. Since {2k^2 + 7k + 6 = (k+2)(2k+3)}, this is {(k+1)(k+2)(2k+3)/6}, the right side of {P(k+1)}. The base case is {1^2 = 1 = 1 \cdot 2 \cdot 3/6}.
- Base case. {1/(1 \cdot 3) = 1/3} and {1/(2 \cdot 1 + 1) = 1/3}. Step. Assume P(k). The next term is {1/((2k+1)(2k+3))}, so the sum up to {k+1} is {k/(2k+1) + 1/((2k+1)(2k+3))}. Over the common denominator this is {(k(2k+3) + 1)/((2k+1)(2k+3))}. The top is {2k^2 + 3k + 1 = (2k+1)(k+1)}, so the sum is {(k+1)/(2k+3)}, which is {(k+1)/(2(k+1)+1)}, the right side of {P(k+1)}.
- Base case. {3 \cdot 1 - 2 = 1} and {1 \cdot 2/2 = 1}. Step. Assume P(k). The next term is {3(k+1) - 2 = 3k + 1}, so the sum up to {k+1} is {k(3k-1)/2 + 3k + 1}. Over the denominator 2 this is {(3k^2 + 5k + 2)/2}, which factors as {(k+1)(3k+2)/2}. That is {(k+1)(3(k+1)-1)/2}, the right side of {P(k+1)}.
- Base case. {3^0 = 1}, and {(3^1 - 1)/2 = 1}. Step. Adding the next term 3^k to the hypothesis gives {(3^k - 1)/2 + 3^k}. That equals {(3^k - 1 + 2 \cdot 3^k)/2}, which is {(3^{k+1} - 1)/2}, the formula for {k+1}.
- Base case. {1 \cdot 2^1 = 2} and {(1-1) \cdot 2^2 + 2 = 2}. Step. Adding the next term {(k+1)2^{k+1}} to the hypothesis gives {(k-1)2^{k+1} + 2 + (k+1)2^{k+1}}. That equals {2k \cdot 2^{k+1} + 2}, which is {k \cdot 2^{k+2} + 2}. That is {((k+1) - 1)2^{(k+1)+1} + 2}, the formula for {k+1}.
- Base case. For {n = 1} the left side is the single term a, and the right side is {1 \cdot (2a + 0 \cdot d)/2 = a}. Step. The term that joins is the {(k+1)}th, {a + kd}. Assume the sum of the first k terms is {k(2a + (k-1)d)/2}. Adding {a + kd} gives {(2ak + k^2 d - kd + 2a + 2kd)/2}, which is {(2a(k+1) + kd(k+1))/2}, which is {(k+1)(2a + kd)/2}. That is {(k+1)(2a + ((k+1)-1)d)/2}, the formula for {k+1} terms.
- Base case. Exercise 5. Step. Assume {1 + r + \cdots + r^k = (r^{k+1} - 1)/(r - 1)}. Adding the next term r^{k+1} gives {(r^{k+1} - 1)/(r - 1) + r^{k+1}}. Over the denominator {r - 1}, which is not 0 because {r \ne 1}, the top is {r^{k+1} - 1 + r^{k+2} - r^{k+1}}, which is {r^{k+2} - 1}. So the sum is {(r^{k+2} - 1)/(r - 1)}, which is the formula for {k+1}.
- The term that joins is {a_{k+1} = (2k+1)^2}, which is {4k^2 + 4k + 1}. As in Example 14, the difference {f(k+1) - f(k)} is {3p\,k^2 + (3p + 2q)\,k + (p + q + r)}. Matching coefficients with {4k^2 + 4k + 1} gives {3p = 4}, {3p + 2q = 4} and {p + q + r = 1}, so {p = 4/3}, {q = 0} and {r = -1/3}. The base case needs {f(1) = 1}, which forces {s = 0}. The formula is {f(n) = (4n^3 - n)/3}, which equals {n(2n-1)(2n+1)/3}. It satisfies {f(k+1) - f(k) = a_{k+1}} for every k by construction, and {f(1) = 1}, so the sum rule proves it. As a check, for {n = 2} the sum is {1 + 9 = 10}, and the formula gives {30 \div 3 = 10}.
- Base case. {F_1 = 1} and {F_3 - 1 = 2 - 1 = 1}. Step. Assume {F_1 + \cdots + F_k = F_{k+2} - 1}. Adding F_{k+1} gives {F_{k+2} - 1 + F_{k+1} = F_{k+3} - 1}, because {F_{k+3} = F_{k+2} + F_{k+1}}. That is the statement for {k+1}. Base cases needed. One, P(1), because the step uses only P(k), plus the defining rule {F_{k+3} = F_{k+2} + F_{k+1}}, which is always available. The two starting values are used to work out F_3, which is ordinary arithmetic. The number of base cases follows the statement being proved, not the sequence.
- Let {N_n = n(n+1)(n+2)}. The base case is {N_1 = 6}. Taking out the common factor {(k+1)(k+2)}, the difference is {N_{k+1} - N_k = (k+1)(k+2)\bigl((k+3) - k\bigr)}, which is {3(k+1)(k+2)}. The product {(k+1)(k+2)} is of two consecutive whole numbers, so it is even, say {2j}, and the difference is {6j}, a multiple of 6. By the multiple rule the step holds, and with the base case 6 divides N_n for every {n \ge 1}.
- Base case. {1^5 - 1 = 0 = 5 \cdot 0}. Step. The hypothesis gives {k^5 - k = 5m} for some whole number m. Expanding, {(k+1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1}. Subtracting {k+1} leaves {(k^5 - k)} plus {5(k^4 + 2k^3 + 2k^2 + k)}, since the +1 cancels the -1. By the hypothesis that is {5m} plus {5(k^4 + 2k^3 + 2k^2 + k)}, which is 5 times the whole number {m + k^4 + 2k^3 + 2k^2 + k}.
- Base case. {n = 0}: {4^1 + 3^2 = 13}. Step. The hypothesis gives {4^{2k+1} + 3^{k+2} = 13m}, so {4^{2k+1} = 13m - 3^{k+2}}. The next expression is {4^{2k+3} + 3^{k+3}}, which can be written {16 \cdot 4^{2k+1} + 3 \cdot 3^{k+2}}. Put in the hypothesis to get {16(13m - 3^{k+2}) + 3 \cdot 3^{k+2}}. The terms in {3^{k+2}} combine: {-16 \cdot 3^{k+2} + 3 \cdot 3^{k+2} = -13 \cdot 3^{k+2}}. So the whole is {13(16m - 3^{k+2})}, a multiple of 13.
- Base case. {7 - 2 = 5}. Step. The hypothesis gives {7^k - 2^k = 5m} for some whole number m. Then {7^{k+1} - 2^{k+1}} equals {7(7^k - 2^k) + 5 \cdot 2^k}, which is {35m + 5 \cdot 2^k}, which is {5(7m + 2^k)}, a multiple of 5.
- Base case. {n = 1}: {8 - 1 = 7 = 7 \cdot 1}. Step. Suppose {8^k - 1 = 7m}. Then {8^{k+1} - 1 = 8(8^k - 1) + 7}, and this equals {56m + 7 = 7(8m + 1)}, which is divisible by 7.
- Base case. {3^1 = 3} and {2^1 + 1 = 3}, so the inequality holds with equality. Step. By Exercise 12, {3^{k+1} \ge 3 \cdot 2^k + 3k}. Now {(3 \cdot 2^k + 3k) - (2^{k+1} + k + 1)} equals {2^k + 2k - 1}, and for {k \ge 1} this is at least {2 + 2 - 1 = 3}, which is positive. So {3^{k+1}} is at least {3 \cdot 2^k + 3k}, which is larger than {2^{k+1} + (k+1)}, and that is {P(k+1)}.
- Base case. {4! = 24 > 16 = 2^4}. Step. Assume {k! > 2^k} for some {k \ge 4}. Then {(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k}, and since {k + 1 \ge 5 > 2} we get {(k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}}. So {(k+1)! > 2^{k+1}}.
- Base case. {(1+x)^1 = 1 + x}, so equality holds. Step. Assume {(1+x)^k \ge 1 + kx}. Since {x > -1}, the number {1 + x} is positive, so multiplying the hypothesis by it keeps the direction: {(1+x)^{k+1} \ge (1 + kx)(1 + x)}. Multiplying out, {(1 + kx)(1 + x) = 1 + (k+1)x + kx^2}. Because {kx^2 \ge 0}, this is at least {1 + (k+1)x}.
- Base case. {1/1^2 = 1} and {2 - 1/1 = 1}. Step. Assume the sum up to k is at most {2 - 1/k}. Then the sum up to {k+1} is at most {2 - 1/k + 1/(k+1)^2}. The gap between the target {2 - 1/(k+1)} and this bound is {1/k - 1/(k+1) - 1/(k+1)^2}. Over the common denominator {k(k+1)^2} the top is {(k+1)^2 - k(k+1) - k = 1}, so the gap is {1/(k(k+1)^2)}, which is positive. So the sum up to {k+1} is at most {2 - 1/(k+1)}.
- Base case. \displaystyle {\frac{1}{\sqrt{1}} = 1 = \sqrt{1}}. Step. Assume the sum up to k is at least \displaystyle {\sqrt{k}}. Then the sum up to {k+1} is at least \displaystyle {\sqrt{k} + \frac{1}{\sqrt{k+1}}}, and it is enough to show that this is at least \displaystyle {\sqrt{k+1}}. Multiplying by \displaystyle {\sqrt{k+1}}, which is positive, that is the same as \displaystyle {\sqrt{k(k+1)} + 1 \ge k + 1}, or \displaystyle {\sqrt{k(k+1)} \ge k}. This is true because {k(k+1) \ge k^2}.
- P(1): {3 \cdot 2^0 - 1 = 2 = a_1}. Then {a_2 = 2 \cdot 2 + 1 = 5} and the formula gives {3 \cdot 2 - 1 = 5}. And {a_3 = 2 \cdot 5 + 1 = 11} and the formula gives {3 \cdot 4 - 1 = 11}. They agree.
- Base case. {c_1 = 1} and {3 - 3 + 1 = 1}. Step. Assume {c_k = 3k^2 - 3k + 1}. The rule gives {c_{k+1} = c_k + 6k}, which is {3k^2 + 3k + 1}. And {3(k+1)^2 - 3(k+1) + 1} expands to {3k^2 + 3k + 1}, the same.
- Base case. {b_1 = 2 = 3^0 + 1}. Step. Assume {b_k = 3^{k-1} + 1}. The rule gives {b_{k+1} = 3b_k - 2}. Put in the hypothesis: {3(3^{k-1} + 1) - 2}, which is {3^k + 3 - 2}, which is {3^k + 1}, and that is {3^{(k+1)-1} + 1}.
- Base case. {d_1 = 1} and {3 \cdot 2^0 - 1 - 1 = 1}. Step. Assume {d_k = 3 \cdot 2^{k-1} - k - 1}. The rule gives {d_{k+1} = 2d_k + k}, which is {2(3 \cdot 2^{k-1} - k - 1) + k}. That simplifies to {3 \cdot 2^k - k - 2}, and {3 \cdot 2^{(k+1)-1} - (k+1) - 1} is the same, which is {P(k+1)}.
- Two, {n = 0} and {n = 1}, because the step looks back two terms and cannot run at {k = 0}. {2^0 + 1 = 2 = u_0} and {2^1 + 1 = 3 = u_1}. As a check, {u_2 = 3 \cdot 3 - 2 \cdot 2 = 5 = 2^2 + 1}.
- Base case. One book can be arranged in {1 = 1!} way. Step. Assume any k different books can be arranged in k! ways. Take {k+1} books and set one of them, x, aside. The other k can be arranged in k! ways by the hypothesis. For each such arrangement, x can be put in any of {k+1} places: before the first book, between two neighbors, or after the last. Every arrangement of all {k+1} books comes from exactly one arrangement of the others together with one place for x, found by taking x out. So the number of arrangements is {(k+1) \cdot k! = (k+1)!}.
- Base case. 1 person has no one to shake hands with, and {1 \cdot 0/2 = 0}. Step. The hypothesis says any k people make {k(k-1)/2} handshakes. Among {k+1} people, set one person aside. The other k make {k(k-1)/2} handshakes by the hypothesis. The person set aside shakes hands with each of those k, adding k more. The total is {k(k-1)/2 + k = (k^2 + k)/2 = (k+1)k/2}.
- Base case. A triangle has 0 diagonals and {3 \cdot 0/2 = 0}. Step. Assume every convex polygon with k corners has {k(k-3)/2} diagonals, and take one with {k+1} corners, {k \ge 3}. Remove one corner X by cutting off the triangle formed by X and its two neighbors U and V. What is left is a convex polygon with k corners. The diagonals of the large polygon are: the diagonals of the smaller one, which are {k(k-3)/2} by the hypothesis; the segment UV, which was a side of the smaller polygon but is a diagonal of the large one; and the diagonals from X, which go to every corner except X’s two neighbors and X itself, so {k - 2} of them. The total is {k(k-3)/2 + 1 + (k-2)}, which simplifies to {(k^2 - k - 2)/2}. This factors as {(k+1)(k-2)/2}, which is {(k+1)((k+1)-3)/2}.
- Base case. {24 = 2 \cdot 5 + 2 \cdot 7}. Step. Let {k \ge 24} and suppose {k = 5a + 7b} with {a, b \ge 0}. If {b \ge 2}, replace two 7-cent stamps (14 cents) by three 5-cent stamps (15 cents): {5(a+3) + 7(b-2) = k + 1}. If {b \le 1}, then {5a = k - 7b \ge 24 - 7 = 17}, so {a \ge 4}. Replace four 5-cent stamps (20 cents) by three 7-cent stamps (21 cents): {5(a-4) + 7(b+3) = k + 1}. The two cases cover every payment, so {k+1} can be made.
- Step: {6^{k+1} + 1 = 6(6^k + 1) - 5}. If {6^k + 1 = 5m}, then {6^{k+1} + 1 = 30m - 5 = 5(6m - 1)}, so it is divisible by 5. But P(1) says {6 + 1 = 7} is divisible by 5, and it is not. Without a true base case the step carries nothing. In fact the claim is false at every n: 6^n is 1 more than a multiple of 5, so {6^n + 1} is 2 more than one.
- If {2k + 1} is even, then {2(k+1) + 1 = (2k+1) + 2} is an even number plus 2, which is even. So {P(k) \Rightarrow P(k+1)} holds for every k. Yet P(1) says 3 is even, which is false, and {2n + 1} is odd for every n. A correct step shows only that truth would be passed along, not that there is any truth to pass, so the base case cannot be left out.
- Only an implication is being proved, “if P(k) then {P(k+1)}”, and to prove an implication you assume its “if” part and argue to its “then” part. The assumption describes the situation the implication is about, it is not claimed as fact. It is circular only to assume what you are proving, which would be P(n) for every n. What is assumed here is one case, and what is proved is a different case.
- Any claim that is false at every value but passes the step works. For example {n > n + 5}: if {k > k + 5}, adding 1 to both sides gives {k + 1 > k + 6}, so the step holds, yet P(1) says {1 > 6} and every statement is false. The classmate left out the base case.
- No, it is false for every n. Let {g(n) = \sum_{i=1}^{n} a_i - f(n)}. Then {g(1) = a_1 - f(1)} is not zero. And {g(k+1) - g(k)} equals {a_{k+1} - (f(k+1) - f(k))}, which is 0 for every k, so g never changes, and {g(n) = g(1) \ne 0} for all n. The step is valid, but it passes a false statement along, and only the base case could have caught it.
- Only P(1). The link from P(1) to P(2) is the step at {k = 1}, which was not proved. The step at {k = 2} needs P(2) to be true already, and it is not known, so nothing after P(1) is reached.
- The step is not proved for {k = 1} and {k = 2}, so nothing carries truth from P(1) to P(2) or from P(2) to P(3). One repair: move the base case to {n_0 = 3} and prove the claim only for {n \ge 3}. The other: check P(1), P(2) and P(3) directly, and run the step from {k = 3} on.
- Yes, it is complete. P(100) is a base case and the step for {k \ge 100} carries the claim to every {n \ge 100}, while the 99 earlier statements were checked by hand. The many checks were needed only because the step was proved from {k = 100} rather than from {k = 1}: a step valid from {k = 1} would have needed the single base case P(1).
- The step at {k = 2} builds P(3) from P(2) and P(1), and P(2) would still be unknown. The step at {k = 1} would need P(0), which does not exist. So both P(1) and P(2) must be settled outright, and then {k = 2} gives P(3), {k = 3} gives P(4), and so on.
- It is true exactly for {k \ge 3}. For {k \ge 1} the number {k - 1} is at least 0, so {(k-1)^2 \ge 2} holds exactly when {k - 1 \ge 2}: at {k = 2} the value is {(2-1)^2 - 2 = -1}, and at {k = 3} it is {(3-1)^2 - 2 = 2}. Starting at {n_0 = 2} would need the step at {k = 2}, where it fails, and it has to fail there, because P(2) is true ({4 \ge 4}) while P(3) is false ({8 < 9}). Starting at {n_0 = 3}, the step works for every {k \ge 3}, but the base case P(3) is false. So {n_0 = 4} is the first start with a true base case and a step that works for every k from there on.
- The implication is false at k = 99: {99 < 100} is true and {100 < 100} is false. (For {k \le 98} both are true and for {k \ge 100} both are false, so the implication holds there.) Adding 1 to both sides of {k < 100} proves {k + 1 < 101}, which is a weaker statement than {P(k+1)}, which is {k + 1 < 100}.
- The sentence “{m \ne n_0}”, which used P(n_0) being true. Without it the smallest false value could be n_0 itself, and then {m - 1} is not a value the claim covers, so there is no true earlier statement for the step to work from and no contradiction.
- It has shown {P(k+1)} outright for every {k \ge n_0}, so P(n) is true for every {n \ge n_0 + 1} with no chain of cases at all. The claim was never a chain, and induction was not needed for it. (Only P(n_0) may still need a separate check.)
- The hypothesis is about every set of k lines in general position, and the k lines left over form such a set, so it applies to them. If it were only about one particular set, nothing would tell us that the leftover lines are that set, and we could not use it for an arbitrary collection of {k + 1} lines. This is why k must be arbitrary: the hypothesis has to cover whichever collection the step happens to produce.
- The hypothesis applies to a board with exactly one square taken. The quadrant that holds the removed square already has one square taken, so the tile must not touch it, or that board would have two squares taken. Each of the other three quadrants needs exactly one square taken, so the tile must cover exactly one square in each. The only place where one tile can reach all three quadrants is the center, where the {2 \times 2} block has one square in each quadrant, and the tile covers three of the four.
- The base case is true: {1^2 - 1 + 41 = 41}, which is prime. But it does not follow. At {n = 41} the value is {41^2 - 41 + 41 = 41^2 = 1681}, which is not prime, and {n = 41} is the smallest such n. P(40) is true, but the implication {P(40) \Rightarrow P(41)} is false. No argument for the step can exist, because the step would have to hold at every k, and it fails at {k = 40}. A true base case is not enough when there is no step. (The same expression with +n in place of -n is in why a pattern is not a proof.)