A-level 数学/Edexcel/进阶 1/数学归纳法证明

数学归纳法证明

数学归纳法是验证或证明一个数学命题在给定参数范围内对于所有$n$值都成立的过程。例如

$Prove\ that\ f(n)=5^{n}+8n+3\ is\ divisible\ by\ 4,for\ n\in \mathbb {Z^{+}}$

我们要证明$f(n)$能被 4 整除。我们可以通过赋予$n\$值来测试它是否成立。

$n$	$f(n)$	$Divisible\ by\ 4$
$1$	$16$	$4*4$
$2$	$44$	$4*11$
$3$	$152$	$4*38$
$4$	$660$	$4*165$
$5$	$3168$	$4*792$

因此，前 5 个 n 值可以被 4 整除，但所有情况呢？这就是数学归纳法派上用场的地方。

数学归纳法是一个严谨的过程，因此所有证明都必须具有相同的通用格式

1. 命题 - 你想证明什么？
2. 基本情况 - 第一种情况是否成立？这意味着它是否适用于第一个可能的 n 值。
3. 假设 - 我们假设我们要证明的内容对一个通用数字是成立的。例如 $k$
4. 归纳 - 证明如果我们的假设对第 ($k^{th})$ 项是成立的，那么它也必须对下一项 ( $k+1^{th})$ 项成立。
5. 结论 - 正式化你的证明。

在 FP1 中，你会遇到四种数学归纳法

1. 求和级数
2. 可除性
3. 递归关系
4. 矩阵

归纳证明的示例，涉及求和级数

命题：$Prove\ by\ induction\ that,\displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2}$$,for\ n\in \mathbb {N^{+}}$

注意我们的参数，$for\ n\in \mathbb {N^{+}}$。这意味着它希望我们证明它对所有属于集合 ($\in$) 的正整数 ($\mathbb {N^{+}}$) 的 $n$ 值是成立的。

基本情况

$Let\ n=1\$

$\displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]$
${\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]$

等式左边等于等式右边，因此基本情况成立。

$LHS=RHS\longrightarrow \displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2},for\ n=1$

现在你需要做假设

$Now,\ let\ n=k\ and\ assume\ true\ \forall \ k\in \mathbb {Z^{+}}$

我们假设对于所有属于正整数集的 K 值，这个公式都是成立的。

$\displaystyle \sum _{r=1}^{k}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}$

归纳法：对于归纳法，我们需要利用我们假设 $n=k$ 成立这一事实，因此我们可以简单地将另一项 $(k+1)$ 添加到系列中 $k^{th}$ 项的总和，从而得到系列中 $(k+1)^{th}$ 项的总和。

$Hence,\ let\ n=k+1:\displaystyle \sum _{r=1}^{k+1}r^{3}=\displaystyle \sum _{r=1}^{k}r^{3}+(k+1)^{3}$

$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}$

提取 ${\frac {1}{4}}(k+1)^{2}$ 我们得到

$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]$ 

这给了我们：$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}(k+2)^{2}$
请注意，我们知道我们已经完成了，因为，看看我们最初被要求证明的内容，$n$ 值被替换为 $k+1$.

总结

$\therefore \ true\ for\ n=k+1\longrightarrow \ true\ \forall \ n\in \mathbb {Z^{+}}$
因此，如果我们的假设对于 $n=k$ 为真，那么 $n=k+1$ 也为真，这意味着 $n$ 对于所有属于正整数集的 $n$ 值都为真。

涉及可除性的归纳证明示例

命题：$Prove\ that\ 4\ |\ f(n)=5^{n}+8n+3,\ for\ n\in \mathbb {N^{+}}$

同样，请注意我们的参数，$for\ n\in \mathbb {N^{+}}$ 这意味着它希望我们证明它对于所有属于正整数集（$\in$）的 $n$ 值都为真（$\mathbb {N^{+}}$）。

基本情况

$Let\ n=1$

$f(1)=5^{1}+8(1)+3\Rightarrow f(1)=16$

$\therefore \ 4\ |\ f(1)$

假设：现在我们令 $n=k$ 其中 $k$ 是一个一般的正整数，并假设 $4\ |\ f(k)$

记住 $f(k)=5^{k}+8k+3$

归纳法：现在我们要证明第 $k+1^{th}$ 项也能够被 4 整除

因此 $let\ n=k+1\rightarrow \ f(k+1)=5^{k+1}+8(k+1)+3$

这就是我们的假设发挥作用的地方，如果 $4\ |\ f(k)$ 那么 4 也必须能整除 $f(k+1)-f(k)$

所以：$f(k+1)-f(k)=5^{k+1}+8(k+1)+3-(5^{k}+8k+3)$

$f(k+1)-f(k)=5(5^{k})-5^{k}+8$ $f(k+1)-f(k)=4(5^{k})+8$ $\therefore f(k+1)-f(k)=4(5^{k}+2)$

我们已经证明了 $4\ |\ f(k+1)-f(k)$，因此 $4\ |\ f(k+1)$，这意味着 $4\ |\ f(n)$，因为你已经成功证明了 4 能整除 $f(n)$，其中 $n$ 是一个一般的正整数 ($k$)，也是一般项后的连续项 ($k+1$)

结论

如果 $4\ |\ f(k)\Rightarrow 4\ |\ f(k+1)$
$\therefore \ 4\ |\ f(n),\forall \ n\in \mathbb {Z^{+}}$

$If\ 4\ divides\ f(k)\ (as\ we\ assumed)\ then\ it\ is\ implies\ that\ 4\ also\ divides\ f(k+1),$
$therefore\ 4\ divides\ f(n),\ for\ all\ values\ of\ n\ that\ belong\ to\ the\ set\ of\ positive\ integers.$