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

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

本节内容涉及函数迭代与数列递推的概念，所以读者应该先阅读复合函数与一阶递推数列章节。

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

假设一个数列{ a n } {\displaystyle \{a_{n}\}} 的通项公式是 a n =( n 2 −5n+5 ) 2{\displaystyle a_{n}=(n^{2}-5n+5)^{2}} ，容易验证此数列前4项的取值都是1，但是我们不能就此认为它的第5项也等于1。实际上容易验证 a 5 =25≠1 {\displaystyle a_{5}=25\neq 1} 。这说明看上去可能成立的规律并非总是可靠。[1]

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

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

证明一个与正整数n有关的命题，可以按下列步骤进行：

只要完成这2个步骤，就可以断定命题对于从 n 0{\displaystyle n_{0}} 开始的所有正整数n都成立。这个证明方法叫做数学归纳法（mathematical induction）[1][2]，简称“数归法”（MI）。

数学归纳法可以用流程框图表示为[2]（在维基教科书输入中文流程图不方面，先将就着看吧……）： prove that the proposition holds for n = n 0 given the proposition holds for n = k ( k ≥ n 0) , prove it still holds when n = k + 1 }⇒ the proposition holds for all n  (n≥ n 0 ) {\displaystyle \left.{\begin{array}{l}{\mbox{prove that the proposition holds for n = }}n_{0}\\{\mbox{given the proposition holds for n = k}}\quad (k\geq n_{0}),{\mbox{ prove it still holds when }}n=k+1\end{array}}\right\}\Rightarrow {\mbox{the proposition holds for all n }}\quad (n\geq n_{0})} 归纳奠基：简单验证   n = n 0 时命题成立 归纳递推：假设   n = k( k ≥ n 0)时命题成立，证明n = k+1时命题也成立}⇒ 命题对从    n 0开始的所有正整数n都成立    {\displaystyle \left.{\begin{array}{l}{\mbox{归纳奠基：简单验证}}\ n=n_{0}{\mbox{时命题成立}}\\{\mbox{归纳递推：假设}}\ n=k\quad (k\geq n_{0}){\mbox{时命题成立，证明n = k+1时命题也成立}}\end{array}}\right\}\Rightarrow {\mbox{命题对从}}\ n_{0}{\mbox{开始的所有正整数n都成立}}\ }

相关例题：已知在数列{ b n } {\displaystyle \{b_{n}\}} 中，有 b 1 =1, b n =b nb n+ 1 (n≥1,n∈ N+ ) {\displaystyle b_{1}=1,b_{n}={\frac {b_{n}}{b_{n}+1}}\quad (n\geq 1,n\in \mathbb {N} ^{+})} ，使用数学归纳法证明： b n = 1n{\displaystyle b_{n}={\frac {1}{n}}} 。

一个与数学归纳法密切相关的生活实例是多米诺骨牌游戏。可以看出，只要满足以下2个条件，所有多米诺骨牌就都能倒下[2]：

其递推关系为：当第k块倒下时，与其相邻的第k+1块也一定倒下。此时，只需要设法推倒第一块骨牌，即可保证其它骨牌一定都会倒下。

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

提示：某些版本的高中数学教材上还有介绍“不完全归纳法”与“完全归纳法”的概念，并指出数学归纳法是一种完全归纳法[1]。由于这方面的介绍和讨论只是枯燥的逻辑学问题，而不是数学问题，故我们学习数学时其实没有必要了解什么是不完全归纳法。

相关例题1：使用数学归纳法求证：(x+1 ) n =(x+1)+x(x+1)+x(x+1 ) 2 +⋯+x(x+1 ) n−1{\displaystyle (x+1)^{n}=(x+1)+x(x+1)+x(x+1)^{2}+\cdots +x(x+1)^{n-1}} 。

相关例题2：使用数学归纳法求证下列等幂求和公式：(1) 1+2+3+⋯+n=n ( 1 + n )2{\displaystyle 1+2+3+\cdots +n={\frac {n(1+n)}{2}}} 。(2)1 2 + 2 2 + 3 2 +⋯+ n 2 =n ( n + 1 ) ( 2 n + 1 )6{\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}} 。(3)1 3 + 2 3 + 3 3 +⋯+ n 3 =(n ( n + 1 )2) 2{\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=({\frac {n(n+1)}{2}})^{2}} 。

