← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

2.5 Induction 数学归纳法

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 2.5 章。公式经 MathJax 渲染，自定义宏已注入。

Mathematical induction is a proof technique, not unlike direct proof or proof by contradiction or combinatorial proof.3 You might or might not be familiar with these yet. We will consider these in Chapter 3. In other words, induction is a style of argument we use to convince ourselves and others that a mathematical statement is always true. Many mathematical statements can be proved by simply explaining what they mean. Others are very difficult to prove—in fact, there are relatively simple mathematical statements which nobody yet knows how to prove. To facilitate the discovery of proofs, it is important to be familiar with some standard styles of arguments. Induction is one such style. Let's start with an example:

数学归纳法是一种证明方法，与直接证明、反证法或组合证明并无本质不同。3 你可能熟悉、也可能还不熟悉这些方法。我们将在第 3 章讨论它们。换言之，归纳法是一种论证方式，用来使我们自己以及他人相信某个数学命题恒为真。许多数学命题只需解释其含义即可得证；另一些则极难证明——事实上，存在一些相当简单的数学命题，至今无人知道如何证明。为了便于发现证明，熟悉若干标准的论证风格十分重要。归纳法便是这样一种风格。我们先从一个例子说起：

Stamps 邮票问题

Investigate! 探究！

You need to mail a package, but don't yet know how much postage you will need. You have a large supply of 8-cent stamps and 5-cent stamps. Which amounts of postage can you make exactly using these stamps? Which amounts are impossible to make?

你要寄一个包裹，但还不知道需要多少邮资。你手头有大量 8 分邮票和 5 分邮票。用这些邮票，你能恰好凑出哪些面值的邮资？哪些面值无法凑出？

Perhaps in investigating the problem above you picked some amounts of postage, and then figured out whether you could make that amount using just 8-cent and 5-cent stamps. Perhaps you did this in order: can you make 1 cent of postage? Can you make 2 cents? 3 cents? And so on. If this is what you did, you were actually answering a sequence of questions. We have methods for dealing with sequences. Let's see if that helps.

在探究上面的问题时，你也许先挑出若干邮资金额，再判断只用 8 分和 5 分邮票能否凑出那些金额。也许你是按次序来的：能否凑出 1 分邮资？2 分？3 分？如此继续。如果你是这样做的，你其实是在回答一连串的问题。我们有处理数列的方法，看看这能否帮上忙。

Actually, we will not make a sequence of questions, but rather a sequence of statements. Let $P(n)$ be the statement "you can make $n$ cents of postage using just 8-cent and 5-cent stamps." Since for each value of $n\text{,}$ $P(n)$ is a statement, it is either true or false. So if we form the sequence of statements

其实，我们要构造的不是一连串问题，而是一连串命题。令 $P(n)$ 表示命题「只用 8 分和 5 分邮票，能恰好凑出 $n$ 分邮资」。由于对每个 $n\text{，}$ $P(n)$ 都是一个命题，它非真即假。于是，若我们列出如下命题序列
\begin{equation*} P(1), P(2), P(3), P(4), \ldots \end{equation*}

the sequence will consist of $T$'s (for true) and $F$'s (for false). In our particular case the sequence starts

该序列就由代表真的 $T$ 和代表假的 $F$ 组成。在我们的具体情形中，序列开头是
\begin{equation*} F,F,F,F,T,F,F,T,F,F,T,F,F,T,\ldots \end{equation*}

because $P(1), P(2), P(3), P(4)$ are all false (you cannot make 1, 2, 3, or 4 cents of postage) but $P(5)$ is true (use one 5-cent stamp), and so on.

因为 $P(1), P(2), P(3), P(4)$ 全为假（你无法凑出 1、2、3 或 4 分邮资），而 $P(5)$ 为真（用一张 5 分邮票即可），余可类推。

Let's think a bit about how we could find the value of $P(n)$ for some specific $n$ (the "value" will be either $T$ or $F$). How did we find the value of the $n$th term of a sequence of numbers? How did we find $a_n\text{?}$ There were two ways we could do this: either there was a closed formula for $a_n\text{,}$ so we could plug in $n$ into the formula and get our output value, or we had a recursive definition for the sequence, so we could use the previous terms of the sequence to compute the $n$th term. When dealing with sequences of statements, we could use either of these techniques as well. Maybe there is a way to use $n$ itself to determine whether we can make $n$ cents of postage. That would be something like a closed formula. Or instead we could use the previous terms in the sequence (of statements) to determine whether we can make $n$ cents of postage. That is, if we know the value of $P(n-1)\text{,}$ can we get from that to the value of $P(n)\text{?}$ That would be something like a recursive definition for the sequence. Remember, finding recursive definitions for sequences was often easier than finding closed formulas. The same is true here.

我们来想想，对于一个具体的 $n$，如何求得 $P(n)$ 的「值」（这个值非 $T$ 即 $F$）。我们是怎样求一个数列第 $n$ 项的值的？我们怎样求 $a_n\text{？}$ 有两种途径：要么存在一个关于 $a_n$ 的闭式，把 $n$ 代入公式即得输出值；要么数列有递推定义，可用前面各项算出第 $n$ 项。处理「命题序列」时，这两种方法同样可用。或许存在某种直接利用 $n$ 本身来判断能否凑出 $n$ 分邮资的办法，那便类似于闭式。或者，我们也可以用序列（命题序列）前面的项来判断能否凑出 $n$ 分邮资——也就是说，若已知 $P(n-1)$ 的值，能否由此推出 $P(n)$ 的值？那便类似于该序列的递推定义。请记住：为数列寻找递推定义，往往比为它寻找闭式更容易；这里也是如此。

Suppose I told you that $P(43)$ was true (it is). Can you determine from this fact the value of $P(44)$ (whether it true or false)? Yes you can. Even if we don't know how exactly we made 43 cents out of the 5-cent and 8-cent stamps, we do know that there was some way to do it. What if that way used at least three 5-cent stamps (making 15 cents)? We could replace those three 5-cent stamps with two 8-cent stamps (making 16 cents). The total postage has gone up by 1, so we have a way to make 44 cents, so $P(44)$ is true. Of course, we assumed that we had at least three 5-cent stamps. What if we didn't? Then we must have at least three 8-cent stamps (making 24 cents). If we replace those three 8-cent stamps with five 5-cent stamps (making 25 cents) then again we have bumped up our total by 1 cent so we can make 44 cents, so $P(44)$ is true.

