Hypergeometric Identities — WZ Method & Vandermonde Convolution

January 2026 · 28 min read

Binomial Sum Identities

Many competitive-programming problems reduce to evaluating a closed-form for a sum involving binomial coefficients. Instead of brute-forcing Σ C(n,k)·(…), knowing the right identity lets you compute the answer in O(1) or O(n) and shave an entire dimension off your solution.

Vandermonde’s Identity

The most fundamental convolution identity for binomial coefficients is Vandermonde’s identity:

Σ_k=0^r C(m, k) · C(n, r−k) = C(m+n, r)

Proof via Generating Functions

Consider the coefficient of x^r on both sides of (1+x)^m · (1+x)ⁿ = (1+x)^m+n. On the left, [x^r] equals Σ_k C(m,k)·C(n,r−k) by the Cauchy product. On the right it equals C(m+n,r). □

Chu–Vandermonde Generalization

Vandermonde’s identity generalizes when we allow the upper index to be a real (or complex) number. Using the generalized binomial coefficient C(α, k) = α(α−1)…(α−k+1) / k!, the identity becomes:

Σ_k=0^r C(α, k) · C(β, r−k) = C(α+β, r)

This is exactly the Chu–Vandermonde identity. In hypergeometric notation it reads ₂F₁(−r, −α; β−r+1; 1) = C(α+β, r)/C(β, r). Setting α = m, β = n recovers the standard version.

An important special case sets β = −n with n a positive integer:

Σ_k=0^r C(α, k) · (−1)^r−k C(n−1, r−k) = C(α−n, r)

This “negative upper-index” form is used frequently in inclusion-exclusion arguments in competitive programming.

More Key Identities

Beyond Vandermonde, several identities appear so often in CP that they deserve a permanent place in your toolbox.

Upper Summation

Σ_k=0ⁿ C(k, r) = C(n+1, r+1)

Proof sketch. Induction on n, using the Pascal recurrence C(n+1, r+1) = C(n, r+1) + C(n, r). Alternatively, a committee argument: from {0,…,n} choose r+1 elements and let k be the largest — the remaining r come from {0,…,k−1}, giving C(k,r) choices.

Parallel Summation

Σ_k=0^r C(n+k, k) = C(n+r+1, r)

This counts lattice paths: the number of monotone paths from (0,0) to (n,r) that first reach column k at row n equals C(n+k, k), and the total is C(n+r+1, r) by the hockey-stick identity.

Dixon’s Identity

Σ_k=−a^a (−1)^k C(2a, a+k)³ = (3a)! / (a!)³

More precisely, for non-negative integers a, b, c:

Σ_k (−1)^k C(a+b, a+k) · C(b+c, b+k) · C(c+a, c+k) = (a+b+c)! / (a! · b! · c!)

Dixon’s identity can be proved by the WZ method (see below). In contests it often appears disguised as a triple-sum convolution that simplifies to a multinomial coefficient.

Pfaff–Saalschütz Identity

₃F₂(−n, a, b; c, 1+a+b−c−n; 1) = C(c−a, n) · C(c−b, n) / (C(c, n) · C(c−a−b, n))

This is a balanced identity (the sum of numerator parameters plus 1 equals the sum of denominator parameters). It subsumes Vandermonde as a special case (set a=0). The combinatorial interpretation involves counting lattice paths with weighted steps.

Hypergeometric Series

A hypergeometric series is a power series whose consecutive term ratio is a rational function of the index. The generalized hypergeometric function is:

_pF_q(a₁,…,a_p; b₁,…,b_q; z) = Σ_k=0^∞ [(a₁)_k … (a_p)_k / ((b₁)_k … (b_q)_k)] · z^k / k!

where (a)_k = a(a+1)…(a+k−1) is the Pochhammer symbol (rising factorial). The most common case in combinatorics is the Gauss hypergeometric function ₂F₁(a,b;c;z).

Connection to Binomial Sums

When one of the upper parameters is a negative integer −n, the series terminates after n+1 terms:

