跳到主要內容

[基礎數學] Binomial Theorem 與其應用例

首先給出 Binomial Theorem 的陳述

Theorem: 
令 $a,b \in \mathbb{R}$ 且 $n \in \mathbb{N}$ 則
\[{(a + b)^n} = \mathop \sum \limits_{k = 0}^n \left( \begin{array}{l}
n\\
k
\end{array} \right){a^k}{b^{n - k}}\]


在證明 Binomial Theorem之前,我們會需要以下結果來幫助我們,

FACT: 給定 $n,k \in \mathbb{N}$ 且 $n \ge k$,則
\[\left( \begin{array}{l}
n + 1\\
k
\end{array} \right) = \left( \begin{array}{l}
n\\
k
\end{array} \right) + \left( \begin{array}{l}
n\\
k - 1

\end{array} \right)\]
Proof: 觀察左式,由定義可知
\[\left( \begin{array}{l}
n + 1\\
k
\end{array} \right): = \frac{{\left( {n + 1} \right)!}}{{k!\left( {n + 1 - k} \right)!}}\]
故如果我們可以證明右式等同於左式,則證明完畢。現在觀察右式
\[\begin{array}{l}
\left( \begin{array}{l}
n\\
k
\end{array} \right) + \left( \begin{array}{l}
n\\
k - 1
\end{array} \right) = \frac{{n!}}{{k!\left( {n - k} \right)!}} + \frac{{n!}}{{\left( {k - 1} \right)!\left( {n - \left( {k - 1} \right)} \right)!}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{{n!\left( {n - k + 1} \right)}}{{k!\left( {n - k + 1} \right)\left( {n - k} \right)!}} + \frac{{n!k}}{{k\left( {k - 1} \right)!\left( {n + 1 - k} \right)!}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{{n!\left( {n - k + 1} \right) + n!k}}{{k!\left( {n + 1 - k} \right)!}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}
\end{array} = \frac{{n!\left( {n + 1} \right)}}{{k!\left( {n + 1 - k} \right)!}} = \frac{{\left( {n + 1} \right)!}}{{k!\left( {n + 1 - k} \right)!}}
\end{array}\]注意到最後的等式與原本左式相等,故證明完畢。$\square$

現在我們可以開始證明 Binomial Theorem

Proof: (Binomial Theorem)
給定 $a,b \in \mathbb{R}$ 且 $n \in \mathbb{N}$ 利用數學歸納法,先觀察 $n=1$ 則
\[\begin{array}{l}
{(a + b)^1} = \sum\limits_{k = 0}^1 {\left( {\begin{array}{*{20}{l}}
1\\
k
\end{array}} \right)} {a^k}{b^{1 - k}}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = \left( {\begin{array}{*{20}{l}}
1\\
0
\end{array}} \right){a^0}{b^{1 - 0}} + \left( {\begin{array}{*{20}{l}}
1\\
1
\end{array}} \right){a^1}{b^{1 - 1}}\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {b^1} + {a^1}
\end{array}\]故成立。現在利用歸納法假設對 Binomial Theorem 對 $n$ 成立,我們要證明 $n+1$ 也成立:亦即假設 ${(a + b)^n} = \mathop \sum \limits_{k = 0}^n \left( \begin{array}{l}
n\\
k
\end{array} \right){a^k}{b^{n - k}}$成立,我們要證明
\[{(a + b)^{n+1}} = \mathop \sum \limits_{k = 0}^{n+1} \left( \begin{array}{l}
n+1\\
k
\end{array} \right){a^k}{b^{n+1 - k}} \;\;\;\;\; (*)
\]現在觀察
\[\begin{array}{l}
{\left( {a + b} \right)^{n + 1}} = {\left( {a + b} \right)^n}\left( {a + b} \right)\\
 = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^k}{b^{n - k}}\left( {a + b} \right)\\
 = \sum\limits_{a = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^{k + 1}}{b^{n - k}} + \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^k}{b^{n - k + 1}}
\end{array}\]為了使上述兩項和可以合成,我們使用變數變換,對第一項和令 $j=k+1$ 且對第二項和令 $j=k+1$ 則我們可得
\[\begin{array}{*{20}{l}}
{{{\left( {a + b} \right)}^{n + 1}} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^{k + 1}}{b^{n - k}} + \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^k}{b^{n - k + 1}}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \underbrace {\sum\limits_{j = 1}^{n + 1} {\left( {\begin{array}{*{20}{l}}
n\\
{j - 1}
\end{array}} \right)} {a^j}{b^{n - \left( {j - 1} \right)}}}_{term1} + \underbrace {\sum\limits_{j = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
j
\end{array}} \right)} {a^j}{b^{n - j + 1}}}_{term2}}\\
\begin{array}{l}
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \underbrace {\left( {\begin{array}{*{20}{l}}
n\\
n
\end{array}} \right){a^{\left( {n + 1} \right)}}{b^{n - \left( {n + 1} \right) + 1}} + \sum\limits_{j = 1}^n {\left( {\begin{array}{*{20}{l}}
n\\
{j - 1}
\end{array}} \right)} {a^j}{b^{n - j + 1}}}_{ = term1}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} + \underbrace {\sum\limits_{j = 1}^n {\left( {\begin{array}{*{20}{l}}
n\\
j
\end{array}} \right)} {a^j}{b^{n - j + 1}} + \left( {\begin{array}{*{20}{l}}
n\\
0
\end{array}} \right){a^0}{b^{n - 0 + 1}}}_{ = term2}
\end{array}\\
{\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {a^{\left( {n + 1} \right)}} + \sum\limits_{j = 1}^n {\left[ {\left( {\begin{array}{*{20}{l}}
n\\
{j - 1}
\end{array}} \right) + \left( {\begin{array}{*{20}{l}}
n\\
j
\end{array}} \right)} \right]} {a^j}{b^{n - j + 1}} + {b^{n + 1}}}
\end{array}\]現在對中間項的和,使用前述的 FACT 可得
\[\begin{array}{l}
{\left( {a + b} \right)^{n + 1}} = {a^{\left( {n + 1} \right)}}{b^{n - \left( {n + 1} \right) + 1}} + \sum\limits_{j = 1}^n {\left[ {\left( {\begin{array}{*{20}{l}}
n\\
{j - 1}
\end{array}} \right) + \left( {\begin{array}{*{20}{l}}
n\\
j
\end{array}} \right)} \right]} {a^j}{b^{n - j + 1}} + {a^0}{b^{n - 0 + 1}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = {a^{\left( {n + 1} \right)}}{b^0} + \sum\limits_{j = 1}^n {\left( {\begin{array}{*{20}{l}}
{n + 1}\\
j
\end{array}} \right)} {a^j}{b^{n + 1 - j}} + {a^0}{b^{n + 1}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left( {\begin{array}{*{20}{l}}
{n + 1}\\
{n + 1}
\end{array}} \right){a^{\left( {n + 1} \right)}}{b^0} + \sum\limits_{j = 1}^n {\left( {\begin{array}{*{20}{l}}
{n + 1}\\
j
\end{array}} \right)} {a^j}{b^{n + 1 - j}} + \left( {\begin{array}{*{20}{l}}
{n + 1}\\
0
\end{array}} \right){a^0}{b^{n + 1}}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \sum\limits_{j = 0}^{n + 1} {\left( {\begin{array}{*{20}{l}}
{n + 1}\\
j
\end{array}} \right)} {a^j}{b^{n + 1 - j}}
\end{array}\]上式滿足 $(*)$ 故得證。 $\square$


以下我們看幾個例子:

Example 1: 
試求\[\mathop \sum \limits_{i = 0}^n \left( \begin{array}{l}
n\\
i
\end{array} \right) = ?\]
Proof: 利用 Binomial Theorem,令 $a=b=1$ 可立刻得到
\[\begin{array}{l}
{(a + b)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^k}{b^{n - k}}\\
 \Rightarrow \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {1^k}{1^{n - k}} = {(1 + 1)^n} = {2^n}
\end{array}\]

Example 2:
試求
\[\mathop \sum \limits_{i = 0}^n {\left( { - 1} \right)^i}\left( \begin{array}{l}
n\\
i
\end{array} \right) = ?\]
Proof: 利用 Binomial Theorem,令 $a=-1$ 與 $b=1$ 可立刻得到
\[\begin{array}{l}
{(a + b)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {a^k}{b^{n - k}}\\
 \Rightarrow \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{l}}
n\\
k
\end{array}} \right)} {\left( { - 1} \right)^k}{1^{n - k}} = {( - 1 + 1)^n} = {0^n} = 0
\end{array}\]



