数学归纳法证明

数学归纳法证明

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

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

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

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

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

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

1. 命题 - 你试图证明什么？
2. 基本情况 - 它对第一个情况成立吗？这意味着它对第一个可能的 $n$ 值成立。
3. 假设 - 我们假设我们试图证明的东西对一个一般数字成立。例如 $k$，也称为归纳假设。
4. 归纳 - 证明如果我们的假设对第 $k^{th})$ 项成立，那么它也必须对第 $k+1^{th})$ 项成立。
5. 结论 - 正式化你的证明。

在 FP1 中，你会遇到四种类型的数学归纳法。

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

级数求和证明的示例

(Empty)

可除性证明的示例

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

注意我们的参数，${\text{for }}n\in \mathbb {N} ^{+}$ 。这意味着我们要证明的内容必须对属于正整数集（用 $\in$ 表示）的 $n$ 的所有值成立 ($\mathbb {N} ^{+}$).

基本情况

${\begin{aligned}&{\text{Let }}n=1\\&f(1)=5^{1}+8(1)+3\implies f(1)=16\\&\therefore 4~|~f(1)\end{aligned}}$

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

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

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

因此：${\text{let }}n=k+1\implies 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)$

${\begin{aligned}&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)\end{aligned}}$

现在我们已经证明了$4~|~{\bigl (}f(k+1)-f(k){\bigr )}$，因此$4~|~f(k+1)$。这意味着$4~|~f(n)$，因为你已经成功地证明了 4 整除$f(n)$，其中$n$ 是一个一般的正整数（$k$），也是一般项后的连续项（$k+1$）。

结论

${\begin{aligned}&4~|~f(k)\implies 4~|~f(k+1)\\&\therefore ~4~|~f(n),\forall n\in \mathbb {Z} ^{+}\end{aligned}}$

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

用递归关系证明的例子

(Empty)

用矩阵证明的例子

(Empty)