₂F₁(−n, b; c; 1) = Σ_k=0ⁿ (−n)_k (b)_k / ((c)_k k!)

Since (−n)_k = (−1)^k n!/(n−k)! = (−1)^k C(n,k) · k!, each term becomes a product of binomial coefficients. This is why almost every binomial sum identity can be restated as a hypergeometric evaluation:

Similarly, Dixon’s identity is a special evaluation of ₃F₂ at z=1, and the Pfaff–Saalschütz identity is a balanced ₃F₂ evaluation. The hypergeometric viewpoint unifies dozens of seemingly unrelated identities into a single framework.

The Term-Ratio Test

Given a sum S = Σ_k t_k, compute the ratio t_k+1/t_k. If it is a rational function of k, the sum is hypergeometric. Factor the numerator and denominator to read off the parameters. For example, if t_k+1/t_k = (k−n)(k+b) / ((k+c)(k+1)), then S is proportional to ₂F₁(−n, b; c; z) evaluated at some z.

The WZ Method

The Wilf–Zeilberger (WZ) method is a mechanical procedure that proves hypergeometric identities. It was developed by Herbert Wilf and Doron Zeilberger in the early 1990s and earned Zeilberger the Steele Prize.

Core Idea

Suppose we want to prove Σ_k F(n,k) = 1 for all n ≥ 0 (after normalizing). The WZ method finds a certificate function R(n,k) such that with G(n,k) = R(n,k) · F(n,k):

F(n+1, k) − F(n, k) = G(n, k+1) − G(n, k)

This is called the WZ equation. Summing both sides over all k (from −∞ to +∞):

Left side: S(n+1) − S(n), where S(n) = Σ_k F(n,k).
Right side: telescopes to 0 (assuming G vanishes at ±∞).

Therefore S(n+1) = S(n) for all n, so S is constant. Checking S(0) = 1 completes the proof.

Example: Proving Σ_k C(n,k)² = C(2n, n)

Set F(n,k) = C(n,k)² / C(2n,n). We want Σ_k F(n,k) = 1. The WZ certificate for this identity is:

R(n,k) = −k² / (2(n+1)(2n+1))

(found by Zeilberger’s algorithm). Let G(n,k) = R(n,k) · F(n,k). One can verify algebraically that F(n+1,k) − F(n,k) = G(n,k+1) − G(n,k). Summing over k, the right side telescopes; the left gives S(n+1) − S(n) = 0. Since S(0) = F(0,0) = 1, we conclude S(n) = 1 for all n. □

Finding the Certificate Algorithmically

Zeilberger’s creative telescoping algorithm works as follows:

1. Write the ratio F(n+1,k)/F(n,k) as a rational function of n and k.
2. Seek R(n,k) = P(n,k)/Q(n,k) (a rational function) satisfying the WZ equation.
3. Clear denominators and match polynomial coefficients — this yields a linear system that can be solved mechanically.
4. If a solution exists of bounded degree, the algorithm finds it. By a theorem of Wilf and Zeilberger, a certificate always exists for proper hypergeometric terms.

In practice, one uses a computer algebra system (Maple, Mathematica, or the EKHAD package by Zeilberger) rather than solving by hand. For competitive programming, the identities derived by the WZ method are what matter — not running the algorithm during a contest.

WZ Pairs You Should Know

Snake Oil Method

The snake oil method, popularized by Herbert Wilf in his book generatingfunctionology, is a systematic technique for evaluating combinatorial sums using generating functions.

Recipe

1. Identify the free variable. In a sum like Σ_k f(n,k), the free variable is n (or whichever index is not summed over).
2. Introduce a GF variable. Multiply by xⁿ and sum over n to form F(x) = Σ_n S(n) xⁿ.
3. Interchange summations. Switch the order of the k-sum and n-sum.
4. Evaluate the inner sum using a known generating function.
5. Extract [xⁿ] F(x) to get S(n) in closed form.

Example 1: Σ_k C(k, n−k)

