文章目录
Proof by Induction
Concept
Mathematical induction works the same way as dominoes: if we set them all up, and then knock over just the first one, they will all fall down. Induction works for any proof in which we need to prove an infinite number of cases (actually, it must be a countably infinite number of cases—you’ll understand what this means in Chapter 8 8 8).
Let’s say we’re able to set up the dominoes by proving the following: if we assume the theorem is true for case 1, then it is also true for case 2; if we assume the theorem is true for case 2, then it is also true for case 3; and so on. This can by summarized by proving that if the theorem is true for n − 1, then it is also true for n. Now all we need to do is knock down the first domino by proving that the theorem is true for case 1. They all fall down, since our setup tells us that once case 1 is true, so is case 2; and now that case 2 is true, so is case 3; and so on.
Knocking the first domino down is easier, so we usually do it first (this step is called the base case). Then we assume the theorem is true for the n − 1 n − 1 n−1 case (this assumption is called the inductive hypothesis) and show that it is also true for the n n n case (this step is called the inductive step).
Example
Let’s try to find a formula for the sum of the first n n n natural numbers, 1 + 2 + 3 + . . . + n 1 + 2 + 3 + . . . + n 1+2+3+...+n. Using our notation from the previous section, this sum is equivalent to ∑ i = 1 n i \displaystyle \sum_{i=1}^ni i=1∑ni.
If you play with this long enough, you might stumble on the answer: ∑ i = 1 n = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n=\frac{n(n+1)}{2} i=1∑n=2n(n+1).
Try plugging in a few values to convince yourself that the formula works. To prove it, we’ll need to be more rigorous (a few examples isn’t a proof, since they don’t exclude the possibility that a counterexample exists). We need to show that this formula works for every possible choice of n n n, which can be any positive integer. Therefore, induction is probably the best technique.
- Base Case. We just need to show that the formula holds for the case n = 1 n = 1 n=1. Well, ∑ i = 1 1 = 1 = 1 ( 1 + 1 ) 2 \displaystyle\sum_{i=1}^1=1=\frac{1(1+1)}{2} i=1∑1=1=21(1+1), so the first step is done. Yay! (Base cases are usually a breeze.)
- Inductive Step. The inductive hypothesis lets us assume that the formula is true for n − 1 n − 1 n−1, so we can assume that ∑ i = 1 n − 1 i = ( n − 1 ) n 2 \displaystyle \sum_{i=1}^{n-1}i=\frac{(n-1)n}{2} i=1∑n−1i=2(n−1)n. Using this assumption, we want to show that the formula holds for n n n, meaning ∑ i = 1 n = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n=\frac{n(n+1)}{2} i=1∑n=2n(n+1). By making a substitution and simplifying, we can write ∑ i = 1 n i = ( ∑ i = 1 n − 1 i ) + n = ( n − 1 ) n 2 + n = n 2 − n 2 + 2 n 2 = n 2 + n 2 = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n i= \left(\sum_{i=1}^{n-1}i\right)+n=\frac{(n-1)n}{2}+n=\frac{n^2-n}{2}+\frac{2n}{2}=\frac{n^2+n}{2}=\frac{n(n+1)}{2} i=1∑ni=(i=1∑n−1i)+n=2(n−1)n+n=2n2−n+22n=2n2+n=2n(n+1), and that’s it!
Although it seems almost too simple, remember, there’s no magic involved. We didn’t “bootstrap” the proof or use circular logic. We just used the inductive step to say, “if it
works for
1
1
1, then it works for
2
2
2; if it works for
2
2
2, then it works for
3
3
3; and so on,” and because the base case says, “it works for 1,” we have thus proved it for every possible positive integer choice of
n
n
n (in other words, for every
n
n
n in
N
\mathbb{N}
N).
归纳证明
概念
数学归纳法的工作原理与多米诺骨牌相同：如果我们将它们全部竖立起来，然后推倒第一个，它们就都会倒下。归纳法适用于我们需要证明无限多情况的任何证明（实际上，它必须是可数无限多的情况——你会在第 8 8 8章理解这意味着什么）。
假设我们能够通过证明以下内容来设置多米诺骨牌：如果我们假设定理对第一种情况成立，那么它对第二种情况也成立；如果我们假设定理对第二种情况成立，那么它对第三种情况也成立；以此类推。这可以总结为证明：如果定理对 n − 1 n-1 n−1成立，那么它对 n n n也成立。现在我们所要做的就是推倒第一个多米诺骨牌，通过证明定理对第一种情况成立。它们都会倒下，因为我们的设置告诉我们一旦第一种情况成立，第二种情况也成立；现在第二种情况成立，第三种情况也成立；以此类推。
推倒第一个多米诺骨牌更容易，所以我们通常先做这一步（这一步被称为基础情况）。然后我们假设定理对 n − 1 n-1 n−1的情况成立（这个假设被称为归纳假设），并证明它对 n n n的情况也成立（这一步被称为归纳步骤）。
案例
我们尝试找出前 n n n个自然数的和的公式，即 1 + 2 + 3 + … + n 1 + 2 + 3 + \ldots + n 1+2+3+…+n。使用上一节的符号表示，这个和等价于 ∑ i = 1 n i \displaystyle \sum_{i=1}^n i i=1∑ni。
如果你足够长时间地研究这个问题，你可能会偶然发现答案： ∑ i = 1 n = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n = \frac{n(n+1)}{2} i=1∑n=2n(n+1)。
尝试代入一些值来说服自己这个公式是正确的。为了证明它，我们需要更严谨（几个例子不能构成证明，因为它们不能排除存在反例的可能性）。我们需要证明这个公式对每一个可能的 n n n都成立， n n n可以是任何正整数。因此，归纳法可能是最好的技术。
- 基础情况： 我们只需要证明当 n = 1 n = 1 n=1时公式成立。那么， ∑ i = 1 1 = 1 = 1 ( 1 + 1 ) 2 \displaystyle \sum_{i=1}^1 = 1 = \frac{1(1+1)}{2} i=1∑1=1=21(1+1)，所以第一步完成了。太棒了！（基础情况通常很简单。）
- 归纳步骤： 归纳假设让我们假设公式对 n − 1 n - 1 n−1成立，所以我们可以假设 ∑ i = 1 n − 1 i = ( n − 1 ) n 2 \displaystyle \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} i=1∑n−1i=2(n−1)n。使用这个假设，我们想证明公式对 n n n成立，即 ∑ i = 1 n = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n = \frac{n(n+1)}{2} i=1∑n=2n(n+1)。通过代换和简化，我们可以写成 ∑ i = 1 n i = ( ∑ i = 1 n − 1 i ) + n = ( n − 1 ) n 2 + n = n 2 − n 2 + 2 n 2 = n 2 + n 2 = n ( n + 1 ) 2 \displaystyle \sum_{i=1}^n i = \left(\sum_{i=1}^{n-1} i\right) + n = \frac{(n-1)n}{2} + n = \frac{n^2 - n}{2} + \frac{2n}{2} = \frac{n^2 + n}{2} = \frac{n(n+1)}{2} i=1∑ni=(i=1∑n−1i)+n=2(n−1)n+n=2n2−n+22n=2n2+n=2n(n+1)，这就完成了证明。
虽然它看起来几乎太简单了，但记住，这里没有魔法。我们没有“自举”证明或使用循环逻辑。我们只是使用归纳步骤说，“如果它对 1 1 1成立，那么它对 2 2 2成立；如果它对 2 2 2成立，那么它对 3 3 3成立；以此类推”，而基础情况说，“它对 1 1 1成立”，因此我们已经证明了对每一个可能的正整数选择的 n n n（换句话说，对每一个 n n n在 N \mathbb{N} N中）都成立。
标签：case,frac,归纳,sum,证明,初探,成立,true,displaystyle From： https://blog.csdn.net/howard2005/article/details/144171277