查看“︁高中数学/不等式与数列/数学归纳法”︁的源代码

== 阅读指南 ==
[[File:Crystal Clear app gnome.png | Crystal Clear app gnome | 50px]]

希望快速了解或快速回顾高中数学的读者可以只看基础知识部分。其余部分是为需要参加学科考试或需要一定知识提升的读者准备的。

本节介绍的数学归纳法在数学的各个领域中都有重要作用，是一种通用性比较广的代数证明方法，主要适用于证明对于正整数恒成立的相关命题。集合论中适用于[[w:超限数|超限数]]的[[w:超限归纳法|超限归纳法]]是数学归纳法的重要推广。作为定义自然数的主要（不是唯一的）公理化方式的[[w:皮亚诺公理|皮亚诺公理]]也蕴含数学归纳法的思想。数学归纳法也会在学习[[高中数学/高等数学初步/极限|极限]]时发挥很大作用。

=== 预备知识 ===
本节内容涉及函数迭代与数列递推的概念，所以读者应该先阅读[[高中数学/函数与三角/分段函数、复合函数与反函数的概念|复合函数]]与[[高中数学/不等式与数列/一阶递推数列及通项公式的求解|一阶递推数列]]章节。

=== 考试要求 ===
在中国大陆高考中，数学归纳法曾是理科数学试卷的考查点之一，常用于解决大题中的结论证明，一般出题难度中等，是比较常用的代数证明方法。而对于高考取消文理分科考法的地区，目前并不将其纳入必考知识范围，只将其列为选学内容。不过由于数学归纳法简单易学，并且是非常重要的代数证明方法，我们仍将其纳入主干知识的范围。

== 基础知识 ==
=== 知识引入 ===
假设一个数列<math>\{a_n\}</math>的通项公式是<math>a_n = (n^2 - 5n + 5)^2</math>，容易验证此数列前4项的取值都是1，但是我们不能就此认为它的第5项也等于1。实际上容易验证<math>a_5 = 25 \neq 1</math>。这说明看上去可能成立的规律并非总是可靠。<ref name="人教版课本2004年高中数学_数学归纳法" />

再比如已知<math>a + b + c = 1, a^2 + b^2 + c^2 = 2, a^3 + b^3 + c^3 = 3</math>，要求<math>a^4 + b^4 + c^4</math>的值。由于前3个式子的计算结果依次为1、2、3，首先最容易猜想第4个式子的结果有可能是4，但是再稍微想一想就会发现支持答案为4的理由并不明显。事实上，这是一道需要使用多个多元[[w:等幂和差|等幂和公式]]求解的坑人题，而且其答案确实不是一开始最容易想到的4。如果继续增加变量和已知算式的个数，这个题还可以变得更为迷惑人。总而言之，基于有限个特例得到的经验并非总是可靠无误。

又比如对于数列<math>\{b_n\}</math>，已知<math>b_1 = 1, b_{n+1} = \frac{b_n}{1 + b_n} \quad (n = 1, 2, 3, ...)</math>。通过对其前4项的计算，容易猜想其通项公式为<math>b_n = \frac 1 n</math>。可以发现，这种与正整数n有关的命题，包含了无穷多种具体情况，如果逐一通过计算验证显然是不可能做到的<ref name="人教版课本2007年高中数学选修2-2_数学归纳法" />。为此需要另想办法，做到只通过有限多个步骤，证明n取所有正整数时命题都成立<ref name="人教版课本2007年高中数学选修2-2_数学归纳法" />。而本节介绍的数学归纳法就是通过构建恒成立的递推关系式来达到这个目的。当然对于这种特殊的分式线性递推关系式，在后面的[[高中数学/不等式与数列/不动点法|不动点法]]章节中还会继续介绍其它求解方法。