相关例题3：求证：1×4+2×7+3×10+...+n(3n+1)=n(n+1 ) 3 (n∈ N+ ) {\displaystyle 1\times 4+2\times 7+3\times 10+...+n(3n+1)=n(n+1)^{3}\quad (n\in \mathbb {N} ^{+})} 。

相关例题4：求证： 1 2 − 2 2 + 3 2 − 4 2 +...+(2n−1 ) 2 −(2n ) 2 =−n(2n+1)(n∈ N+ ) {\displaystyle 1^{2}-2^{2}+3^{2}-4^{2}+...+(2n-1)^{2}-(2n)^{2}=-n(2n+1)\quad (n\in \mathbb {N} ^{+})} 。

相关例题5：求证：−1+3−5+...+(−1 ) n (2n−1)=(−1 ) n n {\displaystyle -1+3-5+...+(-1)^{n}(2n-1)=(-1)^{n}n} 。

相关例题6：求证：1×n+2×(n−1)+3×(n−2)+...+n×1=n ( n + 1 ) ( n + 2 )6{\displaystyle 1\times n+2\times (n-1)+3\times (n-2)+...+n\times 1={\frac {n(n+1)(n+2)}{6}}} 。

相关例题7：Find and prove by induction a formula for∑ i=1n (2i−1) {\displaystyle \sum _{i=1}^{n}\limits (2i-1)} (i.e., the sum of the first n odd numbers), where n∈ Z+{\displaystyle n\in \mathbb {Z} _{+}} .[3]

相关例题8：利用数学归纳法求证：(1⋅ 2 2 −2⋅ 3 2 )+(3⋅ 4 2 −4⋅ 5 2 )+...+((2n−1)⋅(2n ) 2 −2n⋅(2n+1 ) 2 )=−n(n+1)(4n+3) {\displaystyle (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)}

相关例题9：Let x≠0 {\displaystyle x\neq 0} be a real number such that x+ x −1 ∈ Z {\displaystyle x+x^{-1}\in \mathbb {Z} } . Prove that for any n∈ Z, x n + x −n ∈ Z {\displaystyle n\in \mathbb {Z} ,x^{n}+x^{-n}\in \mathbb {Z} } .[4]

相关例题10：Find and prove by induction a formula for∏ i=2n (1− 1 i 2) {\displaystyle \prod _{i=2}^{n}\limits (1-{\frac {1}{i^{2}}})} , where n∈ Z+{\displaystyle n\in \mathbb {Z} _{+}} and n≥2 {\displaystyle n\geq 2} .[3]

相关例题11：Prove that∑ i=1n i⋅(i!)=(n+1)!−1 {\displaystyle \sum _{i=1}^{n}\limits i\cdot (i!)=(n+1)!-1} .[4]

相关例题12：Prove that∏ i=1n i 2i + 1 =n ! n + 1{\displaystyle \prod _{i=1}^{n}\limits {\frac {i^{2}}{i+1}}={\frac {n!}{n+1}}} .[4]

相关例题13：求证韦达定理对n次实系数方程成立。（如果不知道代数基本定理，可以只考虑有n个实数根的n次方程的情况。）

相关例题14：设正数 w 1{\displaystyle w_{1}} 为数字a的权重值，正数 w 2{\displaystyle w_{2}} 为数字b的权重值，若定义2个数a和b的加权平均数为w 1a + w 2b w 1+ w 2 {\displaystyle {\frac {w_{1}a+w_{2}b}{w_{1}+w_{2}}}} ，求证n个数的加权平均数计算公式为：w 1x 1+ w 2x 2+ . . . + w nx nw 1+ w 2+ . . . + w n {\displaystyle {\frac {w_{1}x_{1}+w_{2}x_{2}+...+w_{n}x_{n}}{w_{1}+w_{2}+...+w_{n}}}} 其中各个正数 w i{\displaystyle w_{i}} 分别是下标对应的数字 x i{\displaystyle x_{i}} 的权重值。

