三部曲： 归纳 -> 猜想 -> 证明
一般地，证明一个与正整数n有关的命题，可按下列步骤进行：
(1)归纳奠基：证明当n取第一个值n0(n0∈N∗)时命题成立；
(2)归纳递推：假设当n＝k(k≥n0，k∈N∗)时命题成立，推出当n=k+1时命题也成立。
只要完成这两个步骤，就可以断定命题对从n0开始的所有正整数n都成立．上述证明方法叫做数学归纳法。
注意事项:
1.凡是与自然数有关的命题，或探索性问题都可以使用数学归纳法来证明。
2.两个步骤缺一不可，第一步是归纳奠基，第二步是归纳递推。 第一步的初值不一定是n0=1，还有可能是n0=2或n0=3，比如涉及到多边形的问题时，其初值往往为n0=3。
3.第二步在证明n=k+1时命题成立的时候，必须使用n=k时的归纳假设，否则绕过归纳假设得出的结论就是不可靠的，是错误的。
4.数学归纳法的难点其一，就是从n=k到n=k+1时的项数的变化情况，大多情况下，增加项数为1项，但不是所有题目都增加的项数为1项，当k在指数位置时，增加的项数往往不止一项。
5.在证明n=k＋1(k∈N∗，k≥n0)时命题成立的常用技巧：
①分析n＝k＋1时命题与n＝k时命题形式的差别，确定证明目标。
②证明恒等式时常用乘法公式、因式分解、添拆项配方、通分等等变形技巧，证明不等式时常用分析法、综合法、放缩法、做差法等。
③可能用到公式：(a+b)3=a3+3a2b+3ab2+b3，a3+b3=(a+b)(a2−ab+b2)
ex2:
ex3:
布尔不等式（Boole’s inequality）也叫（union bound），即并集的上界，描述的是至少一个事件发生的概率（P(⋃iAi)P(⋃iAi)\mathbb{P}\left(\bigcup_i A_i\right)）不大于单独事件（事件之间未必独立）发生的概率之和（∑iP(Ai)∑iP(Ai)\sum_i\mathbb P(A_i)）。
P(⋃iAi)≤∑iP(Ai)P(⋃...
一般地，证明一个与正整数\(n\)有关的命题，可按下列步骤进行：
(1)归纳奠基：证明当\(n\)取第一个值\(n_0 (n_0∈N^*)\)时命题成立；
(2)归纳递推：假设当\(n＝k(k≥n_0，k∈N^*)\)时命题成立，推出当\(n=k+1\)时命题也成立。
只要完成这两个步骤，就可以断定命题对从\(n_0\)开始的所有正整数\(n\)都成立．上述证明方法叫做数学归纳法。
二、...
1，证明P(0)正确。
2，假设P(k)正确，证明P(k+1)正确。
正如《程序员的数学》（结城浩 著）一书里作者写道：在学校学习数学归纳法之初，我不是很理解这个结构。
虽说等式的计算并没有那么难，但我不认为数学归纳法是有效的证明方法。当初我搞不明白的是步骤2。在步骤2中，
是要假设P(k)成立，推导出P(k+1)。我当是却想：‘P(k)不是现在要证明的式子吗？如果这样就谈不上证明了吧。‘
数学归纳法(mathematical induction)是一种数学证明方法，常用于证明命题(命题是对某个现象的描述)在自然数范围内成立。随着现代数学的发展，自然数范围内的证明实际上构成了许多其他领域(比如数学分析)的基础，所以数学归纳法对于整个数学体系至关重要。数学归纳法本身非常简单。如果我们想要证明某个命题对于自然数n都成立，那么:
第一步 证明命题对于n = 1成立。
第二步 假设命
什么是数学归纳法
对于某些使用迭代法或者递归的代码，验证的时候可以避免一步步的计算，直接从理论上证明某个结论，节约大量的计算资源和时间，这就是数学归纳法。
数学归纳法的步骤
证明基本情况（通常是 n = 1 的时候）是否成立
假设n = k - 1 成立，再证明 n = k 也是成立的（k 为任意大于1的自然数）
数学归纳和递归的关系
递归调用的代码和数学归纳法的逻辑是一致的，只...
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：
证明当 n= 1 时命题成立。
假设 n=m 时命题成立，那么可以推导出在 n=m+1 时命题也成立。（m代表任意自然数）
设 G=(V, E) 为一个有向图或无向图，假定 BFS 以给定结点 s∈Vs\in V 作为源节点在图 G 上运行。则在 BFS 终结时，对于每个结点 v∈Vv\in V，BFS 计
