Identidades de Vandermonde y sus generalizaciones

La identidad de Vandermonde: enunciado y pruebas

La identidad de Vandermonde establece: para $m, n, r \in \mathbb{Z}_{\geq 0}$,

$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$.

Prueba combinatoria. Queremos contar los subconjuntos de $r$ elementos de un conjunto de $m+n$ elementos (con $m$ "rojos" y $n$ "azules"). Para cada $k \in \{0,1,\ldots,r\}$, elegimos $k$ rojos ($\binom{m}{k}$ formas) y $r-k$ azules ($\binom{n}{r-k}$ formas). Sumando sobre $k$: $\sum_k \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$. $\blacksquare$

Prueba algebraica (coeficientes de polinomios). $(1+x)^m(1+x)^n = (1+x)^{m+n}$. El coeficiente de $x^r$ en el lado izquierdo es $\sum_k \binom{m}{k}\binom{n}{r-k}$ (Leibniz); en el lado derecho es $\binom{m+n}{r}$. $\blacksquare$

Prueba por identidad de Abel (generalización). Existe una versión con diferencias finitas: $\sum_{k=0}^n \binom{n}{k} f(k) g(n-k)$, donde $f, g$ son funciones cualquiera. La identidad de Vandermonde es el caso $f(k) = \binom{m}{k}$, $g(j) = \binom{p}{j}$.

Generalizaciones: Chu–Vandermonde y coeficientes generalizados

Identidad de Chu–Vandermonde. Para $n$ entero no negativo y $x, y$ cualquiera (incluso reales o formales):

$\sum_{k=0}^{n} \binom{x}{k}\binom{y}{n-k} = \binom{x+y}{n}$,

donde $\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}$ es el coeficiente binomial generalizado (polinomio en $x$ de grado $k$). La demostración se reduce a verificar la identidad como polinomio en $x$ e $y$: basta comprobarla para $x = 0, 1, 2, \ldots, n$ (donde coincide con Vandermonde clásica) y extender por densidad polinomial.

Identidad de Zhu–Vandermonde (con potencias superiores). Una generalización menos conocida: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}(-1)^k = \binom{n-m}{r}$. Se demuestra usando $(1+x)^n (1+x)^{-m} = (1+x)^{n-m}$ y expandiendo $(1+x)^{-m} = \sum_k \binom{-m}{k} x^k = \sum_k (-1)^k \binom{m+k-1}{k} x^k$.

Cuadrado de Vandermonde. Caso especial $m = n = r$: $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$. Esta es una de las identidades más usadas en olimpiadas: el cuadrado central del coeficiente binomial.

Identidad de Vandermonde con multiplicación superior. $\sum_{k} \binom{r}{k}\binom{s}{n-k}\binom{t}{m-k} = \binom{r+s}{n}\binom{r+t}{m}$... hay generalizaciones hipergeométricas (serie ${}_{2}F_1$). Para olimpiadas, basta manejar Vandermonde estándar, Chu–Vandermonde y el caso del cuadrado.

El determinante de Vandermonde: definición y aplicaciones

La matriz de Vandermonde con parámetros $x_1, \ldots, x_n$ es:

$V = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ \vdots & & & & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{pmatrix}$.

Su determinante es el famoso determinante de Vandermonde: $\det(V) = \prod_{1 \leq i < j \leq n} (x_j - x_i)$.

Demostración por inducción. Para $n=2$: $\det\begin{pmatrix}1&x_1\\1&x_2\end{pmatrix} = x_2-x_1$. Para el paso inductivo: restamos la columna $j-1$ multiplicada por $x_1$ de la columna $j$ (de derecha a izquierda). La primera fila queda $(1,0,0,\ldots,0)$ y el determinante se reduce a $\det(V_{n-1}(x_2,\ldots,x_n)) \cdot \prod_{j=2}^n (x_j - x_1)$. Por hipótesis inductiva, $\det(V_{n-1}) = \prod_{2\leq i<j\leq n}(x_j-x_i)$, y multiplicando se obtiene el resultado.

