高中數學/不等式與數列/數學歸納法

閱讀指南

希望快速了解或快速回顧高中數學的讀者可以只看基礎知識部分。其餘部分是為需要參加學科考試或需要一定知識提升的讀者準備的。

本節介紹的數學歸納法在數學的各個領域中都有重要作用，是一種通用性比較廣的代數證明方法，主要適用於證明對於正整數恆成立的相關命題。集合論中適用於超限數的超限歸納法是數學歸納法的重要推廣。作為定義自然數的主要（不是唯一的）公理化方式的皮亞諾公理也蘊含數學歸納法的思想。數學歸納法也會在學習極限時發揮很大作用。

預備知識

本節內容涉及函數迭代與數列遞推的概念，所以讀者應該先閱讀複合函數與一階遞推數列章節。

考試要求

在中國大陸高考中，數學歸納法曾是理科數學試卷的考查點之一，常用於解決大題中的結論證明，一般出題難度中等，是比較常用的代數證明方法。而對於高考取消文理分科考法的地區，目前並不將其納入必考知識範圍，只將其列為選學內容。不過由於數學歸納法簡單易學，並且是非常重要的代數證明方法，我們仍將其納入主幹知識的範圍。

基礎知識

知識引入

假設一個數列$\{a_{n}\}$的通項公式是$a_{n}=(n^{2}-5n+5)^{2}$，容易驗證此數列前4項的取值都是1，但是我們不能就此認為它的第5項也等於1。實際上容易驗證$a_{5}=25\neq 1$。這說明看上去可能成立的規律並非總是可靠。

再比如已知$a+b+c=1,a^{2}+b^{2}+c^{2}=2,a^{3}+b^{3}+c^{3}=3$，要求$a^{4}+b^{4}+c^{4}$的值。由於前3個式子的計算結果依次為1、2、3，首先最容易猜想第4個式子的結果有可能是4，但是再稍微想一想就會發現支持答案為4的理由並不明顯。事實上，這是一道需要使用多個多元等冪和公式求解的坑人題，而且其答案確實不是一開始最容易想到的4。如果繼續增加變量和已知算式的個數，這個題還可以變得更為迷惑人。總而言之，基於有限個特例得到的經驗並非總是可靠無誤。

又比如對於數列$\{b_{n}\}$，已知$b_{1}=1,b_{n+1}={\frac {b_{n}}{1+b_{n}}}\quad (n=1,2,3,...)$。通過對其前4項的計算，容易猜想其通項公式為$b_{n}={\frac {1}{n}}$。可以發現，這種與正整數n有關的命題，包含了無窮多種具體情況，如果逐一通過計算驗證顯然是不可能做到的。為此需要另想辦法，做到只通過有限多個步驟，證明n取所有正整數時命題都成立。而本節介紹的數學歸納法就是通過構建恆成立的遞推關係式來達到這個目的。當然對於這種特殊的分式線性遞推關係式，在後面的不動點法章節中還會繼續介紹其它求解方法。

普通數學歸納法的概念

證明一個與正整數n有關的命題，可以按下列步驟進行：

1. 歸納奠基（base case）：證明當n取第一個值$n_{0}\quad (n_{0}\in \mathbb {R} ^{+})$時命題成立；
2. 歸納遞推（induction step）：假設$n=k\quad (k>n_{0},k\in \mathbb {R} ^{+})$時命題成立，繼續證明當$n=k+1$時命題也成立。

只要完成這2個步驟，就可以斷定命題對於從$n_{0}$開始的所有正整數n都成立。
這個證明方法叫做數學歸納法（mathematical induction），簡稱「數歸法」（MI）。

數學歸納法可以用流程框圖表示為（在維基教科書輸入中文流程圖不方面，先將就着看吧……）：
$\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})$
$\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}\}$中，有$b_{1}=1,b_{n}={\frac {b_{n}}{b_{n}+1}}\quad (n\geq 1,n\in \mathbb {N} ^{+})$，使用數學歸納法證明：$b_{n}={\frac {1}{n}}$。

數學歸納法的論證思路藉助了多米諾骨牌效應。

一個與數學歸納法密切相關的生活實例是多米諾骨牌遊戲。可以看出，只要滿足以下2個條件，所有多米諾骨牌就都能倒下：

1. 保證第1個塊骨牌倒下；
2. 對於任意兩塊相鄰的骨牌，保證前一塊倒下時一定導致後一塊也倒下。

其遞推關係為：當第k塊倒下時，與其相鄰的第k+1塊也一定倒下。此時，只需要設法推倒第一塊骨牌，即可保證其它骨牌一定都會倒下。

數學歸納法是一種環環相扣的無限遞推的論證方法，其思路就像多米諾骨牌遊戲一樣，可以使一連串的無窮個命題依次地得到證明。其中每一環的論證都依賴於前一環的成功論證以及相鄰命題之間遞推關係的成立。這個證明過程中最重要的一步就是找到並證明相鄰命題之間遞推關係，也就是要將一個較大的問題設法化歸為（或者說遞歸地表達為）一個規模更小、更易解決的問題。

