數學證明/證明方法/歸納法

歸納法的魅力在於，它允許我們在存在無限多個情況的情況下證明一個定理是正確的，而無需單獨考察每個情況。歸納法類似於一排無限長的多米諾骨牌，每個骨牌都立著。如果你想讓所有的多米諾骨牌都倒下，你可以：

1. 推倒第一個骨牌，等待結果，然後逐個檢查後面的骨牌（如果骨牌數量無限多，這可能需要很長時間！）
2. 或者你可以證明，如果任何一個骨牌倒下，它就會導致它後面的骨牌倒下。（即，如果第一個倒下，那麼第二個就會倒下，如果第二個倒下，那麼第三個就會倒下，等等。）

歸納法本質上是第二點中概述的方法。

歸納法的組成部分

歸納法由三個部分組成

1. 基本情況（在多米諾骨牌的類比中，這表明第一個骨牌會倒下）
2. 歸納假設（在多米諾骨牌的類比中，我們假設某個特定骨牌會倒下）
3. 歸納步驟（在多米諾骨牌的類比中，我們證明我們假設會倒下的骨牌會使下一個骨牌倒下）

弱歸納法

弱歸納法用於證明給定的性質對可數歸納集中的所有成員成立，這通常用於自然數集。

弱歸納法用於證明一個陳述$P(n)$（它取決於$n$）依賴於兩個步驟

• $P(n)$對某個基本情況成立。通常基本情況是$n=1$或$n=0$

• $P(k)\to P(k+1)$。也就是說，如果$P(k)$成立，那麼$P(k+1)$也成立。

如果這兩個性質成立，那麼就可以推斷該性質對該集合中的所有元素都成立。回到例子中，如果你確定你給你的鄰居打了電話，並且你知道每個接到電話的人都會給他們的鄰居打電話，那麼你就能保證這個街區上每個人都接到了電話（假設你的街區是直線形的，或者曲線很好看）。

例子

歸納法證明的第一個例子總是“前n項的和：”

定理 2.4.1. 對於任何固定的$n\in \mathbb {N} ,$ $\sum _{i=1}^{n}{i}={\frac {n(n+1)}{2}}$

證明

• 基本情況：$1={\frac {1\cdot 2}{2}}$，因此基本情況成立。

• 假設$\sum _{i=0}^{n}i={\frac {n(n+1)}{2}}$。考慮$\sum _{i=1}^{n+1}i$。

${\begin{aligned}\sum _{i=1}^{n+1}i&=\sum _{i=1}^{n}i+(n+1)={\frac {n(n+1)}{2}}+n+1\\&=\left({\frac {n}{2}}+1\right)(n+1)\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1){\big (}(n+1)+1{\big )}}{2}}\end{aligned}}$

因此，歸納步驟成立。現在透過歸納法，我們看到該定理是正確的。

逆向歸納法

逆向歸納法是一種使用歸納步驟中負數的歸納方法。它是弱歸納法的一個小變種。該過程仍然只適用於可數集，通常是全數集或整數集，並且通常會在 1 或 0 處停止，而不是適用於所有正數。

逆向歸納法在以下情況下有效。

• 該性質對於一個給定值成立，比如$M$。

• 假設該性質對於一個給定情況成立，比如$n=k+1$，證明該性質對於$n=k$成立。

那麼該性質對於所有值$n\leq M$成立。

逆向歸納法也適用於一般情況: “為了建立命題序列$P(n)\ (n\geq 1)$的有效性，只需建立以下幾點

(a) $P(n)$對於無限多個$n$成立。

(b) 如果$P(n+1)$成立，那麼$P(n)$也成立。

我們可以很容易地證明 $P(1)$ ，並且如果 $P$ 對 $n=m$ 成立，那麼 $P$ 對 $n=2m$ 也成立。在這種情況下，我們有（a）對於無窮多個 $n=2^{k}\ (k\geq 0)$ 。

強歸納法