=== 普通数学归纳法的概念 ===
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">
证明一个与正整数n有关的命题，可以按下列步骤进行：<br />
# 归纳奠基（base case）：证明当n取第一个值<math>n_0 \quad (n_0 \in \mathbb{R}^+)</math>时命题成立；
# 归纳递推（induction step）：假设<math>n = k \quad (k > n_0, k \in \mathbb{R}^+)</math>时命题成立，继续证明当<math>n = k + 1</math>时命题也成立。
只要完成这2个步骤，就可以断定命题对于从<math>n_0</math>开始的所有正整数n都成立。<br />
这个证明方法叫做'''数学归纳法'''（'''mathematical induction'''）<ref name="人教版课本2004年高中数学_数学归纳法">{{cite book |title=数学 |author=人民教育出版社中学数学室 |series=全日制普通高级中学教科书 |volume=第3册 (选修Ⅱ) |publisher=[[w:人民教育出版社|人民教育出版社]] |location=中国北京沙滩后街55号 |edition=1 |isbn=7-107-17448-7 |section=第2章“极限”第2.1节“数学归纳法” |pages=62-72 |language=zh-cn |year=2004}}</ref><ref name="人教版课本2007年高中数学选修2-2_数学归纳法">{{cite book |title=高中数学 (A版) 选修2-2 |author=钱珮玲; 王嵘; 张劲松; 郭慧清; 李龙才; 宋莉莉; 杨照宇; 蒋佩锦 |editor1=刘绍学 (主编) |editor2=章建跃 (副主编) |editor3=李龙才 (责任编辑) |publisher=人民教育出版社 |location=中国北京市海淀区中关村南大街17号院1号楼 |edition=2 |isbn=978-7-107-18675-2 |section=第2讲“推理与证明”第2.3节“数学归纳法” |pages=92-96 |language=zh-cn |year=2007}}</ref>，简称“数归法”（'''MI'''）。
</font>
</blockquote>

数学归纳法可以用流程框图表示为<ref name="人教版课本2007年高中数学选修2-2_数学归纳法" />（在维基教科书输入中文流程图不方面，先将就着看吧……）：<br />
<math>
\left .
\begin{array}{l}
 \mbox{prove that the proposition holds for n = }n_0 \\
 \mbox{given the proposition holds for n = k} \quad (k \ge n_0), \mbox{ prove it still holds when } n = k+1
\end{array}
\right \}
\Rightarrow \mbox{the proposition holds for all n } \quad (n \ge n_0)
</math><br />
<math>
\left .
\begin{array}{l}
 \mbox{归　纳　奠　基　：简　单　验　证　} \ n = n_0 \mbox{时　命　题　成　立} \\
 \mbox{归　纳　递　推　：假　设　} \ n = k \quad (k \ge n_0) \mbox{时　命　题　成　立　，证　明　n = k+1时　命　题　也　成　立}
\end{array}
\right \}
\Rightarrow \mbox{命　题　对　从　} \ n_0 \mbox{开　始　的　所　有　正　整　数　n都　成　立　} \ 
</math>

<!-- 本小节例题 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题：
已知在数列<math>\{b_n\}</math>中，有<math>b_1 = 1, b_n = \frac{b_n}{b_n + 1} \quad (n \ge 1, n \in \mathbb{N}^+)</math>，使用数学归纳法证明：<math>b_n = \frac 1 n</math>。

[[File:Dominoeffect.png |thumb |150px |数学归纳法的论证思路借助了[[w:多米诺骨牌效应|多米诺骨牌效应]]。]]
一个与数学归纳法密切相关的生活实例是[[w:多米诺骨牌|多米诺骨牌]]游戏。可以看出，只要满足以下2个条件，所有多米诺骨牌就都能倒下<ref name="人教版课本2007年高中数学选修2-2_数学归纳法" />：
# 保证第1个块骨牌倒下；
# 对于任意两块相邻的骨牌，保证前一块倒下时一定导致后一块也倒下。
其递推关系为：当第k块倒下时，与其相邻的第k+1块也一定倒下。此时，只需要设法推倒第一块骨牌，即可保证其它骨牌一定都会倒下。

