阶乘与二项式系数
阶乘，记作 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.