階乘與二項式係數
階乘，記作 n!，是從 n 一直乘到 1 的所有正整數之積：例如 4! = 4 · 3 · 2 · 1 = 24。按慣例 0! = 1，這個定義讓後面的公式保持整潔。階乘計數排列方式，這正是它們出現在展開係數中的原因。
二項式係數，記作 C(n, k) 或「n 選 k」，等於 n! / (k!(n − k)!)。它計數從 n 個中選取 k 個的方式數，也正是你展開二項式冪時每一項前面的乘數。儘管有階乘，這些係數始終是整數。
Compute a binomial coefficient: C(5, 2) = "5 choose 2"
C(n, k) = n! / ( k! (n - k)! )
C(5, 2) = 5! / ( 2! * 3! )
= 120 / ( 2 * 6 )
= 120 / 12
= 10二項式定理與帕斯卡三角形
二項式定理說 (a + b)ⁿ 展開為各項 C(n, k) · a^(n−k) · b^k 之和，其中 k 從 0 跑到 n。從左到右讀，每一項 a 的冪減一而 b 的冪加一；它們的指數之和始終為 n。係數就是上面的二項式係數。
帕斯卡三角形是一種無需計算階乘就能快速得到這些係數的方法。每行以 1 開頭、以 1 結尾，每個內部數字都是它上方兩個數之和。第 n 行（從第 0 行數起）恰好給出 (a + b)ⁿ 的係數。
Pascal's triangle (rows 0 to 4):
1 <- row 0: (a+b)^0
1 1 <- row 1: coeffs 1, 1
1 2 1 <- row 2: coeffs 1, 2, 1
1 3 3 1 <- row 3: coeffs 1, 3, 3, 1
1 4 6 4 1 <- row 4: coeffs 1, 4, 6, 4, 1
Each inside number = sum of the two just above it (e.g. 6 = 3 + 3).
Use row 3 to expand (a + b)^3:
(a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3
= a^3 + 3a^2 b + 3a b^2 + b^3歸納法初體驗
我們怎麼知道像 1 + 2 + … + n = n(n + 1)/2 這樣的公式對每一個 n 都成立，而不只是我們測試過的那些？數學歸納法證明它。想像多米諾骨牌：如果第一張倒下，且每張倒下的骨牌都推倒下一張，那麼它們全都會倒。
- 基礎步驟：證明命題對第一個值成立，通常是 n = 1。
- 歸納假設：假設命題對某個值 n = k 成立。
- 歸納步驟：利用那個假設，證明命題隨後對 n = k + 1 也成立。基礎步驟加上這一步，共同迫使它對所有 n 都成立。
Prove: 1 + 2 + ... + n = n(n + 1)/2, for all n >= 1.
Base case (n = 1): left = 1. right = 1(1+1)/2 = 1. Equal. OK.
Assume true at n = k: 1 + 2 + ... + k = k(k + 1)/2.
Step to n = k + 1: add (k + 1) to both sides:
1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)
= (k + 1)[ k/2 + 1 ]
= (k + 1)(k + 2)/2
This is exactly the formula with n replaced by k + 1. Proof complete.