在弱歸納法中，對於歸納步驟，我們只需要對於給定的 $n$ ，其直接前驅 $n-1$ 滿足定理（即 $P(n-1)$ 為真）。在強歸納法中，我們要求不僅直接前驅，而且 $n$ 的所有前驅都滿足定理。歸納步驟的變動是

• 如果 $P(k)$ 對所有 $k<n$ 成立，那麼 $P(n)$ 為真。

這種方法被稱為強歸納法的原因相當明顯——歸納步驟中的假設比弱歸納法中的假設要強得多。當然，對於有限歸納法，它最終是相同的假設，但在超限集的情況下，弱歸納法甚至沒有定義，因為一些集合存在沒有直接前驅的元素。

超限歸納法

用於證明涉及超限基數的定理。這種技術在集合論中用於證明基數的性質，因為很少有其他方法可以做到這一點。

歸納集

我們首先定義*良序*集的概念。一個集合$X$是*良序*的，如果存在一個全序$<$在$X$上，並且只要$Y\subset X$是非空的，$Y$中存在一個*最小元素*。也就是說，$\exists p\in Y$使得$p<q\ \forall q\in Y$。

*歸納集*是一個集合$A\subset X$，滿足以下條件

1. $\alpha \in A$（其中$\alpha$是$X$的最小元素）
2. 如果$\beta \in A$，那麼$\forall \gamma \in X$，使得$\beta <\gamma ,\gamma \in A$

當然，你會看到這一點並說：“等等。這意味著$A=X$！” 當然，你說得對。這正是歸納法起作用的原因。歸納原理是這個定理：它說

定理 2.4.2. 如果$X$是一個非空的良序集，並且$A\subset X$是$X$的歸納子集，那麼$A=X$。

這個定理的證明留作一個非常簡單的練習。這裡我們注意到自然數集顯然是良序的，具有您所熟悉的正常順序，因此$\mathbb {N}$是一個歸納集。如果您接受選擇公理，那麼每個集合都可以被良序化。

練習

證明對於每個正整數：$1+\cdots +n={\frac {n(n+1)}{2}}$

首先，我們證明當 $n=1$ 時成立。

$1={\frac {1(1+1)}{2}}$

假設該等式對某個數 $n=k$ 成立，那麼

$1+\cdots +k={\frac {k(k+1)}{2}}$

我們的目標是證明

$1+\cdots +(k+1)={\frac {(k+1)(k+2)}{2}}$

由此得出

${\begin{aligned}(1+\cdots +k)+(k+1)&={\frac {k(k+1)}{2}}+(k+1)\\&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\end{aligned}}$

這就是我們要證明的。由於該等式對 1 成立，它也對 2 成立，並且由於它對 3 成立，依此類推。

證明對於每個正整數：$1^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}$

首先，我們證明當 $n=1$ 時成立。

$1^{2}={\frac {1(1+1)(2+1)}{6}}$

假設該等式對 $n=k$ 成立。那麼

$1^{2}+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$

我們的目標是證明

$1^{2}+\cdots +(k+1)^{2}={\frac {(k+1)(k+2)(2k+3)}{6}}$

由此得出

${\begin{aligned}(1^{2}+\cdots +k^{2})+(k+1)^{2}&={\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}\\&={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}\\&={\frac {(k+1){\big [}k(2k+1)+6(k+1){\big ]}}{6}}\\&={\frac {(k+1)(2k^{2}+k+6k+6)}{6}}\\&={\frac {(k+1)(2k^{2}+7k+6)}{6}}\\&={\frac {(k+1)(k+2)(2k+3)}{6}}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數：$1^{3}+\cdots +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}$

首先，我們證明當 $n=1$ 時成立。

${\begin{aligned}1^{3}=1\\\left({\frac {1(1+1)}{2}}\right)^{2}=1\end{aligned}}$

假設它對$n=k$ 成立。然後，

$1^{3}+\cdots +k^{3}=\left({\frac {k(k+1)}{2}}\right)^{2}$

由此得出

