There’s no need to fuss over boundary conditions.
Table of Content
\({r\choose k} = \begin{cases} {r^{\underline{k}} / k!},\ k \in \mathbb{N} \\ 0,\ k \in \mathbb{Z}^- \end{cases}\)
\(k\) 必為整數，\(r\) 為任意實數，甚至複數
有些 Identity 可以用 Induction 證明
\(n\) 一定不能是負的！詳見 CMath p.156
利用 Symmetry，可以得到（保持 lower index 不變）
\[(r-k){r \choose k} = r{r-1 \choose k},\ k \in \mathbb{Z},\ r \in \mathbb{R}\]等等，不是說 Symmetry 只能用在 upper index 為非負整數時嗎？但事實上這個 identity 適用於任意實數上標，因為以下闡述的 polynomial argument：
Polynomial Argument
設 \(f(x)\) 和 \(g(x)\) 皆為 \(d\) 次多項式：若 \(f\) 和 \(g\) 在多於 \(d\) 處皆相等，則 \(f = g\)。
Proof
設 \(f(\alpha_i) = g(\alpha_i) = \beta_i,\ i \in \{1, 2, \cdots, k\}\)，令 \(h(x) = f(x) - g(x)\)，則有 \(k\) 個點使 \(h(x)\) 為零。因為 \(h(x)\) 至多為 \(d\) 次多項式，根據代數基本定理，\(h(x) = 0\) 至多有 \(d\) 個解；如果 \(k > d\) 代表 \(h(x) = 0\) 恆成立，也就是
\[f(x) = g(x) \tag*{$\blacksquare$}\]套用到本性質：等號左右皆為 \(r\) 的 \(k+1\) 次多項式，而且對於所有 \(r \in \mathbb{Z}^+\) 等號皆成立（也就是無限多個點上，兩多項式相等，符合 polynomial argument），因此多項式相等，\(r\) 於是可推廣至實數。
如果 \(r\) 是任意實數，就要符合第二個條件
可以推廣至複數（設 \(z = x/y\)）：
\[(1+z)^r = \sum_k{r \choose k}z^k,\ \left| z \right| < 1\]\(z\) 的限制是為了確保 infinite sum 收斂
第二個公式可用 上下差 \(r\) 導出
注意 sum 的下標和 \(k\) 的位置
CMath p.169
Proof
\(\Delta\) 是 operator，\(\Delta = E - 1\)（見 Finite Calculus）。利用 binomal theorem，
\[\Delta^n = (E-1)^n = \sum_k{n \choose k}E^k(-1)^{n-k}\]又 \(E^kf(x) = f(x+k)\)，得證。
把 \(k\) 從下（上）標往上（下）移
Proof
直接將 \(f(x)\) 或 \(g(x)\) 代入
利用 Stirling Numbers，\(x^n\) 可以用 falling factorial 表示，所以任意 polynomial 都可以用 binomial coefficient 表示（因為 \({x \choose k} = x^{\underline k}/k!\)）。Newton Series 就是
\[f(x) = c_d{x \choose d} + c_{d-1}{x \choose d-1} + \cdots + c_0{x \choose 0}\]\[f(x) = a_dx^d + \cdots + a_0 = b_dx^{\underline d} + \cdots + b_0,\ deg(f) = d\]
再根據這個小性質
\[\Delta\Big({x \choose k}\Big) = {x+1 \choose k} - {x \choose k} = {x \choose k-1}\]可以得出 \(n\)-th difference（類比 \(n\) 次微分）
\[\Delta^nf(x) = c_d{x \choose d-n} + c_{d-1}{x \choose d-1-n} + \cdots + c_0{x \choose -n}\]而
\[\Delta^nf(0) = \begin{cases} c_n,\ n \leq d; \\ 0,\ n > d. \end{cases}\]所以 Newton Series 可以寫成
\[f(x) = \Delta^df(0){x \choose d} + \Delta^{d-1}f(0){x \choose d-1} + \cdots + f(0){x \choose 0}\]再來看 Difference（\(n \leq d\)）
\[\begin{eqnarray} \Delta^nf(0) &=& \sum_k{n \choose k}(-1)^{n-k}f(k) \\ &=& \sum_k{n \choose k}(-1)^{n-k}(c_0{k \choose 0} + c_{1}{k \choose 1} + \cdots + c_n{k \choose n}) \\ &=& c_n \end{eqnarray}\]又 Newton Series 和原 polynomial 的領導係數的關係是
\[c_n = n!a_n\]於是可以得到
\[(-1)^nn!a_n = \sum_k{n \choose k}(-1)^{k}(a_0 + \cdots + a_nk^n)\]這個 identity 的重點是 \(\sum{n \choose k}(-1)^k\)
如果 polynomial \(a_0 + \cdots + a_nk^n\) 的次數小於 \(n\)（\(a_n = 0\)），則整個 summation 為 \(0\)（常用！）
將 Newton Series 推廣至 infinity，可以類比 Taylor Series
\[g(a+x) = \sum_n{\Delta^ng(a) \over n!}x^{\underline n} = \sum_n{\Delta^ng(a)} {x \choose n}\]錯置排列，詳見 [CMath] p.193-196
從前從前，有一棒球隊贏得冠軍，隊員們都非常高興，同時用力地將自己的帽子往天空拋去。當帽子墜落下來、重回球員們的手中時，多少人可以拿回自己的帽子？
令 \(h(n, k)\) 代表 \(n\) 位球員中恰 \(k\) 位拿回自己的帽子的排列數，而 \(n¡ = h(n, 0)\)，代表所有人的帽子錯置（\(n¡\) 念做 n factorial）。
\[n! = \sum_k h(n, k) = \sum_k {n \choose k}(n-k)¡ = \sum_k {n \choose k}k¡, \tag{2}\]選 \(k\) 人拿回自己的帽子
然後利用 Inversion 可以得到
\[n¡ = (-1)^n\sum_k{n \choose k}(-1)^kk!\]設 \(g(n) = n!,\ f(k) = (-1)^kk¡\)
所以
\[n¡ = \sum_{0 \leq k \leq n}{n! \over (n-k)!}(-1)^{n-k} = n!\sum_{0 \leq k \leq n}(-1)^k / k!, \tag{3}\]因為
\[\sum_{k \geq 0}(-1)^k/k! = e^{-1}\]然後再經過一番曲折，可以得到 closed form
\[n¡ = \Big\lfloor {n! \over e} + {1 \over 2} \Big\rfloor + [n=0]\]見 CMath p.200