提示：某些版本的高中數學教材上還有介紹「不完全歸納法」與「完全歸納法」的概念，並指出數學歸納法是一種完全歸納法。由於這方面的介紹和討論只是枯燥的邏輯學問題，而不是數學問題，故我們學習數學時其實沒有必要了解什麼是不完全歸納法。

證明等式

相關例題1： 使用數學歸納法求證：$(x+1)^{n}=(x+1)+x(x+1)+x(x+1)^{2}+\cdots +x(x+1)^{n-1}$。

相關例題2： 使用數學歸納法求證下列等冪求和公式：
(1) $1+2+3+\cdots +n={\frac {n(1+n)}{2}}$。
(2) $1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}$。
(3) $1^{3}+2^{3}+3^{3}+\cdots +n^{3}=({\frac {n(n+1)}{2}})^{2}$。

相關例題3： 求證：$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)\quad (n\in \mathbb {N} ^{+})$。

相關例題5： 求證：$-1+3-5+...+(-1)^{n}(2n-1)=(-1)^{n}n$。

相關例題6： 求證：$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 $\sum _{i=1}^{n}\limits (2i-1)$ (i.e., the sum of the first n odd numbers), where $n\in \mathbb {Z} _{+}$.

相關例題8： 利用數學歸納法求證：
$(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\neq 0$ be a real number such that $x+x^{-1}\in \mathbb {Z}$. Prove that for any $n\in \mathbb {Z} ,x^{n}+x^{-n}\in \mathbb {Z}$.

相關例題10： Find and prove by induction a formula for $\prod _{i=2}^{n}\limits (1-{\frac {1}{i^{2}}})$, where $n\in \mathbb {Z} _{+}$ and $n\geq 2$.

相關例題11： Prove that $\sum _{i=1}^{n}\limits i\cdot (i!)=(n+1)!-1$.

相關例題12： Prove that $\prod _{i=1}^{n}\limits {\frac {i^{2}}{i+1}}={\frac {n!}{n+1}}$.

相關例題13： 求證韋達定理對n次實系數方程成立。（如果不知道代數基本定理，可以只考慮有n個實數根的n次方程的情況。）

相關例題14： 設正數$w_{1}$為數字a的權重值，正數$w_{2}$為數字b的權重值，若定義2個數a和b的加權平均數為${\frac {w_{1}a+w_{2}b}{w_{1}+w_{2}}}$，求證n個數的加權平均數計算公式為：
${\frac {w_{1}x_{1}+w_{2}x_{2}+...+w_{n}x_{n}}{w_{1}+w_{2}+...+w_{n}}}$
其中各個正數$w_{i}$分別是下標對應的數字$x_{i}$的權重值。

相關例題15： 使用數學歸納法證明等冪和公式：
$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 has $2^{n}$ subsets.

相關例題17： Number of 2-element subsets: Show that a set of n elements has ${\frac {n(n-1)}{2}}$ subsets with 2 elements. (Take n = 2 as the base case.)

相關例題18： Generalization of De Morgan's Law to unions of n sets. Show that if $A_{1},A_{2},...,A_{n}$ are sets, then
${\overline {A_{1}\cup ...\cup A_{n}}}={\overline {A_{1}}}\cap ...\cap {\overline {A_{n}}}$.

常用結論與常見模型

簡單的整除性問題

相關例題1： 求證：形如$n^{3}+5n\quad (n\in \mathbb {N} ^{+})$的數總能夠被6整除。

相關例題2： 求證：形如$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$ is divisible by 5.

參數求值問題

相關例題1： 求使得關係式$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\in \mathbb {N} ^{+}$，$3^{4n+2}+a^{2n+1}$都能被14整除，求a可以取的最小自然數。

抽象推理

相關例題1： 已知函數$f(x)$滿足$f(xy)=f(x)+f(y)$，利用數學歸納法證明$f(x^{n})=nf(x)\quad (n\in \mathbb {N} ^{+})$。

證明：
①令y = 1，則有$f(x)=f(x)+f(1)$，即$f(1)=0$。即在此情況下，結論成立。
②假設n = k時，有$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)$
所以當n = k+1時，結論也成立。
綜合①、②可知，原結論成立。

相關例題2： 設$f(n)=1+{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n}}$，是否存在$g(n)$使得等式$f(1)+f(2)+...+f(n-1)=g(n)f(n)-g(n)$對滿足$n\geq 2$的一切自然數n成立？使用數學歸納法證明這個結論。

幾何問題

相關例題1： 求證$n\quad (n\geq 3,n\in \mathbb {N} )$邊形的內角和公式為$(n-2)\times 180^{\circ }$。

相關例題2： 利用多邊形三角剖分（polygon triangulation）思想，求證計算平面$n\quad (n\geq 3,n\in \mathbb {N} )$邊形面積A的高斯鞋帶公式（shoelace formula）： ${\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})$依次是n邊形的各個頂點。