假设我告诉你 $P(43)$ 为真（它确实为真）。你能否据此判定 $P(44)$ 的真假？能。即便我们不知道究竟如何用 5 分和 8 分邮票凑出 43 分，也确知总有某种凑法。如果那种凑法至少用了三张 5 分邮票（共 15 分），我们便可用两张 8 分邮票（共 16 分）替换这三张 5 分邮票，总邮资增加 1 分，于是得到一种凑出 44 分的方法，故 $P(44)$ 为真。当然，我们假定了至少用了三张 5 分邮票。若并非如此呢？那必定至少用了三张 8 分邮票（共 24 分）。若用五张 5 分邮票（共 25 分）替换这三张 8 分邮票，总邮资同样增加 1 分，于是也能凑出 44 分，故 $P(44)$ 仍为真。

Notice that we have not said how to make 44 cents, just that we can, on the basis that we can make 43 cents. How do we know we can make 43 cents? Perhaps because we know we can make $42$ cents, which we know we can do because we know we can make 41 cents, and so on. It's a recursion! As with a recursive definition of a numerical sequence, we must specify our initial value. In this case, the initial value is "$P(1)$ is false." That's not good, since our recurrence relation just says that $P(k+1)$ is true if $P(k)$ is also true. We need to start the process with a true $P(k)$. So instead, we might want to use "$P(31)$ is true" as the initial condition.

注意，我们并没有说明如何凑出 44 分，只是说：基于「能凑出 43 分」这一事实，我们便能凑出 44 分。我们怎么知道能凑出 43 分？也许是因为知道能凑出 $42$ 分，而 $42$ 分能凑出又是因知道能凑出 41 分，如此递推。这是一个递归！与数值序列的递推定义一样，我们必须给定初值。这里初值是「$P(1)$ 为假」，这不好，因为递推关系只说：若 $P(k)$ 为真，则 $P(k+1)$ 为真。我们需要在某个为真的 $P(k)$ 处启动这一过程。因此，不妨取「$P(31)$ 为真」作为初始条件。

Putting this all together we arrive at the following fact: it is possible to (exactly) make any amount of postage greater than 27 cents using just 5-cent and 8-cent stamps.4 This is not claiming that there are no amounts less than 27 cents which can also be made. In other words, $P(k)$ is true for any $k \ge 28$. To prove this, we could do the following:

综合上述，我们得到如下结论：只用 5 分和 8 分邮票，可以（恰好）凑出任何大于 27 分的邮资金额。4 这并不声称低于 27 分就不存在能凑出的金额。换言之，对任意 $k \ge 28$，$P(k)$ 为真。要证明这一点，我们可以这样做：
  1. Demonstrate that $P(28)$ is true.
  2. Prove that if $P(k)$ is true, then $P(k+1)$ is true (for any $k \ge 28$).
  1. 验证 $P(28)$ 为真。
  2. 证明：若 $P(k)$ 为真，则 $P(k+1)$ 为真（对任意 $k \ge 28$）。

Suppose we have done this. Then we know that the 28th term of the sequence above is a $T$ (using step 1, the initial condition or base case), and that every term after the 28th is $T$ also (using step 2, the recursive part or inductive case). Here is what the proof would actually look like.

假设我们已完成这两步。那么我们就知道，上述序列的第 28 项为 $T$（由第 1 步，即初始条件或基础步得出），且第 28 项之后每一项也都是 $T$（由第 2 步，即递推部分或归纳步得出）。下面的证明正是这个样子。

Proof 证明

Let $P(n)$ be the statement "it is possible to make exactly $n$ cents of postage using 5-cent and 8-cent stamps." We will show $P(n)$ is true for all $n \ge 28$.

令 $P(n)$ 表示命题「只用 5 分和 8 分邮票，能恰好凑出 $n$ 分邮资」。我们将证明：对所有 $n \ge 28$，$P(n)$ 为真。

First, we show that $P(28)$ is true: $28 = 4 \cdot 5+ 1\cdot 8\text{,}$ so we can make $28$ cents using four 5-cent stamps and one 8-cent stamp.

首先，证明 $P(28)$ 为真：$28 = 4 \cdot 5+ 1\cdot 8\text{，}$ 故可用四张 5 分邮票和一张 8 分邮票凑出 $28$ 分。

Now suppose $P(k)$ is true for some arbitrary $k \ge 28$. Then it is possible to make $k$ cents using 5-cent and 8-cent stamps. Note that since $k \ge 28\text{,}$ it cannot be that we use less than three 5-cent stamps and less than three 8-cent stamps: using two of each would give only 26 cents. Now if we have made $k$ cents using at least three 5-cent stamps, replace three 5-cent stamps by two 8-cent stamps. This replaces 15 cents of postage with 16 cents, moving from a total of $k$ cents to $k+1$ cents. Thus $P(k+1)$ is true. On the other hand, if we have made $k$ cents using at least three 8-cent stamps, then we can replace three 8-cent stamps with five 5-cent stamps, moving from 24 cents to 25 cents, giving a total of $k+1$ cents of postage. So in this case as well $P(k+1)$ is true.

现设对某个任意的 $k \ge 28$，$P(k)$ 为真。于是可用 5 分和 8 分邮票凑出 $k$ 分。注意，由于 $k \ge 28\text{，}$ 不可能同时少于三张 5 分邮票且少于三张 8 分邮票：各用两张总共才 26 分。若凑出 $k$ 分时至少用了三张 5 分邮票，则用两张 8 分邮票替换这三张 5 分邮票，把 15 分邮资换成 16 分，总额由 $k$ 分增至 $k+1$ 分，故 $P(k+1)$ 为真。另一方面，若凑出 $k$ 分时至少用了三张 8 分邮票，则用五张 5 分邮票替换这三张 8 分邮票，由 24 分变为 25 分，总额达到 $k+1$ 分邮资，故此时 $P(k+1)$ 亦为真。

Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \ge 28$.