Interpolación de Lagrange como consecuencia. La no-singularidad de $V$ cuando los $x_i$ son distintos (det $\neq 0$) garantiza la existencia y unicidad del polinomio de grado $\leq n-1$ que pasa por $n$ puntos con abscisas distintas. Esto fundamenta la interpolación de Lagrange, un arma olímpica de primer nivel.

Aplicación directa. Si queremos demostrar que una expresión de la forma $\prod_{i<j}(a_i-a_j)$ es divisible por un entero $m$, puede ser útil interpretarla como determinante de Vandermonde de enteros y usar propiedades del determinante (multilinealidad, reducción mod $m$).

Identidades de Vandermonde en problemas combinatorios

Truco de la convolutoria. Muchas sumas de la forma $\sum_k f(k)g(n-k)$ se evalúan como coeficiente de $x^n$ en el producto de generatrices de $\{f(k)\}$ y $\{g(k)\}$. La identidad de Vandermonde es el caso $f(k) = \binom{m}{k}$ y $g(k) = \binom{p}{k}$.

Identidad de Chu–Vandermonde inversa. $\sum_{k=0}^r (-1)^k \binom{r}{k} \binom{n+k}{m} = \binom{n}{m-r}$. Esta forma con signos alternantes aparece en inclusión–exclusión avanzada y en la demostración de identidades de sumas de cuadrados.

Suma de cuadrados de binomiales. $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$. Una prueba elegante: es la Vandermonde con $m=n=r=n$. Otra prueba: es el coeficiente de $x^n$ en $(1+x)^n(1+1/x)^n x^n$, que es el coeficiente de $x^n$ en $(x+1)^{2n} = \sum_k \binom{2n}{k} x^k$.

Suma de cuadrados centralizada. $\sum_{k=0}^n \binom{n}{k}^2 (-1)^k = \begin{cases} (-1)^{n/2}\binom{n}{n/2} & \text{si } n \text{ par} \\ 0 & \text{si } n \text{ impar.}\end{cases}$ Esta identidad se obtiene de la convolutoria de $\binom{n}{k}$ y $(-1)^k\binom{n}{k} = \binom{-n+k-1}{k}(-1)^n$... o más directamente del coeficiente de $x^n$ en $(1-x)^n(1+x)^n = (1-x^2)^n$.

Conexión con conteo de caminos. La identidad $\sum_k \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ cuenta caminos de longitud $r$ en una grilla $m\times n$: $k$ pasos horizontales en el bloque de $m$ y $r-k$ pasos en el bloque de $n$. Esta interpretación geométrica permite generalizaciones a varias dimensiones.

Problema IMO resuelto: determinante de Vandermonde y divisibilidad

Problema (IMO Shortlist 2003, A2 / adaptación). Sean $x_1, \ldots, x_n$ enteros distintos. Demostrar que $\prod_{1 \leq i < j \leq n} \frac{x_j - x_i}{j - i}$ es un entero.

Solución. Sea $D = \prod_{1\leq i<j\leq n}(x_j-x_i)$ y $V_n = \prod_{1\leq i<j\leq n}(j-i) = \prod_{k=1}^{n-1} k! = 1!2!\cdots(n-1)!$.

Tenemos $D/V_n = \det(V(x_1,\ldots,x_n)) / \det(V(1,2,\ldots,n))$.

Ahora, $\det(V(1,2,\ldots,n)) = V_n$ es el determinante de Vandermonde estándar. El cociente $D/V_n$ puede interpretarse como sigue: el determinante de la matriz $M_{ij} = \binom{x_i}{j-1}$ (ya que las columnas de la matriz de Vandermonde de $x_1,\ldots,x_n$ pueden cambiarse de base: la base $\{1, t, t^2,\ldots, t^{n-1}\}$ por la base $\{\binom{t}{0}, \binom{t}{1}, \ldots, \binom{t}{n-1}\}$, lo que divide el determinante exactamente por $(n-1)!(n-2)!\cdots 1!$).

El cambio de base tiene determinante $1/(0!1!2!\cdots(n-1)!) = 1/V_n$ (triangular superior con unos en la diagonal). Por tanto $\det(M) = D/V_n$. Como $M_{ij} = \binom{x_i}{j-1} \in \mathbb{Z}$ (coeficientes binomiales de enteros), $\det(M) \in \mathbb{Z}$. $\blacksquare$