ii. Binomial Identities

The identities that turn binomial sums into closed forms, divisibility facts (Lucas, Kummer, parity), and algorithms for sums of binomial coefficients that have no closed form: prefix sums of a row (single and many offline queries) and sums over a residue class. Binomials mod a prime come from Comb / mint in Modular Arithmetic.

Identity	Name / use
$(k n) = (k - 1 n - 1) + (k n - 1)$	Pascal
$(k n) = (n - k n)$	symmetry
$k (k n) = n (k - 1 n - 1)$	absorption
$(m n) (k m) = (k n) (m - k n - k)$	trinomial revision (“subset of a subset”)
$\sum_{k} (k n) = 2^{n}$ , $\sum_{k} (- 1)^{k} (k n) = [n = 0]$	row sums
$\sum_{k} k (k n) = n 2^{n - 1}$ , $\sum_{k} k^{2} (k n) = n (n + 1) 2^{n - 2}$	weighted row sums
$\sum_{i = 0}^{n} (k i) = (k + 1 n + 1)$	hockey stick (column sums)
$\sum_{i = 0}^{k} (i n + i) = (k n + k + 1)$	hockey stick (diagonal)
$\sum_{k} (k m) (r - k n) = (r m + n)$	Vandermonde
$\sum_{k} (k n)^{2} = (n 2 n)$	Vandermonde with $m = n$
$\sum_{k} (- 1)^{k} (k n) = 0$ for $n \geq 1$ ; $\sum_{k \leq m} (- 1)^{k} (k n) = (- 1)^{m} (m n - 1)$	alternating partial sums
$(k - n) = (- 1)^{k} (k n + k - 1)$ ; $(1 - x)^{- n} = \sum_{k} (k n + k - 1) x^{k}$	upper negation, negative binomial series
$\sum_{k} (k n - k) = F_{n + 1}$	shallow diagonals give Fibonacci
$(x_{1} + \dots + x_{m})^{n} = \sum (k _{1} , \dots , k _{m} n) x_{1}^{k_{1}} \dots x_{m}^{k_{m}}$	multinomial theorem
$g_{n} = \sum_{k} (k n) f_{k} ⟺ f_{n} = \sum_{k} (- 1)^{n - k} (k n) g_{k}$	binomial inversion
$(n 2 n) \sim \frac{4 ^{n}}{π n}$ , $\frac{4 ^{n}}{2 n + 1} \leq (n 2 n) \leq 4^{n}$	central binomial size
$(k n) \leq (\frac{n e}{k})^{k}$	upper bound used in analyses

Divisibility	Statement
Lucas	$(k n) \equiv \prod_{i} (k _{i} n _{i}) (mod p)$ over the base- $p$ digits: Factorials mod p
parity	$(k n)$ is odd iff $k & n = k$ (every bit of $k$ is set in $n$ ); row $n$ has $2^{popcount (n)}$ odd entries: Sierpiński’s triangle
Kummer	the exponent of $p$ in $(k n)$ is the number of carries when adding $k$ and $n - k$ in base $p$
Legendre	$v_{p} (n!) = \sum_{i \geq 1} ⌊ n / p^{i} ⌋ = \frac{n - s _{p} ( n )}{p - 1}$ ( $s_{p}$ = digit sum)
$p ∣ (k p)$ for $0 < k < p$	the freshman’s dream $(x + y)^{p} \equiv x^{p} + y^{p}$

int kummerCarries(ll n, ll k, ll p) {                      // v_p(C(n, k)) = carries adding k and n - k in base p
    int carries = 0; ll a = k, b = n - k, c = 0;
    while (a > 0 || b > 0 || c > 0) { ll d = a % p + b % p + c; c = d >= p; carries += (int)c; a /= p; b /= p; }
    return carries;
}
 
mint binomialPrefix(ll n, ll k) {                          // sum_{i=0}^{k} C(n, i), n < modulus, O(k)
    if (k < 0) return 0;
    k = min(k, n); mint res = 1, cur = 1;
    for (ll i = 1; i <= k; i++) { cur = cur * mint(n - i + 1) / mint(i); res += cur; }
    return res;
}
 
// Many queries f(n, k) = sum_{i<=k} C(n, i) offline with Mo's algorithm: O((N + q) sqrt N) moves of O(1).
vector<mint> binomialPrefixQueries(const vector<pair<int, int>>& qs, const Comb& cb) {   // cb must cover N + 1
    int q = sz(qs); vector<mint> res(q); if (!q) return res;
    int N = 1; for (auto [n, k] : qs) N = max({N, n + 1, k + 1});
    int B = max(1, (int)(N / sqrt((double)q)));
    vector<int> order(q); iota(all(order), 0);
    sort(all(order), [&](int a, int b) {
        int ba = qs[a].first / B, bb = qs[b].first / B;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? qs[a].second > qs[b].second : qs[a].second < qs[b].second;
    });
    mint inv2 = mint(1) / mint(2); int n = 0, k = 0; mint f = 1;   // f(0, 0) = 1
    for (int id : order) {
        auto [tn, tk] = qs[id];
        while (n < tn) f = mint(2) * f - cb.C(n, k), n++;
        while (n > tn) f = (f + cb.C(n - 1, k)) * inv2, n--;
        while (k < tk) f += cb.C(n, k + 1), k++;
        while (k > tk) f -= cb.C(n, k), k--;
        res[id] = f;
    }
    return res;
}
 