因此，由数学归纳法原理，对所有 $n \ge 28$，$P(n)$ 为真。

Formalizing Proofs 形式化证明

What we did in the stamp example above works for many types of problems. Proof by induction is useful when trying to prove statements about all natural numbers, or all natural numbers greater than some fixed first case (like 28 in the example above), and in some other situations too. In particular, induction should be used when there is some way to go from one case to the next – when you can see how to always "do one more."

上面邮票例子中的做法，适用于许多类型的问题。当要证明关于「所有自然数」或「所有大于某个固定初始值（如上例中的 28）的自然数」的命题，以及其他一些情形时，归纳证明都很有用。特别地，只要存在从一种情形过渡到下一种情形的办法——即你能看出怎样总是「再多走一步」——就应使用归纳法。

This is a big idea. Thinking about a problem inductively can give new insight into the problem. For example, to really understand the stamp problem, you should think about how any amount of postage (greater than 28 cents) can be made (this is non-inductive reasoning) and also how the ways in which postage can be made changes as the amount increases (inductive reasoning). When you are asked to provide a proof by induction, you are being asked to think about the problem dynamically; how does increasing $n$ change the problem?

这是一个重要的思想。用归纳的眼光看待问题，能带来新的洞见。例如，要真正理解邮票问题，你既要思考任意（大于 28 分的）邮资金额如何凑出（这是非归纳的推理），也要思考随着金额增大，凑法的变化方式（这是归纳的推理）。当被要求给出归纳证明时，你其实被要求动态地思考问题：$n$ 增大时，问题如何变化？

But there is another side to proofs by induction as well. In mathematics, it is not enough to understand a problem, you must also be able to communicate the problem to others. Like any discipline, mathematics has standard language and style, allowing mathematicians to share their ideas efficiently. Proofs by induction have a certain formal style, and being able to write in this style is important. It allows us to keep our ideas organized and might even help us with formulating a proof.

但归纳证明还有另一面。在数学中，理解问题还不够，你还必须能把问题传达给他人。如同任何学科，数学有标准的语言与文风，使数学家能高效地交流思想。归纳证明具有某种固定的格式，能按这种格式写作十分重要：它帮助我们理清思路，甚至有助于构思证明。

Here is the general structure of a proof by mathematical induction:

下面是数学归纳法证明的一般结构：

Induction Proof Structure 归纳证明结构

Start by saying what the statement is that you want to prove: "Let $P(n)$ be the statement…" To prove that $P(n)$ is true for all $n \ge 0\text{,}$ you must prove two facts:

先说明你要证明的命题是什么：「令 $P(n)$ 表示命题……」要证明对所有 $n \ge 0$，$P(n)$ 为真，必须证明两件事实：
  1. Base case: Prove that $P(0)$ is true. You do this directly. This is often easy.
  2. Inductive case: Prove that $P(k) \imp P(k+1)$ for all $k \ge 0$. That is, prove that for any $k \ge 0$ if $P(k)$ is true, then $P(k+1)$ is true as well. This is the proof of an if … then … statement, so you can assume $P(k)$ is true ($P(k)$ is called the inductive hypothesis). You must then explain why $P(k+1)$ is also true, given that assumption.
  1. 基础步（base case）：直接证明 $P(0)$ 为真。这通常不难。
  2. 归纳步（inductive case）：证明对所有 $k \ge 0$，$P(k) \imp P(k+1)$。即证明：对任意 $k \ge 0$，若 $P(k)$ 为真，则 $P(k+1)$ 亦为真。这是一个「若……则……」命题的证明，因此你可以假定 $P(k)$ 为真（$P(k)$ 称为归纳假设，inductive hypothesis）。然后，在此基础上说明为何 $P(k+1)$ 也为真。

Assuming you are successful on both parts above, you can conclude, "Therefore by the principle of mathematical induction, the statement $P(n)$ is true for all $n \ge 0$."

若上述两部分都成功完成，便可作结：「因此，由数学归纳法原理，命题 $P(n)$ 对所有 $n \ge 0$ 为真。」

Sometimes the statement $P(n)$ will only be true for values of $n \ge 4\text{,}$ for example, or some other value. In such cases, replace all the 0's above with 4's (or the other value).

有时命题 $P(n)$ 只对 $n \ge 4$（或其他某个值）成立。这时，把上面所有的 0 换成 4（或那个值）即可。

The other advantage of formalizing inductive proofs is it allows us to verify that the logic behind this style of argument is valid. Why does induction work? Think of a row of dominoes set up standing on their edges. We want to argue that in a minute, all the dominoes will have fallen down. For this to happen, you will need to push the first domino. That is the base case. It will also have to be that the dominoes are close enough together that when any particular domino falls, it will cause the next domino to fall. That is the inductive case. If both of these conditions are met, you push the first domino over and each domino will cause the next to fall, then all the dominoes will fall.

把归纳证明形式化，还有一个好处：它让我们能验证这种论证方式背后的逻辑是成立的。归纳法为何有效？想象一排竖立着的多米诺骨牌。我们想论证：一分钟后，所有骨牌都会倒下。为此，你必须推倒第一张牌——这就是基础步。还必须满足：骨牌之间足够靠近，使得任意一张倒下时，都会带倒下一张——这就是归纳步。若这两个条件都满足，你推倒第一张，每张又带倒后一张，那么所有骨牌都会倒下。

Induction is powerful! Think how much easier it is to knock over dominoes when you don't have to push over each domino yourself. You just start the chain reaction, and the rely on the relative nearness of the dominoes to take care of the rest.

归纳法很强大！想想看，不必亲手推倒每一张骨牌，只需启动连锁反应，余下的交给骨牌间的相互靠近即可，多么省力。

Think about our study of sequences. It is easier to find recursive definitions for sequences than closed formulas. Going from one case to the next is easier than going directly to a particular case. That is what is so great about induction. Instead of going directly to the (arbitrary) case for $n\text{,}$ we just need to say how to get from one case to the next.

回想我们对数列的研究：为数列寻找递推定义，比为它寻找闭式更容易；从一种情形走到下一种，比直接跳到某个特定情形更容易。这正是归纳法的精妙之处。我们无需直接处理（任意的）$n$ 这一情形，只要说明如何从一种情形走到下一种即可。