相关例题15：使用数学归纳法证明等幂和公式： a n − b n =(a−b) ∑ r=1na n−rb r−1 =(a−b)( a n−1 + a n−2 b+...+ b n−1 ) {\displaystyle 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})}

相关例题16：Number of subsets: Show that a set of n elements has2 n{\displaystyle 2^{n}} subsets.[3]

相关例题17：Number of 2-element subsets: Show that a set of n elements has n ( n − 1 )2{\displaystyle {\frac {n(n-1)}{2}}} subsets with 2 elements. (Take n = 2 as the base case.)[3]

相关例题18：Generalization of De Morgan's Law to unions of n sets. Show that ifA 1 , A 2 ,..., A n{\displaystyle A_{1},A_{2},...,A_{n}} are sets, thenA 1∪ . . . ∪ A n ¯ =A 1 ¯ ∩...∩A n ¯{\displaystyle {\overline {A_{1}\cup ...\cup A_{n}}}={\overline {A_{1}}}\cap ...\cap {\overline {A_{n}}}} .[3]

相关例题1：求证：形如 n 3 +5n(n∈ N+ ) {\displaystyle n^{3}+5n\quad (n\in \mathbb {N} ^{+})} 的数总能够被6整除。

相关例题2：求证：形如 8 n − 3 n (n∈ N+ ) {\displaystyle 8^{n}-3^{n}\quad (n\in \mathbb {N} ^{+})} 的数总能够被5整除。

相关例题3：Use the Principle of Mathematical Induction to verify that, for n any positive integer,6 n −1 {\displaystyle 6^{n}-1} is divisible by 5.[5]

相关例题1：求使得关系式1×2+4×3+9×4+⋯+ n 2 (n+1)= nm (n+1)(n+2)(3n+1) {\displaystyle 1\times 2+4\times 3+9\times 4+\cdots +n^{2}(n+1)={\frac {n}{m}}(n+1)(n+2)(3n+1)} 恒成立的m的取值。

相关例题2：如果对于任意的n∈ N+{\displaystyle n\in \mathbb {N} ^{+}} ， 3 4n+2 + a 2n+1{\displaystyle 3^{4n+2}+a^{2n+1}} 都能被14整除，求a可以取的最小自然数。

相关例题1：已知函数f(x) {\displaystyle f(x)} 满足f(xy)=f(x)+f(y) {\displaystyle f(xy)=f(x)+f(y)} ，利用数学归纳法证明f( x n )=nf(x)(n∈ N+ ) {\displaystyle f(x^{n})=nf(x)\quad (n\in \mathbb {N} ^{+})} 。

证明： ①令y = 1，则有f(x)=f(x)+f(1) {\displaystyle f(x)=f(x)+f(1)} ，即f(1)=0 {\displaystyle f(1)=0} 。即在此情况下，结论成立。 ②假设n = k时，有f( x k )=kf(x) {\displaystyle f(x^{k})=kf(x)} 。则当n = k+1时，有： f( x k+1 )=f( x k ∗x)=f( x k )+f(x)=kf(x)+f(x)=(k+1)f(x) {\displaystyle f(x^{k+1})=f(x^{k}*x)=f(x^{k})+f(x)=kf(x)+f(x)=(k+1)f(x)} 所以当n = k+1时，结论也成立。 综合①、②可知，原结论成立。

相关例题2：设f(n)=1+ 12 + 13 +...+ 1n{\displaystyle f(n)=1+{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n}}} ，是否存在g(n) {\displaystyle g(n)} 使得等式f(1)+f(2)+...+f(n−1)=g(n)f(n)−g(n) {\displaystyle f(1)+f(2)+...+f(n-1)=g(n)f(n)-g(n)} 对满足n≥2 {\displaystyle n\geq 2} 的一切自然数n成立？使用数学归纳法证明这个结论。