Let S(n) = Σ_k C(k, n−k). We want a closed form.

Step 1. Multiply by xⁿ and sum: F(x) = Σ_n≥0 S(n) xⁿ = Σ_n Σ_k C(k, n−k) xⁿ.

Step 2. Substitute j = n − k (so n = j + k): F(x) = Σ_k≥0 Σ_j≥0 C(k,j) x^j+k = Σ_k≥0 x^k Σ_j≥0 C(k,j) x^j = Σ_k≥0 x^k (1+x)^k = Σ_k≥0 (x(1+x))^k = 1 / (1 − x − x²).

Step 3. The generating function 1/(1 − x − x²) generates the Fibonacci numbers! So S(n) = F_n+1 (with F₁=F₂=1).

Example 2: Σ_k C(n,k) · C(n,k+1) / C(2n, n+1)

Let S(n) = Σ_k≥0 C(n,k) · C(n, k+1). By Vandermonde, this equals C(2n, n+1) — just set r = n+1 in Σ C(n,k) C(n, r−k) = C(2n, r). So S(n) = C(2n, n+1) = C_n · (n+1), where C_n is the n-th Catalan number.

Example 3: Double Sum via Snake Oil

Evaluate Σ_k C(n+k, 2k) · 2^k. Introduce F(x) = Σ_n S(n) xⁿ, interchange, and use the identity Σ_n≥0 C(n+k, 2k) xⁿ = x^k/(1−x)^2k+1. After simplification, F(x) = 1/(1 − x − 2x/(1−x)²), which can be expanded to find S(n). The details are a good exercise.

C++ Toolkit

Below are core routines that appear in virtually every CP problem involving binomial identities.

Precomputing Binomial Coefficients mod p

// Precompute factorials and inverse factorials mod p
// Supports C(n, k) queries in O(1) after O(N) precomputation
const int MOD = 998244353;
const int MAXN = 2000001;

long long fac[MAXN], inv_fac[MAXN];

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

Lucas’ Theorem for Large n

// Lucas' theorem: C(n, k) mod p for prime p and arbitrary n
// Works by decomposing n and k in base p
long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;
    long long ni = n % p, ki = k % p;
    if (ki > ni) return 0;
    // Small C(ni, ki) mod p — precomputed or direct
    // Here we compute directly for small p
    long long num = 1, den = 1;
    for (long long i = 0; i < ki; i++) {
        num = num * ((ni - i) % p + p) % p;
        den = den * ((i + 1) % p) % p;
    }
    long long small_c = num % p * power(den, p - 2, p) % p;
    return small_c % p * lucas(n / p, k / p, p) % p;
}

Evaluating Vandermonde Convolutions Efficiently

When a problem requires computing Σ_k=0^r C(m,k) · C(n, r−k) and you know the answer is C(m+n, r), just compute a single binomial coefficient. But what if the identity is disguised?

Pattern recognition: Given a sum Σ_k f(k) · g(r−k), check if f and g are columns of Pascal’s triangle. If f(k) = C(A, k) and g(j) = C(B, j), the sum is C(A+B, r) by Vandermonde.

NTT-Based Polynomial Convolution

// When identities don't simplify, compute the convolution directly
// using NTT (Number Theoretic Transform) in O(n log n)
#include <vector>
using namespace std;

const int MOD = 998244353, g = 3;

void ntt(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long w = inv ? power(g, MOD - 1 - (MOD - 1) / len, MOD)
                         : power(g, (MOD - 1) / len, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        long long n_inv = power(n, MOD - 2, MOD);
        for (auto& x : a) x = x * n_inv % MOD;
    }
}

vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(result_size);
    return a;
}

// Usage: convolve the k-th column of Pascal's triangle
// a[k] = C(m, k), b[k] = C(n, k) => result[r] = C(m+n, r)
vector<long long> vandermonde_via_ntt(int m, int n) {
    precompute();
    int R = m + n;
    vector<long long> a(m + 1), b(n + 1);
    for (int k = 0; k <= m; k++) a[k] = C(m, k);
    for (int k = 0; k <= n; k++) b[k] = C(n, k);
    return multiply(a, b); // result[r] == C(m+n, r) for each r
}