When you are asked to prove a statement by mathematical induction, you should first think about why the statement is true, using inductive reasoning. Explain why induction is the right thing to do, and roughly why the inductive case will work. Then, sit down and write out a careful, formal proof using the structure above.

当被要求用归纳法证明一个命题时，你应先借助归纳推理，想清楚该命题为何为真；说明为何归纳法是恰当的，并大致说明归纳步为何成立。然后坐下来，按上面的结构写出一份严谨、形式化的证明。

Examples 示例

Here are some examples of proof by mathematical induction.

下面是几个数学归纳法证明的例子。

Example 1

示例 1

Prove for each natural number $n \ge 1$ that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$.

证明：对每个自然数 $n \ge 1$，都有 $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$。

Answer

解答（思路）

First, let's think inductively about this equation. In fact, we know this is true for other reasons (reverse and add comes to mind). But why might induction be applicable? The left-hand side adds up the numbers from 1 to $n$. If we know how to do that, adding just one more term ($n+1$) would not be that hard. For example, if $n = 100\text{,}$ suppose we know that the sum of the first 100 numbers is $5050$ (so $1 + 2 + 3 + \cdots + 100 = 5050\text{,}$ which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have $1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151$. In fact, it would always be easy to add just one more term. This is why we should use induction.

先让我们用归纳的眼光看这个等式。事实上，我们凭别的理由也知道它成立（比如「倒序相加法」）。但为何归纳法可能适用？等号左边是把从 1 到 $n$ 的数相加。若我们已知怎么求和，再多加一项（$n+1$）并不难。例如，若 $n = 100\text{，}$ 假设已知前 100 个数之和为 $5050$（即 $1 + 2 + 3 + \cdots + 100 = 5050\text{，}$ 这成立）。现在要求前 101 个数之和，显然更合理的做法是在 5050 上加 101，而不是把整个和重新算一遍。于是有 $1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151$。事实上，每次只多加一项总是容易的。这正是我们该用归纳法的原因。

Now the formal proof:

下面给出形式化证明：

Proof

证明

Let $P(n)$ be the statement $1 + 2 + 3 + \cdots + n = \frac{n(n+2)}{2}$. We will show that $P(n)$ is true for all natural numbers $n \ge 1$.

令 $P(n)$ 为命题 $1 + 2 + 3 + \cdots + n = \frac{n(n+2)}{2}$。我们将证明：对所有自然数 $n \ge 1$，$P(n)$ 为真。

Base case: $P(1)$ is the statement $1 = \frac{1(1+1)}{2}$ which is clearly true.

基础步：$P(1)$ 即 $1 = \frac{1(1+1)}{2}$，显然为真。

Inductive case: Let $k \ge 1$ be a natural number. Assume (for induction) that $P(k)$ is true. That means $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$. We will prove that $P(k+1)$ is true as well. That is, we must prove that $1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$. To prove this equation, start by adding $k+1$ to both sides of the inductive hypothesis:

归纳步：设 $k \ge 1$ 为自然数。为归纳之故，假设 $P(k)$ 为真，即 $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$。我们将证明 $P(k+1)$ 亦为真，也就是要证明 $1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$。为证此式，先在归纳假设两边同加 $k+1$：
\begin{equation*} 1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1). \end{equation*}

Now, simplifying the right side we get:

化简右边，得：
\begin{align*} \frac{k(k+1)}{2} + k+1 & = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\ & = \frac{k(k+1) + 2(k+1)}{2}\\ & = \frac{(k+2)(k+1)}{2}. \end{align*}

Thus $P(k+1)$ is true, so by the principle of mathematical induction $P(n)$ is true for all natural numbers $n \ge 1$.

故 $P(k+1)$ 为真，于是依数学归纳法原理，对所有自然数 $n \ge 1$，$P(n)$ 为真。

Note that in the part of the proof in which we proved $P(k+1)$ from $P(k)\text{,}$ we used the equation $P(k)$. This was the inductive hypothesis. Seeing how to use the inductive hypotheses is usually straight forward when proving a fact about a sum like this. In other proofs, it can be less obvious where it fits in.

注意，在由 $P(k)$ 推出 $P(k+1)$ 的那部分证明中，我们用到了等式 $P(k)$——这就是归纳假设。在证明关于求和的这类事实时，如何运用归纳假设通常一目了然；而在其他证明中，它该用在何处则不那么明显。

Example 2

示例 2

Prove that for all $n \in \N\text{,}$ $6^n - 1$ is a multiple of 5.

证明：对所有 $n \in \N\text{，}$ $6^n - 1$ 都是 5 的倍数。

Solution

解答

Again, start by understanding the dynamics of the problem. What does increasing $n$ do? Let's try with a few examples. If $n = 1\text{,}$ then yes, $6^1 - 1 = 5$ is a multiple of 5. What does incrementing $n$ to 2 look like? We get $6^2 - 1 = 35\text{,}$ which again is a multiple of 5. Next, $n = 3\text{:}$ but instead of just finding $6^3 - 1\text{,}$ what did the increase in $n$ do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number which is one more than a multiple of 5 by 6 (because $6^2 - 1$ is a multiple of 5, so $6^2$ is one more than a multiple of 5). What do numbers which are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? Depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

还是先理解问题的动态。把 $n$ 增大，会发生什么？试几个例子。若 $n = 1\text{，}$ 有 $6^1 - 1 = 5$，是 5 的倍数。把 $n$ 增到 2 呢？得到 $6^2 - 1 = 35\text{，}$ 仍是 5 的倍数。再看 $n = 3\text{：}$ 我们不只是去算 $6^3 - 1\text{，}$ 而要问：$n$ 的增大带来了什么？我们仍要减 1，但在此之前先多乘了一个 6。换个角度看，我们是在用一个「比 5 的某个倍数多 1」的数去乘 6（因为 $6^2 - 1$ 是 5 的倍数，故 $6^2$ 比 5 的某个倍数多 1）。比 5 的倍数多 1 的数长什么样？其末位必为 1 或 6。这样的数乘 6 会怎样？视具体数值而定，但无论如何，新数的末位必为 6；再减 1，末位变为 5，于是成为 5 的倍数。