数学归纳法是一种环环相扣的无限递推的论证方法，其思路就像多米诺骨牌游戏一样，可以使一连串的无穷个命题依次地得到证明。其中每一环的论证都依赖于前一环的成功论证以及相邻命题之间递推关系的成立。这个证明过程中最重要的一步就是找到并证明相邻命题之间递推关系，也就是要将一个较大的问题设法化归为（或者说[[w:递归|递归]]地表达为）一个规模更小、更易解决的问题。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：某些版本的高中数学教材上还有介绍“不完全归纳法”与“完全归纳法”的概念，并指出数学归纳法是一种完全归纳法<ref name="人教版课本2004年高中数学_数学归纳法" />。由于这方面的介绍和讨论只是枯燥的逻辑学问题，而不是数学问题，故我们学习数学时其实没有必要了解什么是不完全归纳法。

=== 证明等式 ===
<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
使用数学归纳法求证：<math>(x + 1)^n = (x+1) + x(x+1) + x(x+1)^2 + \cdots + x(x+1)^{n-1}</math>。

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
使用数学归纳法求证下列等幂求和公式：<br />
(1) <math>1 + 2 + 3 + \cdots + n = \frac{n(1+n)}{2}</math>。<br />
(2) <math>1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}</math>。<br />
(3) <math>1^3 + 2^3 + 3^3 + \cdots + n^3 = (\frac{n(n+1)}{2})^2</math>。

<!-- 本小节例题3 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题3：
求证：<math>1 \times 4 + 2 \times 7 + 3 \times 10 + ... + n (3n+1) = n(n+1)^3 \quad (n \in \mathbb{N}^+)</math>。

<!-- 本小节例题4 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题4：
求证：<math>1^2 - 2^2 + 3^2 - 4^2 + ... + (2n-1)^2 - (2n)^2 = -n (2n + 1) \quad (n \in \mathbb{N}^+)</math>。

<!-- 本小节例题5 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题5：
求证：<math>-1 + 3 - 5 + ... + (-1)^n (2n-1) = (-1)^n n</math>。

<!-- 本小节例题6 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题6：
求证：<math>1 \times n + 2 \times (n-1) + 3 \times (n-2) + ... + n \times 1 = \frac{n(n+1)(n+2)}{6}</math>。

<!-- 本小节例题7 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题7：
Find and prove by induction a formula for <math>\sum_{i = 1}^n\limits (2i - 1)</math> (i.e., the sum of the first n odd numbers), where <math>n \in \mathbb{Z}_+</math>.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题8 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题8：
利用数学归纳法求证：<br />
<math>(1 \cdot 2^2 - 2 \cdot 3^2) + (3 \cdot 4^2 - 4 \cdot 5^2) + ... + ((2n - 1) \cdot (2n)^2 - 2n \cdot (2n+1)^2) = -n(n+1)(4n+3)</math>

<!-- 本小节例题9 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题9：
Let <math>x \neq 0</math> be a real number such that <math>x + x^{-1} \in \mathbb{Z}</math>. Prove that for any <math>n \in \mathbb{Z}, x^n + x^{-n} \in \mathbb{Z}</math>.<ref name="upenn.edu_Alexandersson_ProofByInduction" />

<!-- 本小节例题10 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题10：
Find and prove by induction a formula for <math>\prod_{i = 2}^n\limits (1 - \frac{1}{i^2})</math>, where <math>n \in \mathbb{Z}_+</math> and <math>n \ge 2</math>.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题11 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题11：
Prove that <math>\sum_{i = 1}^n\limits i \cdot (i!) = (n+1)! - 1</math>.<ref name="upenn.edu_Alexandersson_ProofByInduction" />

<!-- 本小节例题12 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题12：
Prove that <math>\prod_{i = 1}^n\limits \frac{i^2}{i+1} = \frac{n!}{n+1}</math>.<ref name="upenn.edu_Alexandersson_ProofByInduction" />

<!-- 本小节例题13 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题13：
求证[[初中数学/算术与代数/韦达定理|韦达定理]]对n次实系数方程成立。（如果不知道[[w:代数基本定理|代数基本定理]]，可以只考虑有n个实数根的n次方程的情况。）