提示：鞋帶公式也可以被視為微積分學中格林公式的離散化版本。

相關例題3： 平面多邊形X可以被剖分為n個有限的簡單圖形$X_{1},X_{2},...,X_{n}$，這些簡單圖形的重心坐標依次為$(C_{1x},C_{1y}),(C_{2x},C_{2y}),...,(C_{nx},C_{ny})$，面積依次為$A_{1},A_{2},...,A_{n}$。
(1) 根據重心的定義，求證這個平面多邊形的整體重心坐標$(C_{x},C_{y})$可計算如下：
$\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\quad (n\geq 3,n\in \mathbb {N} )$邊形的各個頂點坐標依次為$(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})$。利用多邊形三角剖分思想和鞋帶公式，求證其重心坐標公式為：
$\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有關的命題，但其論證步驟變為：

1. 歸納奠基（base case）：證明當n取第一個值$n_{0}\quad (n_{0}\in \mathbb {R} ^{+})$時命題成立；
2. 歸納遞推（induction step）：假設$n<k\quad (k>n_{0},k\in \mathbb {R} ^{+})$時命題成立，繼續證明當$n=k$時命題也成立。

只要完成這2個步驟，就可以斷定命題對於從$n_{0}$開始的所有正整數n都成立。

我們知道，使用普通數學歸納法的重點和難點是要將一個較大的問題設法化歸為（或者說遞歸地表達為）一個規模更小、更易解決的問題。但是有時候，將一個較大的問題設法化歸為（或者說遞歸地表達為）有限多個規模更小、更易解決的問題會更容易。這時就要用到強數學歸納法。換句話說，如果一個問題更容易轉換為多個小規模的相似子問題解決，而不是只轉換為一個小規模的相似子問題解決，則適合考慮使用強數學歸納法。從另一個角度而言，強數學歸納法適合解決涉及二階和更高階的遞推關係的性質證明。

相關例題1： Consider the famous Fibonacci sequence $\{F_{n}\}_{n=1}^{\infty }$, defined by the relations $F_{1}=1,F_{2}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 3$. Use an extended Priciple of Mathematical Induction in order to show that for $n\geq 1$, $F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})$.
考慮由遞推關係$F_{1}=1,F_{2}=1,F_{n}=F_{n-1}+F_{n-2}\quad (n\geq 3)$定義的知名的Fibonacci數列。使用數學歸納法證明它有如下通項公式： $F_{n}={\frac {1}{\sqrt {5}}}(({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n})$

證明：
①當n = 1時，公式可以驗證如下：
${\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時，公式可以驗證如下：
${\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\quad (k\geq 1)$時，公式成立，即$F_{k}$和$F_{k+1}$此時都符合公式。
此時只需利用遞推關係式繼續分析$F_{k+2}$：
${\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}$也會滿足公式。
綜合①、②、③可知，此通項公式對任何的$a_{n}\quad (n\in \mathbb {N} ^{+})$都成立。證明完畢。

點評：從Fibonacci數列的通項公式可知：(1)整數數列的通項公式是有可能包含無理系數的；(2)Fibonacci數列與黃金分割比例存在聯繫。

相關例題2： Prove that $\sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}$ for all $n\in \mathbb {Z} _{+}$.

相關例題3： Show that for the Fibonacci numbers, $F_{n}F_{n+2}=F_{n+1}^{2}+(-1)^{n+1}$.

相關例題4： Let the "Tribonacci sequence" be defined by $T_{1}=T_{2}=T_{3}=1$ and $T_{n}=T_{n-1}+T_{n-2}+T_{n-3}$ for $n\geq 4$. Prove that $T_{n}<2^{n}$ for all $n\in \mathbb {Z} _{+}$.

相關例題5： Let $a_{n}$ be the sequence defined by $a_{1}=1,a_{2}=8,a_{n}=a_{n-1}+2a_{n-2}\quad (n\geq 3)$. Prove that $a_{n}=3\cdot 2^{n-1}+2\cdot (-1)^{n}$ for all $n\in \mathbb {Z} _{+}$.

相關例題6： Show that for the Fibonacci numbers,
(1) $gcd(F_{n+1},F_{n})=1$;
(2) $gcd(F_{m},F_{n})=F_{gcd(m,n)}$ for $m,n>0$.

相關例題7： Let $p_{0}=1,p_{1}=\cos \theta$ (for $\theta$ some fixed constant) and $p_{n+1}=2p_{1}p_{n}-p_{n-1}$ for $n\geq 1$. Use an extended Principle of Mathematical Induction to prove that $p_{n}=\cos(n\theta )$ for $n\geq 0$.

補充習題

• 思考如何將勾股定理推廣到$n\quad (n\geq 3,n\in \mathbb {N} )$維歐氏空間並給予證明。
• 思考如何利用數學歸納法論證計算格點多邊形面積的皮克定理。

外部連結

維基百科中的相關條目：

數學歸納法

維基百科中的相關條目：

遞歸