The point is, every time we multiply by just one more six, we still get a number with last digit 6, so subtracting 1 gives us a multiple of 5. Now the formal proof:

关键在于：每多乘一个 6，得到的数的末位仍是 6，故减 1 后便得 5 的倍数。下面给出形式化证明：

Proof 证明

Let $P(n)$ be the statement, "$6^n - 1$ is a multiple of 5." We will prove that $P(n)$ is true for all $n \in \N$.

令 $P(n)$ 为命题「$6^n - 1$ 是 5 的倍数」。我们将证明：对所有 $n \in \N$，$P(n)$ 为真。

Base case: $P(0)$ is true: $6^0 -1 = 0$ which is a multiple of 5.

基础步：$P(0)$ 为真：$6^0 -1 = 0$，而 0 是 5 的倍数。

Inductive case: Let $k$ be an arbitrary natural number. Assume, for induction, that $P(k)$ is true. That is, $6^k - 1$ is a multiple of $5$. Then $6^k - 1 = 5j$ for some integer $j$. This means that $6^k = 5j + 1$. Multiply both sides by $6\text{:}$

归纳步：设 $k$ 为任意自然数。为归纳之故，假设 $P(k)$ 为真，即 $6^k - 1$ 是 $5$ 的倍数。于是存在整数 $j$ 使 $6^k - 1 = 5j$，即 $6^k = 5j + 1$。两边同乘 $6\text{：}$
\begin{equation*} 6^{k+1} = 6(5j+1) = 30j + 6. \end{equation*}

But we want to know about $6^{k+1} - 1\text{,}$ so subtract 1 from both sides:

但我们关心的是 $6^{k+1} - 1\text{，}$ 故两边同减 1：
\begin{equation*} 6^{k+1} - 1 = 30j + 5. \end{equation*}

Of course $30j+5 = 5(6j+1)\text{,}$ so is a multiple of 5.

显然 $30j+5 = 5(6j+1)\text{，}$ 故它是 5 的倍数。

Therefore $6^{k+1} - 1$ is a multiple of 5, or in other words, $P(k+1)$ is true. Thus, by the principle of mathematical induction $P(n)$ is true for all $n \in \N$.

因此 $6^{k+1} - 1$ 是 5 的倍数，换言之 $P(k+1)$ 为真。于是依数学归纳法原理，对所有 $n \in \N$，$P(n)$ 为真。

We had to be a little bit clever (i.e., use some algebra) to locate the $6^k - 1$ inside of $6^{k+1} - 1$ before we could apply the inductive hypothesis. This is what can make inductive proofs challenging.

在套用归纳假设之前，我们必须动点脑筋（即用一点代数），在 $6^{k+1} - 1$ 中「分离出」$6^k - 1$。这正是归纳证明有时颇具挑战的原因。

In the two examples above, we started with $n = 1$ or $n = 0$. We can start later if we need to.

在上面两个例子中，我们分别从 $n = 1$ 与 $n = 0$ 起步；若有需要，也可以从更后面开始。

Example 3

示例 3

Prove that $n^2 < 2^n$ for all integers $n \ge 5$.

证明：对所有整数 $n \ge 5$，都有 $n^2 < 2^n$。

Solution

解答

First, the idea of the argument. What happens when we increase $n$ by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have $(n+1)^2 - n^2$. This factors:

先说论证的思路。把 $n$ 加 1，会发生什么？左边，平方的底数增大，进入下一个平方数；右边，2 的幂次升高，意味着数值翻倍。于是问题是：一个数翻倍，与平方数增大到下一个，二者如何比较？想想两个相邻平方数之差是什么样子。我们有 $(n+1)^2 - n^2$，可分解如下：
\begin{equation*} (n+1)^2 - n^2 = (n+1-n)(n+1+n) = 2n+1. \end{equation*}

But doubling the right-hand side increases it by $2^n\text{,}$ since $2^{n+1} = 2^n + 2^n$. When $n$ is large enough, $2^n > 2n + 1$.

但右边翻倍时，增量是 $2^n\text{，}$ 因为 $2^{n+1} = 2^n + 2^n$。当 $n$ 足够大时，$2^n > 2n + 1$。

What we are saying here is that each time $n$ increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when $n = 5$), it will never catch up.

我们的意思是：每增大一次 $n$，左边的增量都小于右边的增量。因此，只要左边起步时更小（正如 $n = 5$ 时那样），它就永远追不上右边。

Now the formal proof:

下面给出形式化证明：

Let $P(n)$ be the statement $n^2 < 2^n$. We will prove $P(n)$ is true for all integers $n \ge 5$.

令 $P(n)$ 为命题 $n^2 < 2^n$。我们将证明：对所有整数 $n \ge 5$，$P(n)$ 为真。

Base case: $P(5)$ is the statement $5^2 < 2^5$. Since $5^2 = 25$ and $2^5 = 32\text{,}$ we see that $P(5)$ is indeed true.

基础步：$P(5)$ 即 $5^2 < 2^5$。因为 $5^2 = 25$ 且 $2^5 = 32\text{，}$ 可见 $P(5)$ 确为真。

Inductive case: Let $k \ge 5$ be an arbitrary integer. Assume, for induction, that $P(k)$ is true. That is, assume $k^2 < 2^k$. We will prove that $P(k+1)$ is true, i.e., $(k+1)^2 < 2^{k+1}$. To prove such an inequality, start with the left-hand side and work towards the right-hand side:

归纳步：设 $k \ge 5$ 为任意整数。为归纳之故，假设 $P(k)$ 为真，即假设 $k^2 < 2^k$。我们将证明 $P(k+1)$ 为真，亦即 $(k+1)^2 < 2^{k+1}$。证明这类不等式，可从左边出发，逐步推向右边：
\begin{align*} (k+1)^2 & = k^2 + 2k + 1 &\\ & < 2^k + 2k + 1 & \ldots\text{by the inductive hypothesis.}\\ & < 2^k + 2^k & \ldots\text{ since } 2k + 1 < 2^k \text{ for }k \ge 5.\\ & = 2^{k+1}. & \end{align*}

Following the equalities and inequalities through, we get $(k+1)^2 < 2^{k+1}\text{,}$ in other words, $P(k+1)$. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \ge 5$.

