數學歸納法證明

數學歸納法證明

數學歸納法是驗證或證明一個數學語句對於給定引數範圍內所有$n$的值都成立的過程。例如

${\text{Prove that }}f(n)=5^{n}+8n+3{\text{ is divisible by }}4,{\text{ for }}n\in \mathbb {Z} ^{+}$

要求我們證明$f(n)$ 能被 4 整除。我們可以透過給$n$ 賦值來測試它是否成立。

$n$	$f(n)$	${\text{Divisible by }}4$
$1$	$16$	$4\cdot 4$
$2$	$44$	$4\cdot 11$
$3$	$152$	$4\cdot 38$
$4$	$660$	$4\cdot 165$
$5$	$3168$	$4\cdot 792$

所以，前 5 個 n 的值可以被 4 整除，但所有情況呢？這就是數學歸納法發揮作用的地方。

數學歸納法是一個嚴謹的過程，因此所有證明必須具有相同的通用格式。

1. 命題 - 你試圖證明什麼？
2. 基本情況 - 它對第一個情況成立嗎？這意味著它對第一個可能的 $n$ 值成立。
3. 假設 - 我們假設我們試圖證明的東西對一個一般數字成立。例如 $k$，也稱為歸納假設。
4. 歸納 - 證明如果我們的假設對第 $k^{th})$ 項成立，那麼它也必須對第 $k+1^{th})$ 項成立。
5. 結論 - 正式化你的證明。

在 FP1 中，你會遇到四種類型的數學歸納法。

1. 級數求和；
2. 可除性；
3. 遞推關係；
4. 矩陣。

級數求和證明的示例

(Empty)

可除性證明的示例

命題：${\text{Prove that }}4~|~f(n)=5^{n}+8n+3,{\text{ for }}n\in \mathbb {N} ^{+}$

注意我們的引數，${\text{for }}n\in \mathbb {N} ^{+}$ 。這意味著我們要證明的內容必須對屬於正整數集（用 $\in$ 表示）的 $n$ 的所有值成立 ($\mathbb {N} ^{+}$).

基本情況

${\begin{aligned}&{\text{Let }}n=1\\&f(1)=5^{1}+8(1)+3\implies f(1)=16\\&\therefore 4~|~f(1)\end{aligned}}$

假設（歸納假設）：現在我們令 $n=k$，其中 $k$ 是一個一般性的正整數，我們假設 $4\ |\ f(k)$。

記住 $f(k)=5^{k}+8k+3$。

歸納：現在我們想要證明 $k+1^{th}$ 項也能夠被 4 整除。

因此：${\text{let }}n=k+1\implies f(k+1)=5^{k+1}+8(k+1)+3$

這裡就用到了我們的假設，如果 $4~|~f(k)$ 那麼 4 也必須能夠整除 $f(k+1)-f(k)$。

所以：$f(k+1)-f(k)=5^{k+1}+8(k+1)+3-(5^{k}+8k+3)$

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

現在我們已經證明了$4~|~{\bigl (}f(k+1)-f(k){\bigr )}$，因此$4~|~f(k+1)$。這意味著$4~|~f(n)$，因為你已經成功地證明了 4 整除$f(n)$，其中$n$ 是一個一般的正整數（$k$），也是一般項後的連續項（$k+1$）。

結論

${\begin{aligned}&4~|~f(k)\implies 4~|~f(k+1)\\&\therefore ~4~|~f(n),\forall n\in \mathbb {Z} ^{+}\end{aligned}}$

${\begin{aligned}&{\text{If }}4{\text{ divides }}f(k){\text{ (as we assumed) then it implies that }}4{\text{ also divides }}f(k+1)\\&{\text{therefore }}4{\text{ divides }}f(n),{\text{ for all values of }}n{\text{ that belong to the set of positive integers.}}\end{aligned}}$

用遞迴關係證明的例子

(Empty)

用矩陣證明的例子

(Empty)