数学归纳法

第一步是验证这个公式在n = 1时成立。左边 = 1，而右边 =${\displaystyle {\frac {1(1+1)}{2}}=1}$，所以这个公式在n = 1时成立。第一步完成。

第二步证明假设 n = m时公式成立，则可推理出n = m+1时公式也成立。

证明步骤如下。

假设n = m时公式成立。即

${\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}}$【等式P（m）】

然后在等式等号两边分别加上m + 1得到

${\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)}$【等式P（m+1）】

这就是n = m+1时的等式。

现在需要根据等式P（m+1）演绎出等式P（m）的符号形式。(需要注意的是如果给定公示不为真，则做不到）通过因式分解合并(形式变换/字符操纵)，等式P（m+1)的右手边

${\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)[(m+1)+1]}{2}}.}$

也就是说

${\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)[(m+1)+1]}{2}}}$

这样便证明了从等式P（m） 成立可推理出等式P（m+1） 也成立。证明至此完成，结论：对于任意自然数n，P（n） 均成立。

在这个证明中，推理的过程如下：

1. 首先证明命题P(1)成立，即公式在n = 1时成立。
2. 然后证明从命题P（m） 成立可以推演出命题P（m+1） 也成立。【此部实际属于演绎推理法。技术方法是基于命题P（m+1）的符号形式变换出命题P（m）的符号形式】
3. 根据上两条从命题P(1)成立可以推理出命题P（1+1），也就是命题P(2)成立。
4. 继续推理，可以知道命题P（3）成立。
5. 从命题P(3)成立可以推导出命题P(4)也成立。
6. 不断的重复推導下一命題成立的步驟。（这就是所谓“归纳”推理的地方）
7. 我们便可以下结论：对于任意自然数n，命题P（n） 成立。

首先，我们先使得n=0的情况成立，${\displaystyle F_{0}=F_{2}-1,0=1-1=0}$ 然后，我们假定n=k的情况下的成立的，${\displaystyle F_{0}+F_{1}+...+F_{k}=F_{k+2}-1}$ 然后我们使得n=k+1的情况也成立，（这是为了表明，如果有任意数k使得其成立，则有其+1也成立） ${\displaystyle F_{0}+F_{1}+...+F_{k}+F_{k+1}=F_{k+2}-1+F_{k+1}=F_{k+3}-1}$ 于是我们得证，即从n=0，到n=0+1,1+1,2+1到所有正实数都成立，就像多米诺骨牌的第一块n=0成立而且每一块的下一块都成立（k,k+1)

第一种情况： 如果欲证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字b的自然数，那么证明的步骤需要做如下修改：

1. 第一步，证明当n = b时命题成立。
2. 第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。

用这个方法可以证明诸如“当n ≥ 3时，n² > 2n”这一类命题。

第二种情况： 如果欲证明的命题针对全部自然数，但仅当大于等于某个数字b时比较容易证明，则可参考如下步骤：

1. 第一步，证明当n =0，1，2，… b时命题成立。
2. 第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。

用这种方法可以证明一些需要通过放缩来证明的不等式。

如果我们想证明的命题并不是针对全部自然数，而只是针对所有奇数或偶数，那么证明的步骤需要做如下修改：

奇数方面：

1. 第一步，证明当n = 1时命题成立。
2. 第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。

偶数方面：

1. 第一步，证明当n = 0或2时命题成立。
2. 第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。

数学归纳法并不是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的n=0,1,2,...,m”这样的命题，如果对一般的n比较复杂，而n=m比较容易验证，并且我们可以实现从k到k-1的递推，k=1,...,m的话，我们就能应用归纳法得到对于任意的n=0,1,2,...,m，原命题均成立。

另一个一般化的方法叫完整归纳法（也称第二数学归纳法或强归纳法），在第二步中我们假定式子不仅当n = m时成立，当n小于或等于m时也成立.这样可以设计出这样两步:

1. 证明当n = 0时式子成立.
2. 证明当n ≤ m时成立，那么当n = m + 1时式子也成立.

例如，这种方法被用来证明：