<!-- 本小节例题14 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题14：
设正数<math>w_1</math>为数字a的权重值，正数<math>w_2</math>为数字b的权重值，若定义2个数a和b的加权平均数为<math>\frac{w_1 a + w_2 b}{w_1 + w_2}</math>，求证n个数的加权平均数计算公式为：<br />
<math>\frac{w_1 x_1 + w_2 x_2 + ... + w_n x_n}{w_1 + w_2 + ... + w_n}</math><br />
其中各个正数<math>w_i</math>分别是下标对应的数字<math>x_i</math>的权重值。

<!-- 本小节例题15 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题15：
使用数学归纳法证明[[w:等幂和差|等幂和公式]]：<br />
<math>a^n - b^n = (a-b) \sum_{r=1}^n\limits a^{n-r} b^{r-1} = (a-b) (a^{n-1} + a^{n-2} b + ... + b^{n-1})</math>

<!-- 本小节例题16 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题16：
Number of subsets: Show that a set of n elements has <math>2^n</math> subsets.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题17 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题17：
Number of 2-element subsets: Show that a set of n elements has <math>\frac{n(n-1)}{2}</math> subsets with 2 elements. (Take n = 2 as the base case.)<ref name="Hildebrand_Math_213" />

<!-- 本小节例题18 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题18：
Generalization of De Morgan's Law to unions of n sets. Show that if <math>A_1, A_2, ..., A_n</math> are sets, then<br />
<math>
\overline{A_1 \cup ... \cup A_n} = \overline{A_1} \cap ... \cap \overline{A_n}
</math>.<ref name="Hildebrand_Math_213">{{cite web |url= https://faculty.math.illinois.edu/~hildebr/213/inductionsampler.pdf |format=pdf |title=Math 213 Worksheet: Induction Proofs III, Sample Proofs |author=A.J. Hildebrand |publisher=[[w:伊利诺伊大学厄巴纳-香槟分校|University of Illinois at Urbana-Champaign]] |language=en |date= |access-date=2020年12月10日}}</ref>

=== 证明不等式 ===

== 常用结论与常见模型 ==
=== 简单的整除性问题 ===
<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
求证：形如<math>n^3 + 5n \quad (n \in \mathbb{N}^+)</math>的数总能够被6整除。

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
求证：形如<math>8^n - 3^n \quad (n \in \mathbb{N}^+)</math>的数总能够被5整除。

<!-- 本小节例题3 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题3：
Use the Principle of Mathematical Induction to verify that, for n any positive integer, <math>6^n - 1</math> is divisible by 5.<ref name="umanitoba.ca_thomas" />

=== 参数求值问题 ===
<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
求使得关系式<math>1 \times 2 + 4 \times 3 + 9 \times 4 + \cdots + n^2 (n+1) = \frac n m (n+1)(n+2)(3n+1)</math>恒成立的m的取值。

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
如果对于任意的<math>n \in \mathbb{N}^+</math>，<math>3^{4n+2} + a^{2n+1}</math>都能被14整除，求a可以取的最小自然数。

=== 简单的一阶递推数列证明题 ===

=== 抽象推理 ===
<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
已知函数<math>f(x)</math>满足<math>f(xy) = f(x) + f(y)</math>，利用数学归纳法证明<math>f(x^n) = n f(x) \quad (n \in \mathbb{N}^+)</math>。

<!-- 本小节例题1的解答 -->
<div class="collapsible proof" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>证明：<br />
 ①令y = 1，则有<math>f(x) = f(x) + f(1)</math>，即<math>f(1) = 0</math>。即在此情况下，结论成立。<br />
 ②假设n = k时，有<math>f(x^k) = k f(x)</math>。则当n = k+1时，有：<br />
 <math>f(x^{k+1}) = f(x^k * x) = f(x^k) + f(x) = k f(x) + f(x) = (k+1) f(x)</math><br />
 所以当n = k+1时，结论也成立。<br />
 综合①、②可知，原结论成立。
 </p>
</div>

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
设<math>f(n) = 1 + \frac 1 2 + \frac 1 3 + ... + \frac 1 n</math>，是否存在<math>g(n)</math>使得等式<math>f(1) + f(2) + ... + f(n - 1) = g(n)f(n) - g(n)</math>对满足<math>n \ge 2</math>的一切自然数n成立？使用数学归纳法证明这个结论。

=== 几何问题 ===
<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
求证<math>n \quad (n \ge 3, n \in \mathbb{N})</math>边形的内角和公式为<math>(n-2) \times 180^\circ</math>。

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
利用多边形三角剖分（polygon triangulation）思想，求证计算平面<math>n \quad (n \ge 3, n \in \mathbb{N})</math>边形面积A的高斯鞋带公式（shoelace formula）：
<math>
\begin{align}
 \mathbf{A} & = {1 \over 2} \left| \sum_{i=1}^{n-1} x_i y_{i+1} + x_n y_1 - \sum_{i=1}^{n-1} x_{i+1} y_i - x_1 y_n \right| \\[4pt]
 & = {1 \over 2} |x_1 y_2 + x_2 y_3 + \cdots + x_{n-1} y_n + x_n y_1 - x_2 y_1 - x_3 y_2 - \cdots - x_n y_{n-1} - x_1 y_n|
\end{align}
</math><br />
其中<math>(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)</math>依次是n边形的各个顶点。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：鞋带公式也可以被视为[[w:微积分学|微积分学]]中[[w:格林公式|格林公式]]的离散化版本。

<!-- 本小节例题3 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题3：
平面多边形X可以被剖分为n个有限的简单图形<math>X_1, X_2, ..., X_n</math>，这些简单图形的重心坐标依次为<math>(C_{1x}, C_{1y}), (C_{2x}, C_{2y}), ..., (C_{nx}, C_{ny})</math>，面积依次为<math>A_1, A_2, ..., A_n</math>。<br />
(1) 根据重心的定义，求证这个平面多边形的整体重心坐标<math>(C_x, C_y)</math>可计算如下：<br />
<math>
\left\{
\begin{align}
C_x = \frac{\sum C_{i_x} A_i}{\sum A_i} = \frac{C_{1x} A_1 + C_{2x} A_2 + ... + C_{nx} A_n}{A_1 + A_2 + ... + A_n} \\
C_y = \frac{\sum C_{i_y} A_i}{\sum A_i} = \frac{C_{1y} A_1 + C_{2y} A_2 + ... + C_{ny} A_n}{A_1 + A_2 + ... + A_n}
\end{align}
\right.
</math><br />
(2) 若一个正<math>n \quad (n \ge 3, n \in \mathbb{N})</math>边形的各个顶点坐标依次为<math>(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)</math>。利用多边形三角剖分思想和鞋带公式，求证其重心坐标公式为：<br />
<math>
\left\{
\begin{align}
C_x = \frac{1}{6A} \sum_{i=1}^n (x_i + x_{i+1})(x_i y_{i+1} - x_{i+1} y_i) \\
C_y = \frac{1}{6A} \sum_{i=1}^n (y_i + y_{i+1}) (x_i y_{i+1} - x_{i+1} y_i)
\end{align}
\right.
</math>

=== 强数学归纳法 ===
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">
'''强归纳法'''（'''strong induction'''）也叫'''完整数学归纳法'''（'''complete induction'''）或'''第二数学归纳法'''，是普通数学归纳法的最常用的变体。它仍用于证明与正整数n有关的命题，但其论证步骤变为：<br />
# 归纳奠基（base case）：证明当n取第一个值<math>n_0 \quad (n_0 \in \mathbb{R}^+)</math>时命题成立；
# 归纳递推（induction step）：假设<math>n < k \quad (k > n_0, k \in \mathbb{R}^+)</math>时命题成立，继续证明当<math>n = k</math>时命题也成立。
只要完成这2个步骤，就可以断定命题对于从<math>n_0</math>开始的所有正整数n都成立。
</font>
</blockquote>

我们知道，使用普通数学归纳法的重点和难点是要将一个较大的问题设法化归为（或者说递归地表达为）一个规模更小、更易解决的问题。但是有时候，将一个较大的问题设法化归为（或者说递归地表达为）有限多个规模更小、更易解决的问题会更容易。这时就要用到强数学归纳法。换句话说，如果一个问题更容易转换为多个小规模的相似子问题解决，而不是只转换为一个小规模的相似子问题解决，则适合考虑使用强数学归纳法。从另一个角度而言，强数学归纳法适合解决涉及二阶和更高阶的递推关系的性质证明。

<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
Consider the famous Fibonacci sequence <math>\{F_n\}_{n=1}^{\infty}</math>, defined by the relations <math>F_1 = 1, F_2 = 1</math>, and <math>F_n = F_{n-1} + F_{n-2}</math> for <math>n \ge 3</math>.
Use an extended Priciple of Mathematical Induction in order to show that for <math>n \ge 1</math>, <math>F_n = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n)</math>.<ref name="umanitoba.ca_thomas">{{cite web |url= http://home.cc.umanitoba.ca/~thomas/Courses/InductionExamples-Solutions.pdf |format=pdf |title=Induction Examples |author=R. S. D. Thomas |publisher=[[w:曼尼托巴大学|University of Manitoba]] |language=en |date= |access-date=2020年12月10日}}</ref><br />
考虑由递推关系<math>F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} \quad (n \ge 3)</math>定义的知名的Fibonacci数列。使用数学归纳法证明它有如下通项公式：
<math>F_n = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n)</math>

<!-- 本小节例题1的解答 -->
<div class="collapsible proof" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>证明：<br />
 ①当n = 1时，公式可以验证如下：<br />
 <math>
 \begin{array}{l}
 F_1 = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^1 - (\frac{1 - \sqrt{5}}{2})^1) \\
	= \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2}) \\
	= \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2}) \\
	= \frac{1}{\sqrt{5}}(\frac{2 \sqrt{5}}{2}) \\
	= 1
 \end{array}
 </math><br />
 ②当n = 2时，公式可以验证如下：<br />
 <math>
 \begin{array}{l}
	F_2 = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^2 - (\frac{1 - \sqrt{5}}{2})^2) \\
	= \frac{1}{\sqrt{5}}(\frac{1 + 2 \sqrt{5} + 5}{4} - \frac{1 - 2 \sqrt{5} + 5}{4}) \\
	= \frac{1}{\sqrt{5}}(\frac{1 + 2 \sqrt{5} + 5 - 1 + 2 \sqrt{5} - 5}{4}) \\
	= \frac{1}{\sqrt{5}}(\frac{4 \sqrt{5}}{4}) \\
	= 1
 \end{array}
 </math><br />
 ③假设当<math>n = k, k+1 \quad (k \ge 1)</math>时，公式成立，即<math>F_k</math>和<math>F_{k+1}</math>此时都符合公式。<br />
 此时只需利用递推关系式继续分析<math>F_{k+2}</math>：<br />
 <math>
 \begin{array}{l}
	F_{k+2} = F_{k+1} + F_k \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{k+1} - (\frac{1 - \sqrt{5}}{2})^{k+1}) + \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k - (\frac{1 - \sqrt{5}}{2})^k) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{k+1} + (\frac{1 + \sqrt{5}}{2})^k - (\frac{1 + \sqrt{5}}{2})^{k+1} - (\frac{1 - \sqrt{5}}{2})^k) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k (\frac{1 + \sqrt{5}}{2} + 1) - (\frac{1 - \sqrt{5}}{2})^k (\frac{1 - \sqrt{5}}{2} + 1)) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k (\frac{3 + \sqrt{5}}{2}) - (\frac{1 - \sqrt{5}}{2})^k (\frac{3 - \sqrt{5}}{2})) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k (\frac{6 + 2 \sqrt{5}}{4}) - (\frac{1 - \sqrt{5}}{2})^k (\frac{6 - 2 \sqrt{5}}{4})) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k (\frac{1 + 2 \sqrt{5} + 5}{4}) - (\frac{1 - \sqrt{5}}{2})^k (\frac{1 - 2 \sqrt{5} + 5}{4})) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^k (\frac{1 + \sqrt{5}}{2})^2 - (\frac{1 - \sqrt{5}}{2})^k (\frac{1 - \sqrt{5}}{2})^2) \\
	= \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{k+2} - (\frac{1 - \sqrt{5}}{2})^{k+2})
 \end{array}
 </math><br />
 这说明<math>F_{k+2}</math>也会满足公式。<br />
 综合①、②、③可知，此通项公式对任何的<math>a_n \quad (n \in \mathbb{N}^+)</math>都成立。证明完毕。
 </p>
