數學歸納法

數學歸納法（粵拼：Sou³ hok⁶ gwai¹ naap⁶ faat³；英國話：Proof by mathematical induction）係一種數學上常用嘅證明方法。利用自然數（Natural number）嘅性質去證明一個有排序嘅命題（Proposition）。

數學歸納法法則

數學歸納法法則（Principal Mathematical Induction）係數學歸納法證明命題嘅邏輯。

首先要證明以下呢兩樣嘢：

• 當 $n=1$ 嘅時候，$P_{n}$ 呢個命題係啱嘅；
• 當 $P_{k}$ 呢個命題係啱嘅時候，可以引伸到 $P_{k+1}$ 都係啱嘅；

假如以上兩點成立到嘅話，咁就有得話當 $n=2$ 嘅時候，$P_{n}$ 呢個命題會係啱嘅，而推落去又有得話當 $n=3$ 嘅時候，$P_{n}$ 呢個命題都會係啱嘅，如此類推，就有得話「對應所有嘅自然數 $n$，$P_{n}$ 都會係啱」（For all natural number $n$, $P_{n}$ is true）。

基本方法

數學歸納法需要以下三個步驟：

1. 基本步驟（Base step）：證明命題喺 $n=1$ 嘅時候係啱嘅。
2. 歸納假設（Induction hypothesis）：假設命題喺 $n=k$ 嘅時候係啱嘅。
3. 推斷（Inductive step）：利用(2)嘅假設，證明命題喺 $n=k+1$ 嘅時候都係啱嘅。

例子一

證明 ${\frac {1}{1\times 3}}+{\frac {1}{3\cdot 5}}+\cdot +{\frac {1}{(2n-1)(2n+1)}}={\frac {n}{2n+1}}$

證明：

基本步驟：當 $n=1$，${\frac {1}{(2\times 1-1)(2\times 1+1)}}={\frac {1}{1\times 3}}={\frac {1}{3}}$

${\frac {1}{2\times 1+1}}={\frac {1}{3}}$

歸納假設：假設 ${\frac {1}{(2k-1)(2k+1)}}={\frac {k}{2k+1}}$

推斷：想證明 $n=k+1$係啱嘅。

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

${\begin{aligned}{\frac {1}{1\times 3}}+{\frac {1}{3\cdot 5}}+\cdot +{\frac {1}{(2k-1)(2k+1)}}+{\frac {1}{(2k+1)(2k+3)}}&={\frac {k}{2k+1}}+{\frac {1}{(2k+1)(2k+3)}}\\&={\frac {k(2k+3)+1}{(2k+1)(2k+3)}}\\&={\frac {2k^{2}+3k+1}{(2k+1)(2k+3)}}\\&={\frac {(2k+1)(k+1)}{(2k+1)(2k+3)}}\\&={\frac {k+1}{2(k+1)+1}}\end{aligned}}$ 所以呢個命題對應所有嘅$n\in \mathbb {N}$係啱。

例子二

證明「如果 $x\neq 0\in \mathbb {Z}$ 係非零整數，咁對應所有正整數 $n\in \mathbb {Z} _{>0}$，$x^{2n}$ 係正數。」

證明：

基本步驟：如果 $n=1$，$x^{2n}=x^{2}$ 咁 $x^{2}$ 係正數。

歸納假設：如果 $n=k$ 係啱嘅話，即係 $n=x^{2k}$ 係正數。

推斷：如果 $n=k+1$，

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

應用

加總類型

假設 $n$ 係正整數。

• $1+2+3+\cdots +n={\frac {n(n+1)}{2}}$
• $1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}$
• $2+2^{2}+2^{3}+\cdots +2^{n}=2(2^{n}-1)$
• $1^{3}+2^{3}+3^{3}+\cdots +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}$

乘完再加型

假設 $n$ 係正整數。

• ${\frac {1}{1\times 2}}+{\frac {1}{2\times 3}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$
• $1\times 2+2\times 2^{2}+\cdots +n\times 2^{n}=(n-1)2^{n+1}+2$
• $a+(a+d)+(a+2d)+\cdots +[a+(n-1)d]={\frac {n}{2}}[2a+(n-1)d]$
• $a+ar+ar^{2}+\cdots +ar^{n-1}=a{\frac {1-r^{n}}{1-r}}$，如果$r\neq 1$
• ${\frac {1}{3}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{3^{n}}}={\frac {1}{2}}(1-{\frac {1}{3^{n}}})$

指數定律

假設 $m,n$ 係正整數，$x,y$ 係整數。

• $(xy)^{n}=x^{n}y^{n}$
• $n(x+y)=nx+ny$
• $(m+n)x=mx+nx$
• $x^{m}\times x^{n}=x^{m+n}$

簡單不等式

假設 $n$ 係正整數。

• $4n>n+2$
• $n<2^{n}$
• $x^{n}<y^{n}$，$x,y$ 都係整數同埋 $0<x<y$
• $n!\leq n^{n}$

不等式

假設 $n$ 係正整數。

• $1+n<n^{2}$，$n\geq 2$
• $1+2n<2^{n}$，$n\geq 3$
• $2^{n}<n!$，$n\geq 4$
• $n^{3}<n!$，$n\geq 6$

睇埋

• 直接證明
• 分類證明
• 反證法
• 否定證明

參考

• Tillema, E., Kilpatrick, J., Johnson, H., Grady, M., Konnova, S., & Heid, M. K. (2015). Proof by mathematical induction. Mathematical Understanding for Secondary Teaching: A Framework and Classroom-Based Situations, 433.