CP Applications

Recognizing Vandermonde in Disguise

Many contest problems give a double sum or a recurrence whose closed form is a Vandermonde convolution. The key signal: a sum of products of two binomial coefficients where the indices add up to a constant.

Example (Codeforces style): Count the number of ways to distribute r identical balls into two groups of urns (m urns of type A, n urns of type B), where each urn holds at most 1 ball.

If k balls go into type-A urns: C(m,k) choices. Then r−k go into type-B: C(n, r−k) choices. Total = Σ_k C(m,k) C(n, r−k) = C(m+n, r). The problem reduces to a single binomial coefficient!

Multi-Convolution Problems

When you have three or more groups, Vandermonde generalizes naturally:

Σ_k1+k2+k3=r C(a, k₁) · C(b, k₂) · C(c, k₃) = C(a+b+c, r)

This follows by applying Vandermonde twice: first convolve a and b to get C(a+b, ·), then convolve that with c. In code, if the groups are too large for direct computation, use NTT convolution.

Contest Walkthrough: Lattice Path Counting

Problem: Count lattice paths from (0,0) to (n,m) that pass through at least one of the points (a,b) or (c,d), modulo 10⁹+7.

By inclusion-exclusion: paths through (a,b) + paths through (c,d) − paths through both. Paths from (0,0) to (a,b) to (n,m) = C(a+b, a) · C((n−a)+(m−b), n−a). This is a product of two binomial coefficients — each computed in O(1) with precomputed factorials.

Contest Walkthrough: Alternating Sum

Problem: Compute Σ_k=0ⁿ (−1)^k C(n,k) · C(2n−2k, n−k) modulo a prime p.

Rewrite C(2n−2k, n−k) = C(2(n−k), n−k). Let j = n−k: the sum becomes Σ_j=0ⁿ (−1)^n−j C(n, n−j) C(2j, j) = (−1)ⁿ Σ_j (−1)^j C(n,j) C(2j,j).

Now recognize this as the coefficient extraction from the generating function (1−4x)^−1/2 composed with sign changes. Using the identity Σ_j C(n,j) (−1)^j C(2j,j) x^j evaluated at x=1, and the Chu–Vandermonde identity, the sum evaluates to C(2n,n) · (−1)ⁿ / 2ⁿ (with appropriate modular inversion).

When No Closed Form Exists

Not every binomial sum has a nice closed form. If Zeilberger’s algorithm produces a recurrence of order > 1, there may be no “simple” expression. In that case:

• Matrix exponentiation: If the recurrence has constant coefficients and bounded order d, compute S(n) in O(d³ log n).
• NTT convolution: If the sum is a literal convolution of two sequences, compute it in O(n log n).
• Prefix sums: For cumulative binomial sums Σ_k=0^m C(n,k), use the recurrence C(n, k+1) = C(n,k) · (n−k)/(k+1) to accumulate in O(m).

Summary

Hypergeometric identities transform intimidating binomial sums into simple closed forms. Here is the hierarchy of techniques, from easiest to most powerful:

1. Direct identity: Vandermonde, upper summation, parallel summation. Recognize the pattern and write C(m+n, r) directly.
2. Snake oil: When the identity isn’t obvious, introduce a generating function variable, swap sums, and extract coefficients.
3. Hypergeometric classification: Compute the term ratio, identify the _pF_q type, and look up known evaluations (Dixon, Pfaff–Saalschütz, etc.).
4. WZ method: For proving identities or finding recurrences. Best used offline with a CAS; in contests, use the results it produces.
5. NTT / brute force: When no closed form exists, fall back to algorithmic evaluation.

In the next post, we explore Möbius Inversion on Posets — a powerful generalization of inclusion-exclusion that operates on partially ordered sets.