</div>
<div class="collapsible remarks" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>点评：从Fibonacci数列的通项公式可知：(1)整数数列的通项公式是有可能包含无理系数的；(2)Fibonacci数列与[[初中数学/几何/黄金分割率与数学神秘主义|黄金分割比例]]存在联系。</p>
</div>

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
Prove that <math>\sum_{i = 1}^n F_i^2 = F_n F_{n+1}</math> for all <math>n \in \mathbb{Z}_+</math>.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题3 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题3：
Show that for the Fibonacci numbers, <math>F_n F_{n+2} = F_{n+1}^2 + (-1)^{n+1}</math>.<ref name="upenn.edu_Alexandersson_ProofByInduction">{{cite web |url= https://www2.math.upenn.edu/~peal/files/Proof.by.Induction%5B2018%5D%5BEng%5D-ALEXANDERSSON.pdf |format=pdf |title=Proof by Induction |author=Per W. Alexandersson |publisher=[[w:宾夕法尼亚大学|University of Pennsylvania]] |language=en |date=2018 |access-date=2020年12月10日}}</ref>

<!-- 本小节例题4 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题4：
Let the "Tribonacci sequence" be defined by <math>T_1 = T_2 = T_3 = 1</math> and <math>T_n = T_{n-1} + T_{n-2} + T_{n-3}</math> for <math>n \ge 4</math>. Prove that <math>T_n < 2^n</math> for all <math>n \in \mathbb{Z}_+</math>.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题5 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题5：
Let <math>a_n</math> be the sequence defined by <math>a_1 = 1, a_2 = 8, a_n = a_{n-1} + 2 a_{n-2} \quad (n \ge 3)</math>. Prove that <math>a_n = 3 \cdot 2^{n-1} + 2 \cdot (-1)^n</math> for all <math>n \in \mathbb{Z}_+</math>.<ref name="Hildebrand_Math_213" />

<!-- 本小节例题6 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题6：
Show that for the Fibonacci numbers,<br />
(1) <math>gcd(F_{n+1}, F_n) = 1</math>;<br />
(2) <math>gcd(F_m, F_n) = F_{gcd(m, n)}</math> for <math>m, n > 0</math>.<ref name="upenn.edu_Alexandersson_ProofByInduction" />

<!-- 本小节例题7 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题7：
Let <math>p_0 = 1, p_1 = \cos \theta</math> (for <math>\theta</math> some fixed constant) and <math>p_{n+1} = 2 p_1 p_n - p_{n-1}</math> for <math>n \ge 1</math>. Use an extended Principle of Mathematical Induction to prove that <math>p_n = \cos (n \theta)</math> for <math>n \ge 0</math>.<ref name="umanitoba.ca_thomas" />

== 补充习题 ==
[[File:Crystal Clear app ksirtet.png | Crystal Clear app ksirtet | 50px]]
[[File:Crystal Clear app laptop battery.png | Crystal Clear app laptop battery | 50px]]
* 思考如何将勾股定理推广到<math>n \quad (n \ge 3, n \in \mathbb{N})</math>维欧氏空间并给予证明。
* 思考如何利用数学归纳法论证计算格点多边形面积的[[w:皮克定理|皮克定理]]。

== 参考资料 ==
{{Reflist}}

== 外部链接 ==
{{Wikipedia|数学归纳法}}
{{Wikipedia|递归}}

{{DEFAULTSORT: mathematical induction}}
[[category:数理逻辑]]
[[category:高中数学]]