强大的感应

强大的感应是归纳的一种变体吗?在归纳中，我们假设命题对前面的所有值都成立 $k$．这为我们提供了更多的信息来证明这个陈述。

现在我们知道怎么做了<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/induction-introduction/">标准的感应是时候来看看它的变体了，强归纳法。在许多方面，强归纳法与正常归纳法相似。然而，归纳假设是不同的。通常，当使用归纳法时，我们假设 $P (k)$证明是正确的 $P (k + 1)$．在强归纳法中，我们假设所有 $P(1)， P(2)，…P (k)$都是真实的 $P (k + 1)$．

我们为什么要这么做?让我们回到多米诺骨牌的类比。假设你有无限多的多米诺骨牌排列在一条线上。但这次，重量 $k ^ \文本{th}$多米诺骨牌不足以击倒 $文本(k + 1) ^ \ {th}$domino。推倒的 $文本(k + 1) ^ \ {th}$Domino需要权重所有前面的多米诺骨牌。即使是现在，如果你能够推倒第一个多米诺骨牌，你就可以证明所有的多米诺骨牌最终都会倒下。

之所以称之为“强归纳法”是因为我们在归纳假设中使用了更多的陈述。让我们更正式地把我们学到的东西写下来。

强归纳法证明

步骤1。演示基本情况:
这就是验证的地方 $P (k_0)$是真的。在大多数情况下, $k_0 = 1。$

步骤2。证明归纳步骤:
这里你假设所有的 $P (k_0)$， $P(k_0+1)， P(k_0+2)， \ldots, P(k)$是真的(我们的归纳假设)。然后你证明 $P (k + 1)$是真的。

为什么这样做的证明与标准归纳法的证明相似。

【算术基本定理】

每个整数 $n \组2$可以被唯一地写成质数的乘积。

---

基本情况:这显然是正确的 $n = 2$．

归纳步骤:假设这个命题是正确的 $N = 2,3,4, ldots, k。$
如果 $(k + 1)$是质数，那么就完成了。否则, $(k + 1)$有一个最小的质因数，我们用它来表示 $p。$让 $k + 1 = p \ N。$自 $N < k$，根据归纳假设， $N$可以被唯一地写成质数的乘积。这意味着 $k + 1 = p \ N$也可以用质数的乘积来表示。我们完成了! $_ \广场$

注意这个假设 $P (k)$是真的还不足以证明吗 $P (k + 1)$是真的。实际上我们需要另一个表述。

斐波那契数列定义为 $F_{n+2} = F_{n+1} + F_n$为整数 $n \组0$，初始值 $F_1 = f_2 = 1$．表明,

$fn = \压裂{1}{\ sqrt{5}} \离开\[左(\压裂{1 + \ sqrt{5}}{2} \右)^ n - \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ n \对吧)。$

---

基本情况:
为 $n = 1$,我们有 $lh: f = 1$和 $RHS: \压裂{1}{\ sqrt{5}} \离开\[左(\压裂{1 + \ sqrt{5}}{2} \右)^ 1 - \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ 1 \]= \压裂{1}{\ sqrt{5}} \离开[\压裂{2 \√{5}}{2}\右]= 1$．

为 $n = 2$,我们有 $Lhs: f_2 = 1$和 $RHS: \压裂{1}{\ sqrt{5}} \离开\[左(\压裂{1 + \ sqrt{5}}{2} \右)^ 2 - \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ 2 \]= \压裂{1}{\ sqrt{5}} \离开[\压裂{4 \ sqrt{5}}{4} \右]= 1$．

归纳步骤:假设这个命题是正确的 $n = k - 1$和 $k$．然后,我们有

$开始\ f {n + 1}{对齐}& = fn + f {n - 1 } \\\\ & = \ 压裂{1}{\ sqrt{5}} \离开\[左(\压裂{1 + \ sqrt{5}}{2} \右)^ n - \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ n \右]+ \压裂{1}{\ sqrt{5}} \离开\[(\压裂{1 + \ sqrt{5}}{2} \右)^ {n} - \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ {n} \ ] \\\\ & = \ 压裂{1}{\ sqrt {5}}左\[\离开(\压裂{1 + \ sqrt{5}}{2} \右)^ n + \离开(\压裂{1 + \ sqrt{5}}{2} \右)^ {n} \右]- \压裂{1}{\ sqrt{5}} \离开\[(\压裂{1 - \ sqrt{5}}{2} \右)^ n + \离开(\压裂{1 - \ sqrt{5}}{2} \右)^ {n} \ ] \\\\ & = \ 压裂{1}{\ sqrt{5}} \离开\[(\压裂{1 + \ sqrt{5}}{2} \右)^ {n + 1} -左(\ \压裂{1 -\sqrt{5} } { 2} \right)^{n+1} \right]. \end{aligned}$