${\begin{aligned}(1^{3}+\cdots +k^{3})+(k+1)^{3}&=\left({\frac {k(k+1)}{2}}\right)^{2}+(k+1)^{3}\\&=(k+1)^{2}\left(\left({\frac {k}{2}}\right)^{2}+(k+1)\right)\\&={\frac {(k+1)^{2}(k^{2}+4k+4)}{4}}\\&=\left({\frac {(k+1)(k+2)}{2}}\right)^{2}\end{aligned}}$

我們已經證明，如果對於$n=k$ 成立，那麼對於$n=k+1$ 也成立。現在對於 1 成立（顯然）。因此對於所有整數都成立。

證明對於$n\geq 4$，$n!>2^{n}$。

當$n=4$ 時，結論成立。

$4!>2^{4}\ \Rightarrow \ 24>16$

現在假設對於$n=k\geq 4$ 成立。那麼，

$k!>2^{k}$

由此得出

${\begin{aligned}(k+1)k!&>(k+1)2^{k}>2^{k+1}\\(k+1)!&>2^{k+1}\end{aligned}}$

我們已經證明，如果對於$n=k$ 成立，那麼對於$n=k+1$ 也成立。由於對於 4 成立，因此對於所有整數$n\geq 4$ 都成立。

證明對於每個正整數，$2+4+6+\cdots +2n=n(n+1)$

首先，我們證明當 $n=1$ 時成立。

$2=1(1+1)$

假設該等式對 $n=k$ 成立。那麼

$2+4+6+\cdots +2k=k(k+1)$

我們的目標是證明

$2+4+6+\cdots +2(k+1)=(k+1)(k+2)$

由此得出