沿等式与不等式一路推下，得到 $(k+1)^2 < 2^{k+1}\text{，}$ 即 $P(k+1)$。故依数学归纳法原理，对所有 $n \ge 5$，$P(n)$ 为真。

$\square$

（证毕）

The previous example might remind you of the racetrack principle from calculus, which says that if $f(a) < g(a)\text{,}$ “and” $f'(x) < g'(x)$ for $x > a\text{,}$ then $f(x) < g(x)$ for $x > a$. Same idea: the larger function is increasing at a faster rate than the smaller function, so the larger function will stay larger. In discrete math, we don't have derivatives, so we look at differences. Thus induction is the way to go.

上一个例子也许令你想起微积分中的「赛道原理」：若 $f(a) < g(a)\text{，}$ 且对 $x > a$ 有 $f'(x) < g'(x)$，则对 $x > a$ 有 $f(x) < g(x)$。思路相同：较大的函数增长得比较小的函数快，因此较大的函数会一直保持领先。在离散数学中没有导数，于是我们考察差值。这正是归纳法大显身手之处。

Warning: 注意（警示）

With great power, comes great responsibility. Induction isn't magic. It seems very powerful to be able to assume $P(k)$ is true. After all, we are trying to prove $P(n)$ is true and the only difference is in the variable: $k$ vs. $n$. Are we assuming that what we want to prove is true? Not really. We assume $P(k)$ is true only for the sake of proving that $P(k+1)$ is true.

能力越大，责任越大。归纳法并非魔法。能够假定 $P(k)$ 为真，看似威力无穷。毕竟我们要证的是 $P(n)$ 为真，而二者唯一的差别只在变量：$k$ 与 $n$。难道我们是在假定想要证明的结论成立吗？并非如此。我们假定 $P(k)$ 为真，纯粹是为了证明 $P(k+1)$ 为真。

Still you might start to believe that you can prove anything with induction. Consider this incorrect "proof" that every Canadian has the same eye color: Let $P(n)$ be the statement that any $n$ Canadians have the same eye color. $P(1)$ is true, since everyone has the same eye color as themselves. Now assume $P(k)$ is true. That is, assume that in any group of $k$ Canadians, everyone has the same eye color. Now consider an arbitrary group of $k+1$ Canadians. The first $k$ of these must all have the same eye color, since $P(k)$ is true. Also, the last $k$ of these must have the same eye color, since $P(k)$ is true. So in fact, everyone the group must have the same eye color. Thus $P(k+1)$ is true. So by the principle of mathematical induction, $P(n)$ is true for all $n$.

尽管如此，你也许会以为用归纳法可以证明任何事。请看下面这个错误的「证明」：所有加拿大人都有相同颜色的眼睛。令 $P(n)$ 为命题「任意 $n$ 个加拿大人眼睛颜色相同」。$P(1)$ 为真，因为每个人与自己的眼睛颜色当然相同。现假设 $P(k)$ 为真，即在任意 $k$ 个加拿大人中，所有人眼睛颜色相同。考虑任意 $k+1$ 个加拿大人组成的一群人。其中前 $k$ 个人必眼睛同色（因 $P(k)$ 为真）；其中后 $k$ 个人也必眼睛同色（因 $P(k)$ 为真）。于是实际上这群人里所有人眼睛颜色都相同，故 $P(k+1)$ 为真。依数学归纳法原理，对所有 $n$，$P(n)$ 为真。

Clearly something went wrong. The problem is that the proof that $P(k)$ implies $P(k+1)$ assumes that $k \ge 2$. We have only shown $P(1)$ is true. In fact, $P(2)$ is false.

显然哪里出了错。问题出在「由 $P(k)$ 推出 $P(k+1)$」的证明隐含假定了 $k \ge 2$。而我们只证明了 $P(1)$ 为真；事实上，$P(2)$ 为假。

Strong Induction 强归纳法

Investigate! 探究！

Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square). Obviously it is possible to cut the square into 4 squares. You can also cut it into 9 squares. It turns out you can cut the square into 7 squares (although not all the same size). What other numbers of squares could you end up with?

取一张正方形纸。你想把它剪成若干小正方形，且不浪费（剪完后每一片都必须是正方形）。显然可以剪成 4 个正方形，也可以剪成 9 个。其实还能剪成 7 个（尽管大小不一）。你最终可能得到多少个正方形的纸片？

Sometimes, to prove that $P(k+1)$ is true, it would be helpful to know that $P(k)$ and $P(k-1)$ and $P(k-2)$ are all true. Consider the following puzzle:

有时，为了证明 $P(k+1)$ 为真，若能知道 $P(k)$、$P(k-1)$ 与 $P(k-2)$ 同时为真，会很有帮助。考虑下面这个谜题：

Puzzle. You have a rectangular chocolate bar, made up of $n$ identical squares of chocolate. You can take such a bar and break it along any row or column. How many times will you have to break the bar to reduce it to $n$ single chocolate squares?

谜题。 你有一块长方形巧克力，由 $n$ 个相同的正方形小块组成。你可以沿任意一行或一列把它掰开。要把它分成 $n$ 个单独的小方块，需要掰多少次？

At first, this question might seem impossible. Perhaps I meant to ask for the smallest number of breaks needed? Let's investigate.

初看这问题似乎无从下手。也许我本该问：所需的最少掰次数是多少？我们来探究一番。

Start with some small cases. If $n=2\text{,}$ you must have a $1\times 2$ rectangle, which can be reduced to single pieces in one break. With $n=3\text{,}$ we must have a $1\times 3$ bar, which requires two breaks: the first break creates a single square and a $1\times 2$ bar, which we know takes one (more) break.

从较小的情形入手。若 $n=2\text{，}$ 必是 $1\times 2$ 的长方形，掰一次即可分成单块。若 $n=3\text{，}$ 必是 $1\times 3$ 的长条，需要掰两次：第一次掰出一个单块和一个 $1\times 2$ 长条，而后者我们已知还需掰一次。