相关例题1：求证n(n≥3,n∈ N) {\displaystyle n\quad (n\geq 3,n\in \mathbb {N} )} 边形的内角和公式为(n−2)× 180 ∘{\displaystyle (n-2)\times 180^{\circ }} 。

相关例题2：利用多边形三角剖分（polygon triangulation）思想，求证计算平面n(n≥3,n∈ N) {\displaystyle n\quad (n\geq 3,n\in \mathbb {N} )} 边形面积A的高斯鞋带公式（shoelace formula）： A= 12|∑ i=1n−1x iy i+1 + x ny 1 − ∑ i=1n−1x i+1y i − x 1y n | = 12| x 1y 2 + x 2y 3 +⋯+ x n−1y n + x ny 1 − x 2y 1 − x 3y 2 −⋯− x ny n−1 − x 1y n| {\displaystyle {\begin{aligned}\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{aligned}}} 其中( x 1 , y 1 ),( x 2 , y 2 ),...,( x n , y n ) {\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})} 依次是n边形的各个顶点。

提示：鞋带公式也可以被视为微积分学中格林公式的离散化版本。

相关例题3：平面多边形X可以被剖分为n个有限的简单图形 X 1 , X 2 ,..., X n{\displaystyle X_{1},X_{2},...,X_{n}} ，这些简单图形的重心坐标依次为( C 1x , C 1y ),( C 2x , C 2y ),...,( C nx , C ny ) {\displaystyle (C_{1x},C_{1y}),(C_{2x},C_{2y}),...,(C_{nx},C_{ny})} ，面积依次为 A 1 , A 2 ,..., A n{\displaystyle A_{1},A_{2},...,A_{n}} 。(1) 根据重心的定义，求证这个平面多边形的整体重心坐标( C x , C y ) {\displaystyle (C_{x},C_{y})} 可计算如下： { C x=∑ Ci x A i ∑ A i= C 1xA 1 + C 2xA 2 +...+ C nxA nA 1 + A 2 +...+ A nC y=∑ Ci y A i ∑ A i= C 1yA 1 + C 2yA 2 +...+ C nyA nA 1 + A 2 +...+ A n {\displaystyle \left\{{\begin{aligned}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{aligned}}\right.} (2) 若一个正n(n≥3,n∈ N) {\displaystyle n\quad (n\geq 3,n\in \mathbb {N} )} 边形的各个顶点坐标依次为( x 1 , y 1 ),( x 2 , y 2 ),...,( x n , y n ) {\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})} 。利用多边形三角剖分思想和鞋带公式，求证其重心坐标公式为： { C x=1 6A ∑ i = 1 n( x i+ x i + 1) ( x iy i + 1− x i + 1y i) C y=1 6A ∑ i = 1 n( y i+ y i + 1) ( x iy i + 1− x i + 1y i){\displaystyle \left\{{\begin{aligned}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{aligned}}\right.}

强归纳法（strong induction）也叫完整数学归纳法（complete induction）或第二数学归纳法，是普通数学归纳法的最常用的变体。它仍用于证明与正整数n有关的命题，但其论证步骤变为：

只要完成这2个步骤，就可以断定命题对于从 n 0{\displaystyle n_{0}} 开始的所有正整数n都成立。

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

相关例题1：Consider the famous Fibonacci sequence { F n} n=1∞{\displaystyle \{F_{n}\}_{n=1}^{\infty }} , defined by the relationsF 1 =1, F 2 =1 {\displaystyle F_{1}=1,F_{2}=1} , andF n = F n−1 + F n−2{\displaystyle F_{n}=F_{n-1}+F_{n-2}} for n≥3 {\displaystyle n\geq 3} .Use an extended Priciple of Mathematical Induction in order to show that for n≥1 {\displaystyle n\geq 1} ,F n = 1 5 ((1 +5 2) n −(1 −5 2) n ) {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})} .[5]考虑由递推关系 F 1 =1, F 2 =1, F n = F n−1 + F n−2 (n≥3) {\displaystyle F_{1}=1,F_{2}=1,F_{n}=F_{n-1}+F_{n-2}\quad (n\geq 3)} 定义的知名的Fibonacci数列。使用数学归纳法证明它有如下通项公式： F n = 1 5 ((1 +5 2) n −(1 −5 2) n ) {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})}