${\begin{aligned}(2+4+6+\cdots +2k)+2(k+1)&=k(k+1)+2(k+1)\\&=(k+1)(k+2)\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數：$1+4+7+\cdots +(3n-2)={\frac {n(3n-1)}{2}}$

首先，我們證明當 $n=1$ 時成立。

$1={\frac {1(3-1)}{2}}$

假設該等式對 $n=k$ 成立。那麼

$1+4+7+\cdots +(3k-2)={\frac {k(3k-1)}{2}}$

我們的目標是證明

$1+4+7+\cdots +{\bigl (}3(k+1)-2{\bigr )}={\frac {(k+1)(3k+2)}{2}}$

由此得出

${\begin{aligned}{\big (}1+4+7+\cdots +(3k-2){\big )}+{\big (}3(k+1)-2{\big )}&={\frac {k(3k-1)}{2}}+(3k+1)\\&={\frac {(3k^{2}-k+6k+2)}{2}}\\&={\frac {(3k^{2}+5k+2)}{2}}\\&={\frac {(k+1)(3k+2)}{2}}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數：$2+7+12+\cdots +(5n-3)={\frac {n(5n-1)}{2}}$

首先，我們證明當 $n=1$ 時成立。

$2={\frac {1(5-1)}{2}}$

假設該等式對 $n=k$ 成立。那麼

$2+7+12+\cdots +(5k-3)={\frac {k(5k-1)}{2}}$

我們的目標是證明

$2+7+12+\cdots +{\bigl (}5(k+1)-3{\bigr )}={\frac {(k+1){\bigl (}5(k+1)-1{\bigr )}}{2}}$

由此得出

${\begin{aligned}{\big (}2+7+12+\cdots +(5k-3){\big )}+{\big (}5(k+1)-3{\big )}&={\frac {k(5k-1)}{2}}+{\big (}5(k+1)-3{\big )}\\&={\frac {k(5k-1)+2{\big (}5(k+1)-3{\big )}}{2}}\\&={\frac {5k^{2}-k+10k+4}{2}}\\&={\frac {5k^{2}+9k+4}{2}}={\frac {(k+1)(5k+4)}{2}}\\&={\frac {(k+1){\bigl (}5(k+1)-3{\bigr )}}{2}}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數: $1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{n-1}n=2^{n}(n-1)+1$

首先，我們證明當 $n=1$ 時成立。

$1=2^{1}(1-1)+1$

假設該等式對 $n=k$ 成立。那麼

$1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k-1}k=2^{k}(k-1)+1$

我們的目標是證明

$1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k}(k+1)=2^{k+1}k+1$

由此得出

${\begin{aligned}(1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k-1}k)+2^{k}(k+1)&=2^{k}(k-1)+1+2^{k}(k+1)\\&=2^{k}(k+1+k-1)+1\\&=2^{k}(2k)+1\\&=2^{k+1}k+1\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數: ${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$

首先，我們證明當 $n=1$ 時成立。

${\frac {1}{1\cdot 2}}={\frac {1}{1+1}}$

假設該等式對 $n=k$ 成立。那麼

${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{k(k+1)}}={\frac {k}{k+1}}$

我們的目標是證明

${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{(k+1)(k+2)}}={\frac {k+1}{k+2}}$

由此得出

${\begin{aligned}{\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{k(k+1)}}+{\frac {1}{(k+1)(k+2)}}&={\frac {k}{k+1}}+{\frac {1}{(k+1)(k+2)}}\\&={\frac {1}{k+1}}\left(k+{\frac {1}{k+2}}\right)\\&={\frac {1}{k+1}}\left({\frac {k(k+2)+1}{k+2}}\right)\\&={\frac {1}{k+1}}\left({\frac {k^{2}+2k+1}{k+2}}\right)\\&={\frac {(k+1)^{2}}{(k+1)(k+2)}}\\&={\frac {k+1}{k+2}}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

這個問題可以用不使用數學歸納法的方法解決。我們注意到

${\frac {1}{n(n+1)}}={\frac {1}{n}}-{\frac {1}{n+1}}$

那麼，這個問題可以改寫為

${\frac {1}{1}}-{\frac {1}{2}}+{\frac {1}{2}}-{\frac {1}{3}}+\cdots +{\frac {1}{n-1}}-{\frac {1}{n}}+{\frac {1}{n}}-{\frac {1}{n+1}}={\frac {n}{n+1}}$

化簡得到

$1-{\frac {1}{n+1}}={\frac {n}{n+1}}$

證明對於所有正整數： $a+\cdots +a^{n}={\frac {a(a^{n}-1)}{a-1}}:a\neq 0$

首先，我們證明當 $n=1$ 時成立。

$a={\frac {a(a^{1}-1)}{a-1}}$

假設該等式對 $n=k$ 成立。那麼

$a+\cdots +a^{k}={\frac {a(a^{k}-1)}{a-1}}$

我們的目標是證明

$a+\cdots +a^{k+1}={\frac {a(a^{k+1}-1)}{a-1}}$

由此得出

${\begin{aligned}(a+\cdots +a^{k})+a^{k+1}&={\frac {a(a^{k}-1)}{a-1}}+a^{k+1}\\&={\frac {a(a^{k}-1)+a^{k+1}(a-1)}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a^{k}(a-1){\big ]}}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a\cdot a^{k}-a^{k}{\big ]}}{a-1}}\\&={\frac {a(a^{k+1}-1)}{a-1}}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

這也可以透過使用幾何級數的求和公式證明。

證明對於每個正整數：$(1+\cdots +n^{5})+(1+\cdots +n^{7})=2\left({\frac {n(n+1)}{2}}\right)^{4}$

首先，我們證明當 $n=1$ 時成立。

$1+1=2\left({\frac {1(1+1)}{2}}\right)^{4}=2$

假設該等式對 $n=k$ 成立。那麼

$(1+\cdots +k^{5})+(1+\cdots +k^{7})=2\left({\frac {k(k+1)}{2}}\right)^{4}$

我們的目標是證明

${\bigl (}1+\cdots +(k+1)^{5}{\bigr )}+{\bigl (}1+\cdots +(k+1)^{7}{\bigr )}=2\left({\frac {(k+1)(k+2)}{2}}\right)^{4}$

由此得出