留言

這個網誌中的熱門文章

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念:

Norm:一般翻譯成範數
(在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣),

也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。

事實上想法是這樣的:
比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "!

但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說
\[x:=[1, -2, 0.1, 0 ]^T
\]上式的大小該是多少? 是 $1$? $-2$? $0.1$???
再者如果更過分一點,我們考慮一個矩陣
\[A = \left[ {\begin{array}{*{20}{c}}
1&2\\
3&4
\end{array}} \right]
\],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。

也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。

故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來)

==================
Definition: Norm
考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質:

(a) $||v|| \geq 0$, $||v||=…

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if
 (此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。)

中文翻譯叫做 若且唯若 (or 當且僅當),記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。

在數學上如果看到 if and only if  這類的句子,其實是表示一種雙條件句,通常可以直接將其視為"定義(Definition)"待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他

假設我們現在有 兩個邏輯陳述句 A 與  B.
注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。

現在,考慮新的陳述:  "A if and only if B"
好了,現在主角登場,我們可以怎麼看待這個句子呢?
事實上我們可以很直覺的把這句子拆成兩部分看待,也就是
"( A if B ) and ( A only if B )"

那麼先針對第一個部分 A if B 來看,
其實這句就是說 if B then A,
更直白一點就是 "if B is true, then A is also true". 
在數學上等價可以寫為 "B implies A". 
或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A" 

現在針對第二個部分 A only if B
此句意指 "If B is not true, then A is also not true".
所以如果已知 A is true, 那麼按照上句不難推得 B is also true
也就是說 A only if B 等價為 "If A is true then B is also true".
同樣,也可以寫作"A implies B"
或者用箭頭表示 "A $\Rightarrow$  B".

所以現在總結如下,下列七個 if and only if 陳述完全等價:

"A if and only if B" "A iff…