2025-2-28-数学归纳法学习

数学归纳法

Mathematical Induction ,MI 是一种数学证明方法

• 作用：证明某个给定命题在整个（或局部）自然数范围内成立。
• 广义：用于证明一般良基结构。
• Example: 集合论中的树
• Alias: 结构归纳法
• 数论中：以一种不同的方式来证明任意一个给定的情形都是正确的。
• Tips: 数学归纳法不是非严谨的归纳推理法，属于严谨的演绎推理法。
• Tips: 所有数学证明都是演绎法。

合理性

• 数学归纳法的原理，通常被规定作为自然数公理（参见皮亚诺公理）。但是在另一些公理的基础上，它可以用一些逻辑方法证明。

• 良序性质（最小自然数公理）推出数学归纳法：

  • 条件1：自然数集是良序的。

  • Example: {1,2,3,4,5} 最小数1

  • 使用性质：

    • 对一个已完成上述证明的数学命题，假设并不是所有正整数都成立。

    • 不成立的数所构成的集合S，必定有最小元素k。

      Tips: 1不属于集合S 所以 k>1

    • 证明：k已经是集合S中的最小元素了，所以k-1 不属于S，意味着 k-1 命题成立

    • 既然 k-1 成立，那么也对k也应该成立

    • 这与我们第二步骤矛盾，完成两个步骤的命题能够对所有n成立

    • 其他公理和数学归纳法原理的公理化形式是等价的。

归纳法开头

由归纳法可知，原命题成立 Q.E.D

数学名词解释：

• Q.E.D：Quod Erat Demonstrandum 意为：证明完毕。

• 命题：命题是一个陈述，表述了某种数学关系或事实。（所以命题是布尔值？）意味着它们在某个已知的数学体系中可以被证明真或假。

  • 所以有真命题，假命题，伪命题？

• 命题成立：

  • 意味着已经通过了一种验证，验证方法有：
    • 逻辑推理
    • 演绎证明
    • 或者某种形式的验证

通过验证既为已经证明了它。

• 证明过程：证明过程是严格的推理，根据已知的公理、定义、或已证明的定理进行推导。

第一数学归纳法

定义： 第一数学归纳法是一种演绎证明的数学证明方法，通常有三个步骤

• 归纳奠基：证明当 n = k0 时命题成立;
• 归纳假设：假设当 n = k 时命题成立;
• 归纳递推：由归纳假设推出当 n = k+1 时，命题也成立；

第二数学归纳法

• 归纳奠基：证明当 n = k0 时 命题成立；
• 归纳假设：假设当 n ≤ k 时 命题成立；
• 归纳递推：由归纳假设推出当 n = k + 1时命题也成立；