${\begin{aligned}(1+\cdots +k^{5})+(k+1)^{5}+(1+\cdots +k^{7})+(k+1)^{7}&=2\left({\frac {k(k+1)}{2}}\right)^{4}+(k+1)^{5}+(k+1)^{7}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)+8(k+1)^{3}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1){\big (}1+(k+1)^{2}{\big )}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)(k^{2}+2k+2){\big ]}}{8}}\\&={\frac {(k+1)^{4}(k^{4}+8k^{3}+24k^{2}+32k+16)}{8}}\\&={\frac {(k+1)^{4}(k+2)^{4}}{8}}\\&=2\left({\frac {(k+1)(k+2)}{2}}\right)^{4}\end{aligned}}$

這正是我們要證明的。根據數學歸納法，該公式適用於所有正整數。

證明對於每個正整數： $(1+x)^{n}\geq 1+nx:x\geq -1$ （稱為伯努利不等式）

首先，我們證明當 $n=1$ 時成立。

$(1+x)^{1}\geq 1+x$ 因為 $(1+x)^{1}=1+1\cdot x$

假設該等式對 $n=k$ 成立。那麼

$(1+x)^{k}\geq 1+kx$

我們的目標是證明

$(1+x)^{k+1}\geq 1+(k+1)x$

在等式兩邊同時乘以$(1+x)$（不會改變不等式的符號，因為$x\geq -1$，因此$x+1\geq 0$）

${\begin{aligned}(1+x)^{k+1}&\geq (1+kx)(1+x)\\&=1+kx+x+kx^{2}\\&=1+(k+1)x+kx^{2}\\&\geq 1+(k+1)x\end{aligned}}$

最後一步依賴於$kx^{2}\geq 0$，因為$k\geq 0,x^{2}\geq 0$。

根據數學歸納法，該公式對所有正整數成立。

證明對於每個正整數：$1^{3}+\cdots +(n-1)^{3}<{\frac {n^{4}}{4}}<1^{3}+\cdots +n^{3}$

首先，我們證明該陳述對$n=1,2$ 成立。

${\begin{aligned}(1-1)^{3}&<{\frac {1^{4}}{4}}<1^{3}\iff 0<{\frac {1}{4}}<1\\(1-1)^{3}+1^{3}&<{\frac {2^{4}}{4}}<1^{3}+2^{3}\iff 1<4<9\end{aligned}}$

假設不等式對$n=k$ 成立。然後，

$1^{3}+\cdots +(k-1)^{3}<{\frac {k^{4}}{4}}<1^{3}+\cdots +k^{3}$

我們的目標是證明