What about $n=4\text{?}$ Now we could have a $2\times 2$ bar, or a $1 \times 4$ bar. In the first case, break the bar into two $2\times 2$ bars, each which require one more break (that's a total of three breaks required). If we started with a $1 \times 4$ bar, we have choices for our first break. We could break the bar in half, creating two $1\times 2$ bars, or we could break off a single square, leaving a $1\times 3$ bar. But either way, we still need two more breaks, giving a total of three.

若 $n=4\text{？}$ 这时可能是 $2\times 2$ 方块，也可能是 $1 \times 4$ 长条。前一种情形：把方块掰成两个 $2\times 2$，每个还需再掰一次（共需三次）。若一开始是 $1 \times 4$ 长条，第一次掰法有多种：可以从中间掰断，得到两个 $1\times 2$；也可以掰下一个单块，剩下一个 $1\times 3$。但无论哪种，都还需再掰两次，总计仍是三次。

It is starting to look like no matter how we break the bar (and no matter how the $n$ squares are arranged into a rectangle), we will always have the same number of breaks required. It also looks like that number is one less than $n\text{:}$

看来，无论怎样掰（也无论这 $n$ 个小方块被排成怎样的长方形），所需的掰次数总是相同；而且这个数似乎是 $n$ 减一：

Conjecture 2.5.4 猜想 2.5.4

Given a $n$-square rectangular chocolate bar, it always takes $n-1$ breaks to reduce the bar to single squares.

给定一个由 $n$ 个小方块组成的长方形巧克力，把它分成单块总需 $n-1$ 次掰断。

It makes sense to prove this by induction because after breaking the bar once, you are left with smaller chocolate bars. Reducing to smaller cases is what induction is all about. We can inductively assume we already know how to deal with these smaller bars. The problem is, if we are trying to prove the inductive case about a $(k+1)$-square bar, we don't know that after the first break the remaining bar will have $k$ squares. So we really need to assume that our conjecture is true for all cases less than $k+1$.

用归纳法证明它顺理成章，因为掰一次之后，你得到的是更小的巧克力。化归为更小的情形，正是归纳法的精髓。我们可以归纳地假定已经会处理这些更小的块。问题在于：若我们要证关于 $(k+1)$ 个小方块的归纳步，我们无法保证第一次掰开后剩下的块恰好有 $k$ 个小方块。所以我们确实需要假定：对所有小于 $k+1$ 的情形，猜想都成立。

Is it valid to make this stronger assumption? Remember, in induction we are attempting to prove that $P(n)$ is true for all $n$. What if that were not the case? Then there would be some first $n_0$ for which $P(n_0)$ was false. Since $n_0$ is the first counterexample, we know that $P(n)$ is true for all $n < n_0$. Now we proceed to prove that $P(n_0)$ is actually true, based on the assumption that $P(n)$ is true for all smaller $n$.

作此更强的假定是否合法？请记住，归纳法中我们要证的是对所有 $n$，$P(n)$ 为真。倘若并非如此，就存在某个最小的反例 $n_0$ 使 $P(n_0)$ 为假。由于 $n_0$ 是第一个反例，我们知道对所有 $n < n_0$，$P(n)$ 都为真。于是，在「对所有更小的 $n$，$P(n)$ 为真」这一假定下，我们接着去证明 $P(n_0)$ 其实为真。

This is quite an advantage: we now have a stronger inductive hypothesis. We can assume that $P(1)\text{,}$ $P(2)\text{,}$ $P(3)\text{,}$ … $P(k)$ is true, just to show that $P(k+1)$ is true. Previously, we just assumed $P(k)$ for this purpose.

这带来很大便利：我们现在有了更强的归纳假设。只需假定 $P(1)\text{、}$ $P(2)\text{、}$ $P(3)\text{、}$ …… $P(k)$ 为真，便可推出 $P(k+1)$ 为真。此前，我们只假定 $P(k)$ 来达到这个目的。

It is slightly easier if we change our variables for strong induction. Here is what the formal proof would look like:

若改用更适合强归纳法的变量记号，会稍微方便些。下面是形式化证明的样子：

Strong Induction Proof Structure 强归纳法证明结构

Again, start by saying what you want to prove: "Let $P(n)$ be the statement…" Then establish two facts:

同样，先说明要证的是什么：「令 $P(n)$ 表示命题……」然后确立两件事实：
  1. Base case: Prove that $P(0)$ is true.
  2. Inductive case: Assume $P(k)$ is true for all $k < n$. Prove that $P(n)$ is true.
  1. 基础步：证明 $P(0)$ 为真。
  2. 归纳步：假设对所有 $k < n$，$P(k)$ 为真。证明 $P(n)$ 为真。

Conclude, "therefore, by strong induction, $P(n)$ is true for all $n > 0$."

作结：「因此，由强归纳法，对所有 $n > 0$，$P(n)$ 为真。」

Of course, it is acceptable to replace 0 with a larger base case if needed.5 Technically, strong induction does not require you to prove a separate base case. This is because when proving the inductive case, you must show that $P(0)$ is true, assuming $P(k)$ is true for all $k < 0$. But this is not any help so you end up proving $P(0)$ anyway. To be on the safe side, we will always include the base case separately.

当然，若有需要，把 0 换成更大的基础步也是允许的。5 严格地说，强归纳法并不要求单独证明基础步，因为在证明归纳步时，你必须证明 $P(0)$ 为真（假定对所有 $k < 0$，$P(k)$ 为真）。但这毫无助益，最终你仍得去证 $P(0)$。为稳妥起见，我们总是把基础步单独列出。

Let's prove our conjecture about the chocolate bar puzzle:

我们来证明关于巧克力谜题的猜想：

Proof 证明

Let $P(n)$ be the statement, "it takes $n-1$ breaks to reduce a $n$-square chocolate bar to single squares."

令 $P(n)$ 为命题「把一个由 $n$ 个小方块组成的巧克力分成单块，需 $n-1$ 次掰断」。

Base case: Consider $P(2)$. The squares must be arranged into a $1\times 2$ rectangle, and we require $2-1 = 1$ breaks to reduce this to single squares.

基础步：考虑 $P(2)$。两个小方块只能排成 $1\times 2$ 的长方形，而要将其分成单块，需要 $2-1 = 1$ 次掰断。

Inductive case: Fix an arbitrary $n\ge 2$ and assume $P(k)$ is true for all $k < n$. Consider a $n$-square rectangular chocolate bar. Break the bar once along any row or column. This results in two chocolate bars, say of sizes $a$ and $b$. That is, we have an $a$-square rectangular chocolate bar, a $b$-square rectangular chocolate bar, and $a+b = n$.

归纳步：任取固定的 $n\ge 2$，假设对所有 $k < n$，$P(k)$ 为真。考虑一个由 $n$ 个小方块组成的长方形巧克力。沿任意一行或一列掰一次，得到两块巧克力，设其大小分别为 $a$ 与 $b$。也就是说，我们有一块 $a$ 方块的长方形巧克力和一块 $b$ 方块的长方形巧克力，且 $a+b = n$。

We also know that $a < n$ and $b < n\text{,}$ so by our inductive hypothesis, $P(a)$ and $P(b)$ are true. To reduce the $a$-sqaure bar to single squares takes $a-1$ breaks; to reduce the $b$-square bar to single squares takes $b-1$ breaks. Doing this results in our original bar being reduced to single squares. All together it took the initial break, plus the $a-1$ and $b-1$ breaks, for a total of $1+a-1+b-1 = a+b-1 = n-1$ breaks. Thus $P(n)$ is true.

又已知 $a < n$ 且 $b < n\text{，}$ 故依归纳假设，$P(a)$ 与 $P(b)$ 为真。把 $a$ 方块的巧克力分成单块需 $a-1$ 次，把 $b$ 方块的分成单块需 $b-1$ 次。这样一来，原巧克力就被分成了单块。总共用了最初的 1 次，加上 $a-1$ 次与 $b-1$ 次，合计 $1+a-1+b-1 = a+b-1 = n-1$ 次。故 $P(n)$ 为真。

Therefore, by strong induction, $P(n)$ is true for all $n \ge 2$.

因此，由强归纳法，对所有 $n \ge 2$，$P(n)$ 为真。

Here is a more mathematically relevant example:

下面给出一个与数学更相关的例子：

Example 5

示例 5

Prove that any natural number greater than 1 is either prime or can be written as the product of primes.

证明：任何大于 1 的自然数，要么本身是素数，要么可以写成若干个素数的乘积。

Solution

解答

First, the idea: if we take some number $n\text{,}$ maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than $n$ (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

先说思路：取某个数 $n\text{，}$ 它也许是素数；若是，则已得证。若不是，则它是合数，即可分解为两个较小的数之积。这两个因子都小于 $n$（但至少为 2），于是可对它们重复上述论证，从而化归为更小的情形。

Proof

证明

Let $P(n)$ be the statement, "$n$ is either prime or can be written as the product of primes." We will prove $P(n)$ is true for all $n \ge 2$.

令 $P(n)$ 为命题「$n$ 要么是素数，要么可以写成若干素数的乘积」。我们将证明：对所有 $n \ge 2$，$P(n)$ 为真。

Base case: $P(2)$ is true because $2$ is indeed prime.

基础步：$P(2)$ 为真，因为 $2$ 确为素数。

Inductive case: assume $P(k)$ is true for all $k < n$. We want to show that $P(n)$ is true. That is, we want to show that $n$ is either prime or is the product of primes. If $n$ is prime, we are done. If not, then $n$ has more than 2 divisors, so we can write $n = m_1 \cdot m_2\text{,}$ with $m_1$ and $m_2$ less than $n$ (and greater than 1). By the inductive hypothesis, $m_1$ and $m_2$ are each either prime or can be written as the product of primes. In either case, we have that $n$ is written as the product of primes.

归纳步：假设对所有 $k < n$，$P(k)$ 为真。我们要证 $P(n)$ 为真，即证 $n$ 要么是素数，要么可写成若干素数之积。若 $n$ 是素数，则已得证。若不是，则 $n$ 有不止两个因子，于是可写为 $n = m_1 \cdot m_2\text{，}$ 其中 $m_1$ 与 $m_2$ 都小于 $n$（且大于 1）。依归纳假设，$m_1$ 与 $m_2$ 各自要么是素数，要么可写成若干素数之积。无论哪种，$n$ 都表示为若干素数之积。

Thus by the strong induction, $P(n)$ is true for all $n \ge 2$.

故由强归纳法，对所有 $n \ge 2$，$P(n)$ 为真。

Whether you use regular induction or strong induction depends on the statement you want to prove. If you wanted to be safe, you could always use strong induction. It really is stronger, so can accomplish everything "weak" induction can. That said, using regular induction is often easier since there is only one place you can use the induction hypothesis. There is also something to be said for elegance in proofs. If you can prove a statement using simpler tools, it is nice to do so.

究竟用普通归纳法还是强归纳法，取决于你要证的命题。若求稳妥，尽可一直用强归纳法——它确实更强，普通（「弱」）归纳法能做到的它都能做到。不过话说回来，普通归纳法往往更易上手，因为能使用归纳假设之处只有一处。此外，证明的简洁优雅也值得讲究：若能用更简单的工具证出，自然是好的。

As a final contrast between the two forms of induction, consider once more the stamp problem. Regular induction worked by showing how to increase postage by one cent (either replacing three 5-cent stamps with two 8-cent stamps, or three 8-cent stamps with five 5-cent stamps). We could give a slightly different proof using strong induction. First, we could show five base cases: it is possible to make 28, 29, 30, 31, and 32 cents (we would actually say how each of these is made). Now assume that it is possible to make $k$ cents of postage for all $k < n$ as long as $k \ge 28$. As long as $n > 32\text{,}$ this means in particular we can make $k = n-5$ cents. Now add a 5-cent stamp to get make $n$ cents.

最后，再对比一下两种归纳法，仍回到邮票问题。普通归纳法通过说明「邮资如何增加 1 分」（要么用三张 5 分换两张 8 分，要么用三张 8 分换五张 5 分）来推进。用强归纳法，可给出一个略有不同的证明：先验证五个基础步——可以凑出 28、29、30、31、32 分（并具体说明每种如何凑出）。现假设只要 $k \ge 28$ 且 $k < n$，就都能凑出 $k$ 分邮资。只要 $n > 32\text{，}$ 特别地就能凑出 $k = n-5$ 分，再加上一张 5 分邮票，便凑出了 $n$ 分。