prueba (combinatoria y algebraica) de que $\sum_{q=1}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k} - \binom{n}{2k}2^{2k}$

Question

Llegué a la siguiente identidad a través de un intento de problema de deberes: el LHS es mi solución; el RHS, la del libro. Y por lo que he probado son equivalentes. $$\sum_{q=1}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k} - \binom{n}{2k}2^{2k}$$

El significado combinatorio de esta identidad es bastante intuitivo según la letra de la tarea:

"Encuentra el número de formas de formar un grupo de $2k$ personas de $n$ parejas en las que $k,n \in \Bbb N$ y $2k \leq n$ para que al menos una pareja esté incluida en dicho grupo".

Dicho esto, el significado combinatorio del LHS (e incluso del RHS) es bastante claro: itera sobre $q = \{1,2,...,n\}$ parejas, selecciona $2k-2q$ parejas del resto de $n-q$ y luego escoge a una persona de cada uno de estos $2k-2q$ parejas, lo que puede hacerse en $2^{2k-2q}$ formas, para formar el grupo. El RHS lo hace por composición: eliminando los grupos que no contienen una pareja.

Sin embargo, aunque sé lo que se supone que hace el LHS, no sé cómo funciona. Sé que los grupos que no contienen 1 pareja está dada por $\binom{n}{2k}2^{2k}$ (después de todo, este es el caso en el que $q=0$ ), pero no tengo mucha idea de cómo el $\binom{2n}{2k}$ término cuenta el "resto". Y tengo muchas menos ideas sobre cómo podría demostrar esto algebraicamente.

Edición posterior: Me di cuenta de que el $\binom{2n}{2k}$ término simplemente cuenta el número de formas de agrupar $2k$ personas del conjunto $2n$ gente de la $n$ parejas. Así que, por supuesto, todo lo que hay que hacer después es eliminar los grupos que no contengan 1 pareja.

Answer 1

Prueba algebraica . Su identidad equivale a (nótese que el límite superior debe ser $k$ y el límite inferior es $0$ porque nos mudamos $\binom{n}{2k}2^{2k}$ a la izquierda): $$\sum_{q=0}^k \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k}.$$ Ahora tenemos que $$\begin{align*} \sum_{q=0}^k \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)}&= \sum_{q=0}^k \binom{n}{q}2^{2(k-q)}[z^{2k-2q}] (1+z)^{n-q} \\ &=[z^{2k}]4^k(1+z)^n\sum_{q\geq 0} \binom{n}{q} \frac{z^{2q}}{4^q(1+z)^{q}} \\ &=[z^{2k}]4^k(1+z)^n\left(1+\frac{z^2}{4(1+z)}\right)^n\\ &=[z^{2k}]4^k\left(1+z+\frac{z^2}{4}\right)^n\\ &=[z^{2k}]4^k\left(1+\frac{z}{2}\right)^{2n}=\binom{2n}{2k}. \end{align*}$$

Answer 2

Su igualdad se conoce de una forma algo diferente. En primer lugar, permítanme traer el $\binom{n}{2k}2^{2k}$ El sustraendo de la derecha a la izquierda, donde encaja perfectamente en la suma como un $q=0$ añadir. Así, su igualdad se convierte en \begin{align} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k}. \end{align} A continuación, voy a generalizar esta igualdad sustituyendo $2k$ por $k$ por lo que se convierte en \begin{align} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} = \binom{2n}{k}. \end{align} En esta forma, se trata del Ejercicio 2 de mi juego de deberes de matemáticas 5705 de otoño de 2018 nº 2 donde doy dos soluciones.

Permítanme esbozar aquí la primera solución (véase el enlace anterior para los detalles y para la segunda solución, puramente algebraica):