${\displaystyle \mathrm {fib} (n)={\frac {\Phi ^{n}-\left(-\Phi \right)^{-n}}{5^{\frac {1}{2}}}}}$

其中fib（n） 是第n个斐波纳契数和Φ = (1 + 5^1/2) / 2 (即黄金分割).如果我们可以假设式子已经在当n = m和n = m − 1时成立，从fib（m + 1） = fib(m) + fib（m − 1）之后可以直截了当地证明当n=m + 1时式子成立.

这种方法也是第一种形式的特殊化：

1. 定义P（n） 是我们将证的式子,
2. P（0）和P（1）成立
3. P（m + 1）在P（m）和P（m − 1）成立时成立。

结论：P（n）对一切自然数n成立。

最后两步可以用这样一步表示：

1. 证明如果式子在所有的n < m成立，那么式子在当n = m时也成立.

实际上这是数学归纳法的大多数通式，可以知道他不仅对表达自然数的式子有效，而且对于任何在良基集（也就是一个偏序的集合，包括有限降链） 中元素的式子也有效（这里"<"被定义为a < b 当且仅当a ≤ b和a ≠ b）.

这种形式的归纳法当运用到序数（以有序的和一些的良基类的形式）时被称为超限归纳法.它在集合论，拓扑学和其他领域是一種重要的方法.

要区别用超限归纳法证明的命题的三种情况：

1. m是一个极小元素，也就是没有一个元素小于m
2. m有一个直接的前辈，比m小的元素有一个大的元素
3. m没有任何前辈，也就是m是一个界限序数.

参见数学归纳法的三种形式。

二階邏輯可捕捉數學歸納法這概念，表達成如下邏輯式：

${\displaystyle \displaystyle \forall P{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n{\bigl (}P(n){\bigr )}{\Bigr )}}$，

P(.) 是容納一自然數的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），k 與 n 則是自然數變元，遍歷所有自然數。

白話解釋此式，此式說：起始步驟 P(0) 與推遞步驟（即歸納假設，P(k) 蘊涵 P(k + 1)） 兩步成立會導出對任一自然數 n， P(n) 成立之結論。通常，我們為了證明第二步，會假設P(n)成立（歸納假設），再進一步證明P(n+1)。此牽涉到條件證法，將條件句之前件作為假設，假定其正確以便於證明。

若用一階邏輯將數學歸納法公設化，則須採用公設模式，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為 P₁、P₂、P₃ ，則原先以二階邏輯描述的公設可改寫為：

${\displaystyle \displaystyle P_{1}(0)\land \forall k{\bigl (}P_{1}(k)\to P_{1}(k+1){\bigr )}\to \forall n{\bigl (}P_{1}(n){\bigr )}}$，

${\displaystyle \displaystyle P_{2}(0)\land \forall k{\bigl (}P_{2}(k)\to P_{2}(k+1){\bigr )}\to \forall n{\bigl (}P_{2}(n){\bigr )}}$，

${\displaystyle \displaystyle P_{3}(0)\land \forall k{\bigl (}P_{3}(k)\to P_{3}(k+1){\bigr )}\to \forall n{\bigl (}P_{3}(n){\bigr )}}$，

。然而其強度與以二階邏輯描述之邏輯式不同，前者較後者弱。理由為一階邏輯述詞之數量為可數，而二階邏輯量限所迭代的集合為不可數。

此外，二階邏輯所表示的歸納公設綜合其它皮亞諾公設為同疇(categorical)，且所得之自然數模型無限大。根據勒文海姆-斯科倫定理，用一階邏輯表達的理論若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化[4]。亦即，用二階邏輯表達的公設僅允許一群模型彼此同構，而一階邏輯模型則因前述定理，並非每個模型都同構。

一階ZFC集合論不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：

${\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}$

${\displaystyle A}$ 本身是集合，但可視作命題——只要命題在這數下成立，數字就會收入集合。別於皮亞諾公設，將數學歸納法定為公設，ZFC集合論直接定義自然數，使得歸納法本身是定理而非公設。