Proof by induction
Introduced| English | Meaning |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | A whole number greater than zero, such as 1, 2 or 3. |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | A proof method using a base case and a conditional step from an arbitrary integer case to the next. |
| base case/beɪs keɪs/ | The directly verified first case in the stated integer range of an induction proof. |
| inductive step/ɪnˈdʌktɪv step/ | The proof that the assumed statement at an arbitrary allowed integer k implies the required statement at k+1. |
| inductive hypothesis/ɪnˈdʌktɪv haɪˈpɒθəsɪs/ | The statement temporarily assumed at an arbitrary integer k in order to prove the conditional induction step. |
| divisible/dɪˈvɪzɪbl/ | An integer F is divisible by a non-zero integer m when F=mq for some integer q. |
| conjecture/kənˈdʒektʃə/ | A mathematical statement proposed as true but not yet established by a proof. |
| factorial/fækˈtɔːrɪəl/ | For a positive integer n, the product of the integers from 1 to n, denoted n!; zero factorial is 1. |
A repeatable rule must start somewhere
- Checking a pattern for the first few positive integers 正整数 cannot establish infinitely many cases. Mathematical induction 数学归纳法 joins a first true statement to a rule that reaches every next statement.
- The base case 基础情形 starts the chain. The inductive step 归纳步骤 proves a conditional link for an arbitrary allowed integer, not just the next number in a short table.
The domino picture represents two separate requirements: a starting truth and a link that works at every later position.
A starting truth and a general forward link
The base case P(n₀) and P(k)⇒P(k+1) for every k≥n₀ together establish P(n) for all integers n≥n₀.
State exactly what is being proved
- Write the claim $P(n)$ and its integer range, starting at $n_0$. Check $P(n_0)$ directly, using a given starting condition if appropriate. Then assume $P(k)$ for an arbitrary integer $k\ge n_0$ and use that assumption to derive $P(k+1)$.
- The inductive hypothesis 归纳假设 is temporary and conditional: it does not assume the result for every integer. Conclude that $P(n)$ holds for all integers $n\ge n_0$, because the verified base case and the general link together reach them.
Do not assume the $k+1$ case while trying to prove it. Showing only $P(k+1)\Rightarrow P(k)$ gives the wrong implication. Backward algebra can help you plan, but a proof needs a valid forward argument, or a justified chain of equivalent statements.
The two steps of proof by induction are the base case and the:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Induction needs a base case plus an inductive step from k to k+1.
For a claim stated for every positive integer n starting at 1, which base case is needed?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The base case checks the smallest value, usually n = 1.
If P(1) is true and P(k) implies P(k+1) for every integer k≥1, then P(n) is true for all positive integers n.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The base case is explicitly1, and the forward implication applies to every later step. A proof starting at a different base has a different guaranteed range.
You can prove a result by induction using only the inductive step, without a base case.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Both steps are essential. Without the base case, the chain never starts.
Add the new term in a sum
- For a finite sum, separate the last term of the $k+1$ sum. Replace only its first $k$ terms using the hypothesis, then simplify to the formula with $n=k+1$.
- Show the starting case, the exact hypothesis and the final conclusion. A line that merely quotes the sum formula for $k+1$ has not established the link.
Prove $\sum_{r=1}^{n}r(r+1)=n(n+1)(n+2)/3$ for positive integers $n$.
At $n=1$, both sides equal $2$. Assume the formula holds for $n=k$. Then
This is the required $k+1$ formula, so the result follows for all positive integers by induction.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
10(11)/2 = 55.
Prove by induction that $\sum_{r=1}^{n}(2r-1)^2=n(4n^2-1)/3$ for every positive integer $n$. Show the algebra in the forward step.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $\sum_{r=0}^{n}3^r=(3^{n+1}-1)/2$ for every integer $n\ge0$. State the correct base case and explain the term count.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Expose an integer multiple for divisibility
- To prove an expression is divisible 整除 by a non-zero integer $m$, write it as $m$ times an integer. In the inductive step, isolate the assumed divisible expression and show every remaining term is also a multiple of $m$.
- Both a convenient multiple of the $k$ expression and the difference between consecutive expressions can help. Name the integer multiplier; “it is divisible by inspection” can hide a missing use of the hypothesis.
Let $F_n=10^n-4^n$. At $n=1$, $F_1=6$. Assume $F_k=6q$ for an integer $q$. Then
The bracket is an integer. Thus $6$ divides $F_{k+1}$, and induction proves the result for every positive integer $n$.
Prove by induction that $25^n+7^n-2$ is divisible by $6$ for every positive integer $n$. Identify an integer multiple in the step instead of quoting a pattern from small cases.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $n^3-n$ is divisible by $6$ for every positive integer $n$. Explain why the extra term in the step is divisible by $6$, rather than only by $3$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Use the recurrence to move forward
- A recurrence gives a legal way to pass from $u_k$ to $u_{k+1}$. Check that a proposed closed form has the correct first term, substitute its $k$ version into the recurrence and simplify.
- Do not insert the proposed $k+1$ formula into the recurrence and call it a proof unless you establish a reversible equivalence with the known $k$ formula. The clearest route starts from the given recurrence.
Suppose $u_1=2$ and $u_{n+1}=3u_n+2$. The claim is $u_n=3^n-1$. It is true at $n=1$. Assuming $u_k=3^k-1$,
This proves the claimed closed form for all positive integers, not just the first computed terms $2,8,26$.
A sequence has $u_1=3$ and $u_{n+1}=2u_n+3$. Calculate its first four terms, conjecture a closed formula, and prove it by induction. Separate evidence for the guess from its proof.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Preserve a bound and check denominator signs
- For an inequality involving a recurrence, substitute the hypothesis into an expression whose sign can be controlled. State why its denominator is positive before using it to preserve an inequality.
- Sometimes the needed hypothesis contains two bounds. Prove both survive the step. Once a bound is established for every term, it can justify a later monotonicity argument without assuming the answer.
Let $u_1=1$ and $u_{n+1}=(4u_n+3)/(u_n+2)$. Prove $0<u_n<3$.
The first term satisfies both inequalities. If $0<u_k<3$, numerator and denominator of $u_{k+1}$ are positive. Also,
Thus $0<u_{k+1}<3$. By induction, $0<u_n<3$ for every positive integer $n$. The established bounds then give
so the sequence is increasing. This last deduction uses the proven bound; it does not replace that proof.
Suppose $0<u_1<1$ is given and $u_{n+1}=2u_n/(1+u_n)$. Prove by induction that $0<u_n<1$ for all positive integers. Then use your proved bounds to decide whether the sequence is increasing.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove a matrix-power formula by multiplication
- For powers of one matrix, $M^{k+1}=M^kM$. Substitute the proposed expression for $M^k$, multiply row by column and show every entry has the $k+1$ form.
- A matrix power is not found by raising each entry to a power. Also, a formula checked at $M$ and $M^2$ is only evidence until the arbitrary-$k$ step has been proved.
For $M=\begin{pmatrix}2&1\\0&1\end{pmatrix}$, claim
The $n=1$ case is $M$ itself. Using the $k$ hypothesis,
Therefore the formula holds for all positive integers by induction. The separate $n=0$ case is $M^0=I$, which also fits this formula.
For $M=\begin{pmatrix}2&1\\0&2\end{pmatrix}$, calculate $M^2$, then prove $M^n=\begin{pmatrix}2^n&n2^{n-1}\\0&2^n\end{pmatrix}$ for every positive integer $n$. Show the off-diagonal multiplication explicitly.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Conjecture 猜想 and prove a derivative pattern
- A conjecture is a statement suggested by evidence, not an established theorem. Compute a few derivatives, look for a pattern and express it precisely with its starting value of $n$.
- For an $n$th-derivative formula, differentiate the assumed $k$th derivative once. A correct pattern needs an actual differentiation and simplification in the inductive step.
For $f(x)=xe^{2x}$, the first derivatives are $e^{2x}(2x+1)$, $e^{2x}(4x+4)$ and $e^{2x}(8x+12)$. Conjecture
The first derivative gives the base case. Differentiating the $k$ formula yields
which is the required $k+1$ derivative. Hence the conjecture is true for every positive integer $n$.
In mathematics, a conjecture is:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction).
For $f(x)=x^2e^x$, compute the first three derivatives and conjecture $f^{(n)}(x)$ for $n\ge1$. Prove the formula by induction for all real $x$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
The values n²−n+41 at n=1,2,3 are 41,43,47, all prime. A student conjectures that the expression is prime for every positive integer n. Test n=41 and explain what the result says about limited trials and induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Match the derivative order in the statement
- If the claimed formula is for derivative order $2n$, increasing $n$ by one increases the derivative order by two. The inductive step must differentiate twice. Count the derivative order before starting the algebra.
- Track the alternating sign and the coefficient depending on $n$ separately. A statement about selected even orders is not automatically a statement about every derivative order.
For $f(x)=x\sin x$, claim
At $n=1$, $f''(x)=2\cos x-x\sin x$, as required. Differentiating the assumed $2k$ formula once gives $(-1)^k\{x\cos x+(2k+1)\sin x\}$. A second differentiation gives
completing the step to derivative order $2(k+1)$. The formula therefore holds for all positive integers $n$ by induction.
Prove by induction that for $f(x)=x\sin x$, $f^{(2n-1)}(x)=(-1)^{n-1}\{x\cos x+(2n-1)\sin x\}$ for every positive integer $n$. How many differentiations does one induction step require?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Turn a short trial into a factorial 阶乘 conjecture
- A factorial is $n!=1\cdot2\cdots n$ for a positive integer $n$, with $0!=1$. A few partial sums may suggest a shifted factorial, but the pattern must then survive a general induction step.
- Compute the first terms carefully and look for a simple expression after adding or subtracting a constant. When a question asks for induction, present that proof even if a direct telescoping argument is also available.
For $S_n=\sum_{r=1}^{n}r\,r!$, the first sums are $1,5,23,119$. Adding $1$ suggests $S_n=(n+1)!-1$.
At $n=1$, both sides equal $1$. Assuming the formula for $k$,
Thus the conjecture holds for all positive integers by induction. The identity $r\,r!=(r+1)!-r!$ also explains why the sums telescope, but listing early values alone is not a proof.
Let $S_n=\sum_{r=1}^{n}(r^2+r+1)r!$. Compute $S_1,S_2,S_3$, compare $S_n+1$ with $(n+1)!$, conjecture a formula for $S_n$, and prove it by induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Start at the first value the claim actually covers
- A claim may start at $n=4$ or another stated integer. Prove that starting case and assume $k$ lies in the allowed range; do not silently replace the domain by all positive integers.
- For $2^n\ge n^2$ with $n\ge4$, the base case is $16=16$. Assuming $2^k\ge k^2$ for $k\ge4$, we have $2^{k+1}\ge2k^2\ge(k+1)^2$, because $2k^2-(k+1)^2=(k-1)^2-2>0$ in that range. Hence induction proves the stated claim for all integers $n\ge4$.
The chain proves the stated range beginning at 4. In fact n=3 fails, since 8 is less than 9; the starting point is part of the claim.
Prove $3^n\ge n^2$ by induction for every integer $n\ge2$. Justify the comparison in your inductive step. Does this proof by itself cover $n=1$?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Audit the implication and the conclusion
- Check that the hypothesis is used to prove the next case in the forward direction, with all expressions defined. A checked base and a backward implication alone do not establish the claim for later integers.
- Match the conclusion to the link: $P(k)\Rightarrow P(k+1)$ reaches every later integer, while a link from $k$ to $k+2$ reaches only one parity from a single base. To cover both parities with that link, two starting cases are needed.
The statements $P(n): n\le5$ give a warning. $P(1)$ is true and $P(k+1)\Rightarrow P(k)$ is true for positive integers, yet $P(6)$ is false. The reversed implication cannot replace the required forward step.
Prove the correct starting case, assume an arbitrary allowed k and establish the forward step. Match the conclusion to the reached range; an even-order derivative formula needs two differentiations per step.
Using the formula for the sum of the first n integers, what is the sum when n = 8, and why is the inductive step not enough on its own?
The closed formula gives the sum directly. Induction still has to anchor that formula with a first true case.
What is the sum of the first 8 integers?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
8 times 9 divided by 2 is 36. Other options — 55 (the lesson sum for n = 10); 8 (the value of n).
A proposed proof of n+1<n says: assume k+1<k; adding 1 gives k+2<k+1; therefore the result holds for every positive integer. Identify the error and explain why a valid conditional calculation is insufficient.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Let P(n) be n≤7. A student checks P(1), proves P(k+1) implies P(k), and concludes P(n) for all positive integers. Show why this fails and identify a value of k where the required forward link fails.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
For P(n): n is odd, P(1) is true and P(k) implies P(k+2). What range does this chain cover? Why can it not establish the claim for all positive integers merely by calling the link an inductive step?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.