Las identidades combinatorias siempre fueron un tema favorito para mí, desde mis tiempos de competidor olímpico en el bachillerato. Actualmente mis intereses de investigación matemática se han enfocado en la combinatoria, y revivir estos pasatiempos juveniles es un deleite.
Hojeando un texto clásico, Enumerative Combinatorics de Richard Stanley, encontré la siguiente identidad combinatoria.
Problema. Demuestre que $latex \displaystyle \sum_{j=0}^n 2^{-j} \binom{n+j}{j}=2^n$.
En un comentario a un ejercicio, Stanley menciona la relación de esta identidad con un problema clásico de la teoría de probabilidad, sobre el cual hablaremos a continuación.
El problema de las cerillas de Banach
Consideremos la siguiente situación.
Un matemático carga consigo dos cajas de cerillas, una en su bolsillo derecho y otra en el izquierdo. Cada vez que desea un cigarrillo, elige uno de sus bolsillos al azar, y toma una cerilla de la caja correspondiente. Suponga que el matemático se encuentra por primera vez con una caja vacía. Si cada caja posee $latex N$ cerillas, ¿cuál es la probabilidad de que en ese momento la otra caja contenga exactamente $latex r$ cerillas?
Citamos parte del texto de William Feller [1], quien de paso aclara que el problema hace jocosa referencia al hábito de fumar de Stefan Banach. Vale la pena mencionar que Banach fue uno de los matemáticos más influyentes del s. XX, y formó parte de una escuela matemática muy original e idiosincrásica que estuvo activa en Polonia en el período entre las dos guerras mundiales.
Denotamos por $latex u_r$ la probabilidad de que, al descubrir por primera vez una caja vacía, la otra contenga exactamente $latex r$ cerillas, con $latex 0 \leq r \leq N$. Ante todo, notamos que el problema asume implícitamente que cada bolsillo es elegido con igual probabilidad, y que cada elección ocurre independientemente de las demás. Estamos por tanto ante un caso particular de los ensayos de Bernoulli. Si declaramos como "éxito" la elección del bolsillo izquierdo, las probabilidades de éxito y fracaso son $latex p=q=1/2$.
Para que la caja izquierda esté vacía por primera vez cuando la derecha contenga $latex r$ cerillas, debimos tener exactamente $latex N-r$ fracasos antes del $latex N+1$-ésimo éxito. De acuerdo a una fórmula clásica, la probabilidad de que esto ocurra viene dada por
$latex \displaystyle \binom{(N+1)+(N-r)-1}{N-r} \left( \frac{1}{2} \right) ^{-(N+1)} \left( \frac{1}{2} \right)^{-(N-r)}= \binom{2N-r}{N-r}2^{-2N+r-1} $
—Cf. [1], sección VI.8, fórmula (8.1), p. 165. Por simetría, obtenemos la misma expresión al analizar el caso de la caja derecha. En consecuencia
$latex \displaystyle u_r=\binom{2N-r}{N-r}2^{-2N+r} $.
Finalizamos observando que al recorrer $latex r=0,\dots N$ obtenemos la totalidad de posibles casos, por lo cual las probabilidades $latex u_r$ suman 1, i.e.
$latex \displaystyle \sum_{r=0}^N \binom{2N-r}{N-r}2^{-2N+r}=1$.
Efectuando el cambio de variables $latex j=N-r$ tenemos que $latex 0\leq j \leq N$ y la expresión anterior toma la forma
$latex \displaystyle \sum_{j=0}^N \binom{N+j}{j}2^{-N-j}=1$
Multiplicando ambos lados por $latex 2^N$ obtenemos la identidad deseada. $latex \square$
Un punto de vista algebraico
Posteriormente, me di cuenta de que esta bonita identidad es muy clásica; de hecho, la encontré como ejemplo en otro excelente texto de matemática discreta, Concrete Mathematics [2]; véase la ecuación (5.20) de la p. 167.
En dicho texto, el resultado en cuestión se deduce a partir de cierta identidad algebraica; cf. ecuación (5.19) de la p. 166. Las dos demostraciones que se presentan ahí me parecieron muy ingeniosas... quizás demasiado ingeniosas para el lector casual. Luego, sentí la curiosidad de intentar mi propia demostración, que resumo a continuación.
Proposición. $latex \displaystyle \sum_{k=0}^m \binom{m+r}{k} x^ky^{m-k}=\sum_{k=0}^m \binom{-r}{k}(-x)^k(x+y)^{m-k}$.
Demostración. Comenzamos sustituyendo la fórmula para los coeficientes binomiales negativos:
$latex \displaystyle \binom{-r}{k}=(-1)^k \binom{k+r-1}{k}$
Obtenemos así la siguiente versión equivalente de la identidad:
$latex \displaystyle \sum_{k=0}^m \binom{m+r}{k} x^ky^{m-k}=\sum_{k=0}^m \binom{k+r-1}{k}x^k(x+y)^{m-k}$
Para mayor claridad, expandimos la sumatoria al lado derecho:
$latex \displaystyle \binom{r-1}{0} (x+y)^m+ \binom{r}{1} x(x+y)^{m-1} + \binom{r+1}{2} x^2 (x+y)^{m-2} + \dots + \binom{r+m-1}{r}x^m$
Sea $latex 0 \leq k \leq m$ fijo. Deseamos calcular el coeficiente de $latex x^ky^{m-k}$ en la expresión anterior; para ello basta expandir cada sumando con el teorema del binomio y seleccionar el monomio de grado adecuado, obteniendo así
$latex \displaystyle \binom{r-1}{0}\binom{m}{k}+\binom{r}{1}\binom{m-1}{k-1}+\dots+\binom{r+k-1}{k}\binom{m-k}{0}=\sum_{s=0}^k \binom{r-1+s}{s}\binom{m-s}{k-s}$
A partir de la simetría de los coeficientes binomiales tenemos que
$latex \displaystyle \binom{r-1+s}{s}= \binom{r-1+s}{r-1}$, $latex \displaystyle \binom{m-s}{k-s}=\binom{m-s}{m-k}$.
Finalmente aplicamos la identidad (5.26) en ibidem, p. 169 para calcular esta sumatoria:
$latex \displaystyle \sum_{s=0}^k \binom{r-1+s}{s} \binom{m-s}{k-s} = \sum_{s=0}^k \binom{r-1+s}{r-1} \binom{m-s}{m-k}=\binom{r+m}{r+m-k}$
Nuevamente por simetría $latex \displaystyle \binom{r+m}{r+m-k}=\binom{r+m}{k}$, que es justamente el coeficiente de $latex x^ky^{m-k}$ en el lado izquierdo de la identidad pedida. $latex \square$
Ahora sustituimos valores convenientes en nuestra identidad algebraica. Tomando $latex x=y=1$ y $latex r=m+1$ nos queda
$latex \displaystyle \sum_{k=0}^m \binom{2m+1}{k} = \sum_{k=0}^m \binom{k+m}{k} 2^{m-k} $.
Por la simetría de los coeficientes binomiales, la suma $latex \displaystyle \sum_{k=0}^m \binom{2m+1}{k}$ es justamente la mitad de
$latex \displaystyle \sum_{k=0}^{2m+1} \binom{2m+1}{k}=2^{2m+1}$.
Concluimos que $latex \displaystyle \sum_{k=0}^m \binom{k+m}{k} 2^{m-k} =2^{2m}$, o bien $latex \displaystyle \sum_{k=0}^m \binom{k+m}{k} 2^{-k} =2^{m}$.
Otras demostraciones
Tal y como se menciona ibidem, existe otra interpretación probabilística de esta identidad; cf. [3]. A mi entender, la discusión de este artículo difiere del problema de los cerillos de Banach; dejo la referencia para el lector curioso.
Finalizamos retomando a Stanley: en el ejercicio 5.53 (p. 98) se propone deducir la identidad en cuestión tomando las sumas parciales de la expansión en series
$latex \displaystyle \left( 1-\frac{1}{2} \right)^{-n}=1 + \frac{1}{2} n +\frac{1}{4}\binom{n+1}{2}+\dots $
A su vez, esto corresponde a hallar la expansión de la siguiente función generatriz:
$latex \displaystyle \frac{\left(1- \frac{1}{2}X \right)^{-n}}{1-X} $
Esto puede lograrse a través de la llamada fórmula de expansión de Lagrange, una herramienta importante en combinatoria que permite calcular inversos de funciones generatrices de manera sistemática. Exploraré estas ideas en otra publicación. $latex \blacksquare$
Referencias
[1] William Feller, An Introduction to Probability Theory and Its Applications, vol. 1, 3a. ed., Wiley, 1968.
[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2a. ed., Addison-Wesley, 1994.
[3] Tamas Lengyel, "A Combinatorial Identity and the World Series", SIAM Review, vol. 35(2), junio 1993, pp. 294-297.
[4] Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999.