$\newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)}$ Imagina que tienes $n$ pares de zapatos $\tup{L_1, R_1}, \tup{L_2, R_2}, \ldots, \tup{L_n, R_n}$ , donde el $2n$ zapatos $L_1, R_1, L_2, R_2, \ldots, L_n, R_n$ son todos distinguibles. ¿Cuántas maneras hay de agarrar $k$ de estos $2n$ zapatos, es decir, elegir un $k$ -subconjunto de elementos del conjunto de todos los $2n$ ¿Zapatos? Por un lado, es evidente que hay $\dbinom{2n}{k}$ muchas maneras. Por otro lado, he aquí una forma más complicada de contar estas formas: Digamos que usted está agarrando $q$ pares completos (es decir, hay $q$ muchos $i$ 's tal que se agarran ambos $L_i$ y $R_i$ ). El número de formas de hacerlo es $\dbinom{n}{q}\dbinom{n-q}{k-2q}2^{k-2q}$ (porque hay $\dbinom{n}{q}$ muchas opciones para estos $q$ pares completos, entonces $\dbinom{n-q}{k-2q}$ muchas opciones para elegir cuál de las $n-q$ pares de los que se agarra un zapato, y finalmente $2^{k-2q}$ opciones para elegir entre los zapatos izquierdo y derecho). Sumando esto sobre todos los valores posibles de $q$ concluimos que el número total de formas de agarrar $k$ fuera del $2n$ zapatos es $\displaystyle \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q}$ . Ahora compara esto con la primera respuesta, y la identidad se deduce.

Este ejercicio lo aprendí de Titu Andreescu, Zuming Feng, Un camino hacia la combinatoria para estudiantes universitarios , Birkhäuser 2004 donde la 1ª prueba combinatoria aparece (como caso particular) como Ejemplo 2.11.

Answer 3

Aquí hay un " aceite de serpiente " prueba de la generalización señalada por @darijgrinberg: \begin{align} \sum_{k \ge 0} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} z^k &= \sum_{q=0}^n \binom{n}{q} \sum_{k=2q}^{n+q} \binom{n-q}{k-2q}2^{k-2q} z^k \\ &= \sum_{q=0}^n \binom{n}{q} \sum_{k=0}^{n-q} \binom{n-q}{k}2^k z^{k+2q} \\ &= \sum_{q=0}^n \binom{n}{q} z^{2q} \sum_{k=0}^{n-q} \binom{n-q}{k}(2z)^k \\ &= \sum_{q=0}^n \binom{n}{q} z^{2q} (1+2z)^{n-q} \\ &= (1+2z)^n \sum_{q=0}^n \binom{n}{q} \left(\frac{z^2}{1+2z}\right)^q \\ &= (1+2z)^n \left(1+\frac{z^2}{1+2z}\right)^n \\ &= (1+2z)^n \left(\frac{(1+z)^2}{1+2z}\right)^n \\ &= (1+z)^{2n} \\ &= \sum_{k \ge 0}\binom{2n}{k} z^k \end{align} Por lo tanto, $$\sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} = \binom{2n}{k}.$$

Answer 4

He aquí una variación del tema, una prueba ligeramente diferente para enriquecimiento. Al tratar de evaluar

$$\sum_{q=0}^k {n\choose q} {n-q\choose 2k-2q} 2^{2k-2q}$$

observamos que (OP observa que $2k\le n$ )

$${n\choose q} {n-q\choose 2k-2q} = \frac{n!}{q! \times (2k-2q)! \times (n+q-2k)!} = {n\choose 2k-2q} {n-2k+2q\choose q}.$$

Esto da

$$\sum_{q=0}^k {n\choose 2q} {n-2q\choose k-q} 2^{2q} = [z^k] (1+z)^n \sum_{q=0}^k {n\choose 2q} \frac{z^q}{(1+z)^{2q}} 2^{2q}.$$

Aquí el extractor de coeficientes impone el límite superior de la suma y encontramos

$$[z^k] (1+z)^n \sum_{q\ge 0} {n\choose 2q} \frac{z^q}{(1+z)^{2q}} 2^{2q} \\ = [z^{2k}] (1+z^2)^n \sum_{q\ge 0} {n\choose 2q} \frac{z^{2q}}{(1+z^2)^{2q}} 2^{2q} \\ = [z^{2k}] (1+z^2)^n \frac{1}{2} \left[ \left(1+\frac{2z}{1+z^2} \right)^n + \left(1-\frac{2z}{1+z^2}\right)^n \right] \\ = [z^{2k}] \frac{1}{2} \left[ (1+z)^{2n} + (1-z)^{2n}\right] = \frac{1}{2} \left[ {2n\choose 2k} + (-1)^{2k} {2n\choose 2k} \right] = {2n\choose 2k}.$$