vector<mint> binomialResidueSums(ll n, int m) {            // res[r] = sum_{i = r (mod m)} C(n, i), any n <= 1e18, O(m^2 log n)
    auto mul = [&](const vector<mint>& a, const vector<mint>& b) {
        vector<mint> c(m, 0);
        for (int i = 0; i < m; i++) if (a[i] != mint(0)) for (int j = 0; j < m; j++) c[(i + j) % m] += a[i] * b[j];
        return c;
    };
    vector<mint> res(m, 0), base(m, 0); res[0] = 1; base[0] += 1; base[1 % m] += 1;   // 1 + x
    for (; n; n >>= 1, base = mul(base, base)) if (n & 1) res = mul(res, base);
    return res;
}

For $(i n)$ with $n \geq$ the modulus use Lucas; for large $m$ in the residue sums use NTT cyclic convolution instead of the $O (m^{2})$ product. Sums of a row prefix have no closed form, which is why the Mo walk (or the residue-class trick) is needed; for a single query with small $k$ the $O (k)$ loop suffices.

Proof: the identity table

Absorption: choose a committee of $k$ with a chair: $k (k n)$ (committee, then chair) $= n (k - 1 n - 1)$ (chair, then the rest). Trinomial revision: choose $m$ of $n$ and then $k$ of those, or the $k$ first and then the other $m - k$ from the remaining $n - k$ . Row sums: $(1 + x)^{n}$ at $x = \pm 1$ ; differentiating $(1 + x)^{n}$ once or twice and setting $x = 1$ gives the weighted sums. Hockey stick: classify the $(k + 1)$ -subsets of ${1.. n + 1}$ by their largest element $i + 1$ : the other $k$ elements come from ${1.. i}$ , $(k i)$ ways. The diagonal version is the column version after symmetry $(i n + i) = (n n + i)$ . Vandermonde: choose $r$ people from $m$ men and $n$ women by the number $k$ of men; or compare coefficients in $(1 + x)^{m} (1 + x)^{n}$ . Alternating partial sums: induction with Pascal, $(k n) = (k n - 1) + (k - 1 n - 1)$ , telescopes. Upper negation: $(k - n) = \frac{( - n ) ( - n - 1 ) \dots ( - n - k + 1 )}{k !} = (- 1)^{k} \frac{n ( n + 1 ) \dots ( n + k - 1 )}{k !}$ . Fibonacci diagonals: $\sum_{k} (k n - k)$ counts tilings of a $1 \times n$ strip by $k$ dominoes and $n - 2 k$ squares, which satisfies the Fibonacci recurrence (last tile a square or a domino). Multinomial theorem: a term picks one $x_{j}$ from each of the $n$ factors. Binomial inversion: in terms of EGFs, $G = e^{x} F$ , so $F = e^{- x} G$ . Central binomial: $(n 2 n)$ is the largest of the $2 n + 1$ terms of row $2 n$ summing to $4^{n}$ , so it lies between $\frac{4 ^{n}}{2 n + 1}$ and $4^{n}$ (Stirling gives the asymptotic). $(k n) \leq \frac{n ^{k}}{k !} \leq (\frac{n e}{k})^{k}$ since $k! \geq (k / e)^{k}$ .

Proof: parity, Kummer, and the prefix-sum moves

Kummer. $v_{p} (k n) = v_{p} (n!) - v_{p} (k!) - v_{p} ((n - k)!)$ , and by Legendre $v_{p} (m!) = \frac{m - s _{p} ( m )}{p - 1}$ , so $v_{p} (k n) = \frac{s _{p} ( k ) + s _{p} ( n - k ) - s _{p} ( n )}{p - 1}$ . Each carry in the base- $p$ addition $k + (n - k)$ lowers the digit sum by exactly $p - 1$ , so this is the number of carries. Parity ( $p = 2$ ): $(k n)$ is odd iff adding $k$ and $n - k$ in binary has no carry, i.e. $k$ and $n - k$ have disjoint bits, i.e. $k & n = k$ ; the odd entries of row $n$ are the $2^{popcount (n)}$ submasks of $n$ (Lucas gives the same).

Mo moves for $f (n, k) = \sum_{i \leq k} (i n)$ . $f (n, k + 1) = f (n, k) + (k + 1 n)$ is the definition. By Pascal, $f (n + 1, k) = \sum_{i \leq k} (i n) + \sum_{i \leq k} (i - 1 n) = f (n, k) + f (n, k - 1) = 2 f (n, k) - (k n)$ , and solving for $f (n, k)$ gives $f (n - 1, k) = \frac{f ( n , k ) + ( k n - 1 )}{2}$ (needs 2 invertible: an odd modulus). Each move is $O (1)$ ; Mo’s ordering (blocks of $n$ , alternating $k$ direction) makes the total number of moves $O ((N + q) N)$ . Residue classes: $\sum_{i \equiv r} (i n)$ is the coefficient of $x^{r}$ in $(1 + x)^{n}$ reduced modulo $x^{m} - 1$ , computed by binary exponentiation with cyclic products. All functions were checked against direct summation, and the table identities numerically for $n \leq 30$ .

whoashish's cp notes

Directory

ii. Binomial Identities

Graph View

whoashish's cp notes

Directory

ii. Binomial Identities

Related notes

Graph View