A-level 數學/Edexcel/進階 1/數學歸納法證明

數學歸納法證明

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

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

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

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

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

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

1. 命題 - 你想證明什麼？
2. 基本情況 - 第一種情況是否成立？這意味著它是否適用於第一個可能的 n 值。
3. 假設 - 我們假設我們要證明的內容對一個通用數字是成立的。例如 $k$
4. 歸納 - 證明如果我們的假設對第 ($k^{th})$ 項是成立的，那麼它也必須對下一項 ( $k+1^{th})$ 項成立。
5. 結論 - 正式化你的證明。

在 FP1 中，你會遇到四種數學歸納法

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

歸納證明的示例，涉及求和級數

命題：$Prove\ by\ induction\ that,\displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2}$$,for\ n\in \mathbb {N^{+}}$

注意我們的引數，$for\ n\in \mathbb {N^{+}}$。這意味著它希望我們證明它對所有屬於集合 ($\in$) 的正整數 ($\mathbb {N^{+}}$) 的 $n$ 值是成立的。

基本情況

$Let\ n=1\$

$\displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]$
${\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]$

等式左邊等於等式右邊，因此基本情況成立。

$LHS=RHS\longrightarrow \displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2},for\ n=1$

現在你需要做假設

$Now,\ let\ n=k\ and\ assume\ true\ \forall \ k\in \mathbb {Z^{+}}$

我們假設對於所有屬於正整數集的 K 值，這個公式都是成立的。

$\displaystyle \sum _{r=1}^{k}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}$

歸納法：對於歸納法，我們需要利用我們假設 $n=k$ 成立這一事實，因此我們可以簡單地將另一項 $(k+1)$ 新增到系列中 $k^{th}$ 項的總和，從而得到系列中 $(k+1)^{th}$ 項的總和。

$Hence,\ let\ n=k+1:\displaystyle \sum _{r=1}^{k+1}r^{3}=\displaystyle \sum _{r=1}^{k}r^{3}+(k+1)^{3}$

$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}$

提取 ${\frac {1}{4}}(k+1)^{2}$ 我們得到

$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]$ 

這給了我們：$\displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}(k+2)^{2}$
請注意，我們知道我們已經完成了，因為，看看我們最初被要求證明的內容，$n$ 值被替換為 $k+1$.

總結

$\therefore \ true\ for\ n=k+1\longrightarrow \ true\ \forall \ n\in \mathbb {Z^{+}}$
因此，如果我們的假設對於 $n=k$ 為真，那麼 $n=k+1$ 也為真，這意味著 $n$ 對於所有屬於正整數集的 $n$ 值都為真。

涉及可除性的歸納證明示例

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

同樣，請注意我們的引數，$for\ n\in \mathbb {N^{+}}$ 這意味著它希望我們證明它對於所有屬於正整數集（$\in$）的 $n$ 值都為真（$\mathbb {N^{+}}$）。

基本情況

$Let\ n=1$

$f(1)=5^{1}+8(1)+3\Rightarrow f(1)=16$

$\therefore \ 4\ |\ f(1)$

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

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

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

因此 $let\ n=k+1\rightarrow \ 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)$

$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)$

我們已經證明了 $4\ |\ f(k+1)-f(k)$，因此 $4\ |\ f(k+1)$，這意味著 $4\ |\ f(n)$，因為你已經成功證明了 4 能整除 $f(n)$，其中 $n$ 是一個一般的正整數 ($k$)，也是一般項後的連續項 ($k+1$)

結論

如果 $4\ |\ f(k)\Rightarrow 4\ |\ f(k+1)$
$\therefore \ 4\ |\ f(n),\forall \ n\in \mathbb {Z^{+}}$

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