數學歸納法 (粵拼 :Sou3 hok6 gwai1 naap6 faat3 ;英國話 :Proof by mathematical induction)係一種數學 上常用嘅證明方法 。利用自然數 (Natural number)嘅性質去證明一個有排序嘅命題 (Proposition)。
數學歸納法法則 [ 編輯 ]
數學歸納法法則(Principal Mathematical Induction)係數學歸納法證明命題嘅邏輯。
首先要證明以下呢兩樣嘢:
當
n
=
1
{\displaystyle n=1}
嘅時候,
P
n
{\displaystyle P_{n}}
呢個命題係啱嘅;
當
P
k
{\displaystyle P_{k}}
呢個命題係啱嘅時候,可以引伸到
P
k
+
1
{\displaystyle P_{k+1}}
都係啱嘅;
假如以上兩點成立到嘅話,咁就有得話當
n
=
2
{\displaystyle n=2}
嘅時候,
P
n
{\displaystyle P_{n}}
呢個命題會係啱嘅,而推落去又有得話當
n
=
3
{\displaystyle n=3}
嘅時候,
P
n
{\displaystyle P_{n}}
呢個命題都會係啱嘅,如此類推,就有得話「對應所有嘅自然數
n
{\displaystyle n}
,
P
n
{\displaystyle P_{n}}
都會係啱」(For all natural number
n
{\displaystyle n}
,
P
n
{\displaystyle P_{n}}
is true)。
基本方法 [ 編輯 ]
數學歸納法需要以下三個步驟:
基本步驟(Base step):證明命題喺
n
=
1
{\displaystyle n=1}
嘅時候係啱嘅。
歸納假設(Induction hypothesis):假設命題喺
n
=
k
{\displaystyle n=k}
嘅時候係啱嘅。
推斷(Inductive step):利用(2)嘅假設,證明命題喺
n
=
k
+
1
{\displaystyle n=k+1}
嘅時候都係啱嘅。
例子一 [ 編輯 ]
證明
1
1
×
3
+
1
3
⋅
5
+
⋅
+
1
(
2
n
−
1
)
(
2
n
+
1
)
=
n
2
n
+
1
{\displaystyle {\frac {1}{1\times 3}}+{\frac {1}{3\cdot 5}}+\cdot +{\frac {1}{(2n-1)(2n+1)}}={\frac {n}{2n+1}}}
證明:
基本步驟:當
n
=
1
{\displaystyle n=1}
,
1
(
2
×
1
−
1
)
(
2
×
1
+
1
)
=
1
1
×
3
=
1
3
{\displaystyle {\frac {1}{(2\times 1-1)(2\times 1+1)}}={\frac {1}{1\times 3}}={\frac {1}{3}}}
1
2
×
1
+
1
=
1
3
{\displaystyle {\frac {1}{2\times 1+1}}={\frac {1}{3}}}
歸納假設:假設
1
(
2
k
−
1
)
(
2
k
+
1
)
=
k
2
k
+
1
{\displaystyle {\frac {1}{(2k-1)(2k+1)}}={\frac {k}{2k+1}}}
推斷:想證明
n
=
k
+
1
{\displaystyle n=k+1}
係啱嘅。
1
[
2
(
k
+
1
)
−
1
]
[
2
(
k
+
1
)
+
1
]
=
1
(
2
k
+
2
−
1
)
(
2
k
+
2
+
1
)
=
1
(
2
k
+
1
)
(
2
k
+
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}}}
1
1
×
3
+
1
3
⋅
5
+
⋅
+
1
(
2
k
−
1
)
(
2
k
+
1
)
+
1
(
2
k
+
1
)
(
2
k
+
3
)
=
k
2
k
+
1
+
1
(
2
k
+
1
)
(
2
k
+
3
)
=
k
(
2
k
+
3
)
+
1
(
2
k
+
1
)
(
2
k
+
3
)
=
2
k
2
+
3
k
+
1
(
2
k
+
1
)
(
2
k
+
3
)
=
(
2
k
+
1
)
(
k
+
1
)
(
2
k
+
1
)
(
2
k
+
3
)
=
k
+
1
2
(
k
+
1
)
+
1
{\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}}}
所以呢個命題對應所有嘅
n
∈
N
{\displaystyle n\in \mathbb {N} }
係啱。
例子二 [ 編輯 ]
證明「如果
x
≠
0
∈
Z
{\displaystyle x\neq 0\in \mathbb {Z} }
係非零整數 ,咁對應所有正整數
n
∈
Z
>
0
{\displaystyle n\in \mathbb {Z} _{>0}}
,
x
2
n
{\displaystyle x^{2n}}
係正數。」
證明:
基本步驟:如果
n
=
1
{\displaystyle n=1}
,
x
2
n
=
x
2
{\displaystyle x^{2n}=x^{2}}
咁
x
2
{\displaystyle x^{2}}
係正數。
歸納假設:如果
n
=
k
{\displaystyle n=k}
係啱嘅話,即係
n
=
x
2
k
{\displaystyle n=x^{2k}}
係正數。
推斷:如果
n
=
k
+
1
{\displaystyle n=k+1}
,
x
2
n
=
x
2
(
k
+
1
)
=
x
2
k
+
2
=
x
2
k
⋅
x
2
{\displaystyle {\begin{aligned}x^{2n}&=x^{2(k+1)}\\&=x^{2k+2}\\&=x^{2k}\cdot x^{2}\end{aligned}}}
最細整數性質 [ 編輯 ]
起點歸納 [ 編輯 ]
完全歸納 [ 編輯 ]
加總類型 [ 編輯 ]
假設
n
{\displaystyle n}
係正整數。
1
+
2
+
3
+
⋯
+
n
=
n
(
n
+
1
)
2
{\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}
1
2
+
2
2
+
3
2
+
⋯
+
n
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
{\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}}
2
+
2
2
+
2
3
+
⋯
+
2
n
=
2
(
2
n
−
1
)
{\displaystyle 2+2^{2}+2^{3}+\cdots +2^{n}=2(2^{n}-1)}
1
3
+
2
3
+
3
3
+
⋯
+
n
3
=
n
2
(
n
+
1
)
2
4
{\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}={\frac {n^{2}(n+1)^{2}}{4}}}
乘完再加型 [ 編輯 ]
假設
n
{\displaystyle n}
係正整數。
1
1
×
2
+
1
2
×
3
+
⋯
+
1
n
(
n
+
1
)
=
n
n
+
1
{\displaystyle {\frac {1}{1\times 2}}+{\frac {1}{2\times 3}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}}
1
×
2
+
2
×
2
2
+
⋯
+
n
×
2
n
=
(
n
−
1
)
2
n
+
1
+
2
{\displaystyle 1\times 2+2\times 2^{2}+\cdots +n\times 2^{n}=(n-1)2^{n+1}+2}
a
+
(
a
+
d
)
+
(
a
+
2
d
)
+
⋯
+
[
a
+
(
n
−
1
)
d
]
=
n
2
[
2
a
+
(
n
−
1
)
d
]
{\displaystyle a+(a+d)+(a+2d)+\cdots +[a+(n-1)d]={\frac {n}{2}}[2a+(n-1)d]}
a
+
a
r
+
a
r
2
+
⋯
+
a
r
n
−
1
=
a
1
−
r
n
1
−
r
{\displaystyle a+ar+ar^{2}+\cdots +ar^{n-1}=a{\frac {1-r^{n}}{1-r}}}
,如果
r
≠
1
{\displaystyle r\neq 1}
1
3
+
1
3
2
+
⋯
+
1
3
n
=
1
2
(
1
−
1
3
n
)
{\displaystyle {\frac {1}{3}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{3^{n}}}={\frac {1}{2}}(1-{\frac {1}{3^{n}}})}
指數定律 [ 編輯 ]
假設
m
,
n
{\displaystyle m,n}
係正整數,
x
,
y
{\displaystyle x,y}
係整數。
(
x
y
)
n
=
x
n
y
n
{\displaystyle (xy)^{n}=x^{n}y^{n}}
n
(
x
+
y
)
=
n
x
+
n
y
{\displaystyle n(x+y)=nx+ny}
(
m
+
n
)
x
=
m
x
+
n
x
{\displaystyle (m+n)x=mx+nx}
x
m
×
x
n
=
x
m
+
n
{\displaystyle x^{m}\times x^{n}=x^{m+n}}
簡單不等式 [ 編輯 ]
假設
n
{\displaystyle n}
係正整數。
4
n
>
n
+
2
{\displaystyle 4n>n+2}
n
<
2
n
{\displaystyle n<2^{n}}
x
n
<
y
n
{\displaystyle x^{n}<y^{n}}
,
x
,
y
{\displaystyle x,y}
都係整數同埋
0
<
x
<
y
{\displaystyle 0<x<y}
n
!
≤
n
n
{\displaystyle n!\leq n^{n}}
不等式 [ 編輯 ]
假設
n
{\displaystyle n}
係正整數。
1
+
n
<
n
2
{\displaystyle 1+n<n^{2}}
,
n
≥
2
{\displaystyle n\geq 2}
1
+
2
n
<
2
n
{\displaystyle 1+2n<2^{n}}
,
n
≥
3
{\displaystyle n\geq 3}
2
n
<
n
!
{\displaystyle 2^{n}<n!}
,
n
≥
4
{\displaystyle n\geq 4}
n
3
<
n
!
{\displaystyle n^{3}<n!}
,
n
≥
6
{\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.