证明： ①当n = 1时，公式可以验证如下：F 1 = 1 5 ((1 +5 2) 1 −(1 −5 2) 1 )= 1 5 (1 +5 2 −1 −5 2 )= 1 5 (1 +5− 1 +5 2 )= 1 5 (25 2 )=1 {\displaystyle {\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}}} ②当n = 2时，公式可以验证如下：F 2 = 1 5 ((1 +5 2) 2 −(1 −5 2) 2 )= 1 5 (1 + 25+ 54 −1 − 25+ 54 )= 1 5 (1 + 25+ 5 − 1 + 25− 54 )= 1 5 (45 4 )=1 {\displaystyle {\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}}} ③假设当n=k,k+1(k≥1) {\displaystyle n=k,k+1\quad (k\geq 1)} 时，公式成立，即 F k{\displaystyle F_{k}} 和 F k+1{\displaystyle F_{k+1}} 此时都符合公式。 此时只需利用递推关系式继续分析 F k+2{\displaystyle F_{k+2}} ：F k+2 = F k+1 + F k = 1 5 ((1 +5 2) k+1 −(1 −5 2) k+1 )+ 1 5 ((1 +5 2) k −(1 −5 2) k )= 1 5 ((1 +5 2) k+1 +(1 +5 2) k −(1 +5 2) k+1 −(1 −5 2) k )= 1 5 ((1 +5 2) k (1 +5 2 +1)−(1 −5 2) k (1 −5 2 +1))= 1 5 ((1 +5 2) k (3 +5 2 )−(1 −5 2) k (3 −5 2 ))= 1 5 ((1 +5 2) k (6 + 25 4 )−(1 −5 2) k (6 − 25 4 ))= 1 5 ((1 +5 2) k (1 + 25+ 54 )−(1 −5 2) k (1 − 25+ 54 ))= 1 5 ((1 +5 2) k (1 +5 2) 2 −(1 −5 2) k (1 −5 2) 2 )= 1 5 ((1 +5 2) k+2 −(1 −5 2) k+2 ) {\displaystyle {\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}}} 这说明 F k+2{\displaystyle F_{k+2}} 也会满足公式。 综合①、②、③可知，此通项公式对任何的 a n (n∈ N+ ) {\displaystyle a_{n}\quad (n\in \mathbb {N} ^{+})} 都成立。证明完毕。

点评：从Fibonacci数列的通项公式可知：(1)整数数列的通项公式是有可能包含无理系数的；(2)Fibonacci数列与黄金分割比例存在联系。

相关例题2：Prove that∑ i=1nF i2 = F nF n+1{\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}} for all n∈ Z+{\displaystyle n\in \mathbb {Z} _{+}} .[3]

相关例题3：Show that for the Fibonacci numbers,F nF n+2 = F n+12 +(−1 ) n+1{\displaystyle F_{n}F_{n+2}=F_{n+1}^{2}+(-1)^{n+1}} .[4]

相关例题4：Let the "Tribonacci sequence" be defined byT 1 = T 2 = T 3 =1 {\displaystyle T_{1}=T_{2}=T_{3}=1} andT n = T n−1 + T n−2 + T n−3{\displaystyle T_{n}=T_{n-1}+T_{n-2}+T_{n-3}} for n≥4 {\displaystyle n\geq 4} . Prove thatT n 0 {\displaystyle m,n>0} .[4]

相关例题7：Letp 0 =1, p 1 =cos⁡θ {\displaystyle p_{0}=1,p_{1}=\cos \theta } (for θ {\displaystyle \theta } some fixed constant) andp n+1 =2 p 1p n − p n−1{\displaystyle p_{n+1}=2p_{1}p_{n}-p_{n-1}} for n≥1 {\displaystyle n\geq 1} . Use an extended Principle of Mathematical Induction to prove thatp n =cos⁡(nθ) {\displaystyle p_{n}=\cos(n\theta )} for n≥0 {\displaystyle n\geq 0} .[5]