# 數學歸納法

## 數學歸納法法則

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

### 基本方法

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

### 例子一

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

{\displaystyle {\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}}}

{\displaystyle {\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}}} 所以呢個命題對應所有嘅${\displaystyle n\in \mathbb {N} }$係啱。

## 應用

### 加總類型

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

### 乘完再加型

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

### 指數定律

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

### 簡單不等式

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

### 不等式

• ${\displaystyle 1+n${\displaystyle n\geq 2}$
• ${\displaystyle 1+2n<2^{n}}$${\displaystyle n\geq 3}$
• ${\displaystyle 2^{n}${\displaystyle n\geq 4}$
• ${\displaystyle n^{3}${\displaystyle 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.