因此，命题为真。 $_ \广场$

注意，在本例中，我们不需要使用前面的所有语句，而只需要使用前面的2个语句。

一个巧克力棒由排列在一个 $n \乘以m$矩形网格。你可以沿着线将棒子分割成一个个单元正方形。所需的休息次数是多少?

---

我们将展示所需的休息次数是 $nm - 1$．

基本情况:
对于一个 $1 \ * 1$Square，我们已经完成了，所以不需要任何步骤。
$1乘以1 - 1 = 0$，所以基本情况为真。

归纳步骤:让 $P (n, m)$表示需要分开的次数 $n \乘以m$广场。

WLOG，我们可以假设第一个break是沿着一行的，然后我们得到an $n_1 \乘以m$和一个 $甲烷\乘以m$酒吧, $N_1 + n_2 = n$．
根据归纳假设，我们需要进一步休息的次数是 $N_1乘以m - 1$和 $N_2乘以m - 1$．
因此，我们需要的停顿总数是

$1 + (n_1) * m -1 + (n_2) * m -1 = (n_1 + n_2) * m -1 = n * m -1。\ _ \广场$

注意:这个问题也可以用<一个href="//www.parkandroid.com/wiki/invariant-principle-definition/" class="wiki_link" title="不变性原理" target="_blank">不变性原理．

一个国家有 $n$城市。任何两个城市都有单行道连接。说明每个城市都有一条路线。

---

如果你已经读过了<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/induction-introduction/">标准归纳法的维基在美国，这个问题似乎很常见。是的，我们在那篇文章中证明了这一点(如果你还没有读过那个维基，现在是时候去看看了)。我们将看到更强的感应如何产生更短和更干净的解决方案。

我们已经看到，这个的基本情况是成立的。

现在我们做一个“强假设”。我们假设这个命题对任意集合都成立 $k$或更少的城市。

现在，对于一组 $(k + 1)$城市，拿出 $文本(k + 1) ^ \ {th}$城市 $C_ {k + 1}$然后把剩下的分成两组 $一个$和 $B$． $一个$能容纳所有的城市吗 $C_ {k + 1}$和 $B$能容纳所有的城市吗 $C_ {k + 1}$导致。

自 $一个$有 $k$或者城市更少，根据归纳假设，每个城市都有一条路径 $一个$．同样的论点也成立 $B$．

现在从经过每个城市的路线开始 $一个$．然后去 $C_ {k + 1}$．你可以这样做，因为所有的城市 $一个$导致 $C_ {k + 1}$．在那之后，去经过每个城市的路线 $B$．你可以这样做，因为 $C_ {k + 1}$通往每个城市 $B$．

就这样，我们的证据是完整的! $_ \广场$

这个证明几乎和<一个href="//www.parkandroid.com/wiki/induction/" class="wiki_link" title="标准归纳证明" target="_blank">标准归纳证明．你能看出区别吗?

让 $年代$是一组正整数，具有以下属性:

1. 整数1属于集合。
2. 每当整数 $1 2 3 ldots k$在 $年代$，下一个整数 $k + 1$必须也在 $年代$．

然后 $年代$是所有正整数的集合。

我们将用反证法来证明这个定理。

让 $T$是所有不在的正整数的集合 $年代$．的假设, $T$非空。因此它必须包含一个最小的元素，我们用它来表示 $\α$．

(1), $0 < alpha-1 < alpha$．自 $\α$最小的整数在 $T$，这意味着 $在T里的-1不等于在S里的-1$．
(2), $年代$还必须包含 $(\ alpha -) + 1 = \α$．这与假设相矛盾 $α\ \子集$ $T$．

因此设置 $T$为空，并设置 $年代$包含所有正整数。 $_ \广场$

1. 证明每个整数 $N \ neq 0$可以写成这种形式吗 $N = 2 ^ k l$,在那里 $k$是一个非负整数吗 $l$为奇数。

2. (APMO 99) $\ \} {a_i$是一个实数序列，满足 $A_ {i+j} \leq a_i + a_j$ $\原则,i, j$．证明 $\ \压裂压裂{a_1} {1} + {a₂}{2}+ \ cdots + \压裂{an} {n} \组an。$

3. 证明每个正整数 $n$具有二进制表达式。也就是说，存在整数 $C_i \in \{0,1 \}$这样 $n = 2 ^ c_r r + c_ {r 1} 2 ^ {r 1} + \ cdots + c₂2 ^ 2 + c₁2 ^ 1 + c_0 2 ^ 0。$

4. 考虑定义为 $(1 = 1, 2 = 2, 3 = 1)$和 $D_ {n+3} = D_ {n+2} + D_ {n+1} + d_n$对于所有正整数 $n$．
   表明, $D_n < 2 ^ n$．