$1^{3}+\cdots +k^{3}<{\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

我們知道

${\bigl (}1^{3}+\cdots +(k-1)^{3}{\bigr )}+k^{3}<{\frac {k^{4}}{4}}+k^{3}$

現在我們需要證明

${\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}$

由此得出

${\begin{aligned}{\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}&\iff {\frac {k^{3}(k+1)}{4}}<{\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}\\&\iff 0<{\frac {6k^{2}+4k+1}{4}}\end{aligned}}$

最後一個結論顯然成立（$k>0$）。因此，

$1^{3}+\cdots +k^{3}<{\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}$

現在我們證明

${\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

我們知道

${\frac {k^{4}}{4}}+(k+1)^{3}<(1^{3}+\cdots +k^{3})+(k+1)^{3}$

現在我們需要證明

${\frac {(k+1)^{4}}{4}}<{\frac {k^{4}}{4}}+(k+1)^{3}$

由此得出

${\begin{aligned}{\frac {(k+1)^{4}}{4}}<{\frac {k^{4}}{4}}+(k+1)^{3}&\iff {\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}<{\frac {k^{4}+4(k^{3}+3k^{2}+3k+1)}{4}}\\&\iff {\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}<{\frac {k^{4}+4k^{3}+12k^{2}+12k+4}{4}}\\&\iff 0<{\frac {6k^{2}+8k+3}{4}}\end{aligned}}$

最後一個結論顯然成立（$k>0$）。因此，

${\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

結合我們證明的兩個不等式，得到歸納步驟中需要的那個不等式。

$1^{3}+\cdots +k^{3}<{\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

根據數學歸納法，該公式對所有正整數都成立。

證明對於所有正整數：$1+\cdots +{\frac {1}{\sqrt {n}}}\leq 2{\sqrt {n}}-1$（困難）

首先，我們證明當 $n=1$ 時成立。

$1\leq 2{\sqrt {1}}-1$ 因為 $1\leq 1$

假設不等式對$n=k$ 成立。然後，

$1+\cdots +{\frac {1}{\sqrt {k}}}\leq 2{\sqrt {k}}-1$

我們的目標是證明

$1+\cdots +{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}-1$

我們知道

$\left(1+\cdots +{\frac {1}{\sqrt {k}}}\right)+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1$

現在我們需要證明

$2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$

由此得出

${\begin{aligned}2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1&\iff 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}\\&\iff 2{\sqrt {k(k+1)}}+1\leq 2(k+1)\\&\iff 2{\sqrt {k(k+1)}}\leq 2k+1\\&\iff 2^{2}{\sqrt {k(k+1)}}^{2}\leq {(2k+1)}^{2}\\&\iff 4k^{2}+4k\leq 4k^{2}+4k+1\\&\iff 0\leq 1\end{aligned}}$

最後一個語句顯然是正確的。所以，

$1+\cdots +{\frac {1}{\sqrt {k}}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$

根據數學歸納法，該公式對所有正整數都成立。

證明對於每個正整數: 3 是 $n^{3}-n+3$ 的一個因子。

首先，我們證明這個結論對於 $n=1$ 是成立的。對於 $n=1$

$1^{3}-1+3=3$, 且 3 是 3 的一個因子。

由於我們已經證明了基本情況是成立的，我們假設這個結論對於 $n=k$ 是成立的，其中 $k\in \mathbb {Z^{+}}$。

$k^{3}-k+3=3w$ 其中 $w\in \mathbb {Z^{+}}$ （換句話說，對於任何正整數，這個表示式都可以被 3 整除）。

假設基本情況在 $n=1$ 時成立，並且假設該命題在 $n=k$ 時成立，那麼它在 $n=k+1$ 時也必須成立，我們現在嘗試證明這一點。

${\begin{aligned}3z&=(k+1)^{3}-(k+1)+3\\&=k^{3}+3k^{2}+3k+1-k-1+3\\&=[k^{3}-k+3]+3k^{2}+3k\\&=3w+3k^{2}+3k\\&=3(w+k^{2}+k)\\z&=w+k^{2}+k\end{aligned}}$

因此，基於 $n=k$ 為真這一假設，該命題在 $n=k+1$ 時為真，因此根據數學歸納法，該命題對所有正整數都成立。

證明對於每個正整數：9 是 $10^{n+1}+3\cdot 10^{n}+5$ 的因數。

首先，我們證明這個命題在 $n=1$ 時成立。

$10^{1+1}+3\cdot 10^{1}+5=135=9\cdot 15$

由於我們已經證明了基本情況成立，我們現在假設該命題在 $n=k$ 時成立，其中 $k\in \mathbb {Z^{+}}$。

我們知道

$10^{k+1}+3\cdot 10^{k}+5=9w$ 對於某些 $w\in \mathbb {Z^{+}}$，

我們需要證明

$10^{k+2}+3\cdot 10^{k+1}+5=9z$ 對於某些 $z\in \mathbb {Z^{+}}$。

我們嘗試證明以上內容

${\begin{aligned}10^{k+2}+3\cdot 10^{k+1}+5&=10(10^{k+1}+3\cdot 10^{k})+5\\&=9(10^{k+1}+3\cdot 10^{k})+10^{k+1}+3\cdot 10^{k}+5\\&=9(10^{k+1}+3\cdot 10^{k})+9w\\&=9(10^{k+1}+3\cdot 10^{k}+w)\end{aligned}}$

令 $z=10^{k+1}+3\cdot 10^{k}+w$，我們有

$10^{k+2}+3\cdot 10^{k+1}+5=9z$

我們在假設該結論對 $n=k$ 成立的情況下，證明了該結論對 $n=k+1$ 成立。因此，根據數學歸納法，該結論對所有正整數都成立。

請注意，也可以使用 9 的整除性規則來證明這一點：$10^{n+1}+3\cdot 10^{n}+5$ 的各位數字之和為 $1+3+5=9$，因此該數字本身可以被 9 整除。

證明對每個正整數：4 是 $5^{n}-1$ 的一個因子

首先，我們證明該結論對 $n=1,2$ 成立。當 n=1 時，

$5^{1}-1=4$，4 是 4 的一個因子。

當 n=2 時，

$5^{2}-1=24$，4 是 24 的一個因子。

因此，基本情況成立。現在我們假設上述方程 $f(n)$ 對 n=k 成立，並試圖證明該方程對 n=k+1 成立。

${\begin{aligned}f(k+1)&=5^{k+1}-1\\&=5(5^{k})-1\\&=5(5^{k}-1)-1+5\\&=5(5^{k}-1)+4\\&=5(f(k))+4\end{aligned}}$

根據我們上面的歸納假設，4 是 f(k) 的一個因子，4 也是 4 的一個因子，所以我們知道 4 必須也是 $5(f(k))+4$ 的一個因子。根據數學歸納法，該方程對所有正整數都成立。

證明對於任意正整數：$x-y$ 是 $x^{n}-y^{n}$ 的因式。

我們將使用強歸納法。

首先，我們證明當 $n=1,2$ 時，該結論成立。

$x-y$ 是 $x^{1}-y^{1}$ 的因式，因為任何表示式都是其自身的因式。 $x-y$ 是 $x^{2}-y^{2}$ 的因式，因為 $x^{2}-y^{2}=(x-y)(x+y)$

由於當 $n=1$ 和 $n=2$ 時，該結論成立，我們現在假設它對於所有 $k<n$ 成立，其中 $k\in \mathbb {Z^{+}}$.

我們知道

$x-y$ 是 $x^{k}-y^{k}$ 的因式

我們需要證明

$x-y$ 是 $x^{n}-y^{n}$ 的因式

我們嘗試證明以上內容

${\begin{aligned}x^{n}-y^{n}&=x^{n}-y^{n}+xy^{n-1}-x^{n-1}y-xy^{n-1}+x^{n-1}y\\&=x^{n}+xy^{n-1}-x^{n-1}y-y^{n}+x^{n-1}y-xy^{n-1}\\&=x(x^{n-1}+y^{n-1})-y(x^{n-1}+y^{n-1})+x^{n-1}y-xy^{n-1}\\&=(x-y)(x^{n-1}+y^{n-1})+xy(x^{n-2}-y^{n-2})\end{aligned}}$

因為該語句對 $k=n-2$ 成立，因為 $n-2<n$，$x-y$ 是表示式兩項的因子。

因此，$x-y$ 是整個表示式 $x^{n}-y^{n}$ 的一個因子。

我們已經證明了該語句對 $k=n$ 成立，假設它對所有 $k<n$ 成立。因此，該語句對所有正整數成立。

證明對每個正整數：2304 是 $7^{2n}-48n-1$ 的一個因子。

無解

找到 $n_{0}\in \mathbb {N}$，使得不等式 $n^{2}<2^{n}$ 對所有 $n\geq n_{0}$ 成立，並給出歸納法證明。

首先，我們證明該語句對 $n=n_{0}=5$ 成立。

$5^{2}=25<32=2^{5}$

假設不等式對 $n=k$ 成立，其中 $k\geq 5$。那麼，

${\begin{aligned}(k+1)^{2}&=k^{2}+2k+1\\&<k^{2}+2k+k\quad ({\text{since}}\ k>1)\\&=k^{2}+3k\\&=k(k+3)\\&<k(k+k)\quad ({\text{since}}\ k>3)\\&=k(2k)\\&=2k^{2}\\&<2\cdot 2^{k}\quad ({\text{by induction hypothesis}})\\&=2^{k+1}\end{aligned}}$ .

我們已經證明，如果對於 $n=k$ 成立，那麼它對於 $n=k+1$ 也成立。由於它對於 $n_{0}=5$ 成立，因此對於所有整數 $n\geq n_{0}$ 成立。