Estoy tratando de resolver la siguiente fórmula:
$$\sum^{\lfloor (n-1)/2\rfloor}_{m=k}\binom{m}{k}\binom{n}{2m+1} = \binom{n-k-1}{k}2^{n-2k-1}$$
Sin embargo, no tengo ni idea. ¿Alguien puede arrojar algo de luz sobre esto?
Respuestas
¿Demasiados anuncios?
Marko Riedel
Puntos
19255
Buscamos a verificar para $n-k-1\ge k$ la identidad
$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\elegir k} {n\elegir 2m+1} = {n-k-1\elegir k} 2^{n-2k-1}.$$
El LHS es
$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\elegir k} {n\elegir n-2m-1} = \sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\elegir k} [z^{n-2m-1}] (1+z)^n \\ = \sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\elegir k} [z^{n}] z^{2m+1} (1+z)^n.$$
Ahora observe que cuando se $2m+1\gt n$ cero del coeficiente de extractor de lo que en realidad se codifica el límite superior de la suma, que podemos extender hasta el infinito, ya que no hay contribución de los valores de $m$. Obtenemos
$$[z^n] (1+z)^n \sum_{m\ge k} {m\elegir k} z^{2m+1} = [z^{n-1}] (1+z)^n \sum_{m\ge k} {m\elegir k} z^{2m} \\ = [z^{n-1}] (1+z)^n \sum_{m\ge 0} {m+k\elegir k} z^{2m+2k} = [z^{n-2k-1}] (1+z)^n \sum_{m\ge 0} {m+k\elegir k} z^{2m} \\ = [z^{n-2k-1}] (1+z)^n \frac{1}{(1-z^2)^{k+1}} = [z^{n-2k-1}] (1+z)^{n-k-1} \frac{1}{(1-z)^{k+1}}.$$
Extraer el coeficiente encontramos
$$\sum_{q=0}^{n-2k-1} {n-k-1\elegir q} {n-2k-1-p+k\elegir k} \\ = \sum_{q=0}^{n-2k-1} {n-k-1\elegir q} {n-k-1-p\elegir k}.$$
El producto de binomios es
$$\frac{(n-k-1)!}{p! \times k! \times (n-2k-1-q)!} = {n-k-1\elegir k} {n-2k-1\elegir q}$$
y llegamos
$${n-k-1\elegir k} \sum_{q=0}^{n-2k-1} {n-2k-1\elegir q} = {n-k-1\elegir k} 2^{n-2k-1}$$
como se reivindica.
Markus Scheuer
Puntos
16133
Aquí es una variación del tema. Es conveniente utilizar el coeficiente de operador $[z^n]$ para denotar el coeficiente de $z^n$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}
Obtenemos para $n\geq 2k+1$: \begin{align*} \color{blue}{\sum_{m=k}^{\left\lfloor\frac{n-1}{2}\right\rfloor}}&\color{blue}{\binom{m}{k}\binom{n}{2m+1}}\\ &=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{m+k}{m}\binom{n}{2m+2k+1}\tag{1}\\ &=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{-k-1}{m}(-1)^m\binom{n}{n-2m-2k-1}\tag{2}\\ &=\sum_{m=0}^\infty[z^m](1-z)^{-k-1}[u^{n-2m-2k-1}](1+u)^n\tag{3}\\ &=[u^{n-2k-1}](1+u)^n\sum_{m=0}^\infty u^{2m}[z^m](1-z)^{-k-1}\tag{4}\\ &=[u^{n-2k-1}](1+u)^n\left(1-u^2\right)^{-k-1}\tag{5}\\ &=[u^{n-2k-1}](1+u)^{n-k-1}(1-u)^{-k-1}\tag{6}\\ &=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{-k-1}{n-2k-1-j}(-1)^{n-2k-1-j}\tag{7}\\ &\color{blue}{=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{n-k-j-1}{k}}\tag{8}\\ &=\sum_{j=0}^{\infty}[u^j](1+u)^{n-k-1}[z^k](1+z)^{n-k-j-1}\tag{9}\\ &=[z^k](1+z)^{n-k-1}\sum_{j=0}^\infty (1+z)^{-j}[u^j](1+u)^{n-k-1}\tag{10}\\ &=[z^k](1+z)^{n-k-1}\left(1+\frac{1}{1+z}\right)^{n-k-1}\tag{11}\\ &=[z^k](2+z)^{n-k-1}\tag{12}\\ &\color{blue}{=\binom{n-k-1}{k}2^{n-2k-1}}\tag{13} \end{align*} y el reclamo de la siguiente manera.
Comentario:
En (1) nos cambio el índice de $j$ a inicio de $j=0$.
En (2) utilizamos el binomio identidad $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$\binom{p}{q}=\binom{p}{p-q}$.
En (3) se aplica el coeficiente de operador en dos ocasiones y también establece el límite superior para $\infty$ sin cambiar nada, ya que estamos añadiendo ceros sólo.
En (4) utilizamos la linealidad del coeficiente de operador y aplicar la regla de $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
En (5) aplicamos la norma de sustitución del coeficiente de operador con $z=u^2$
\begin{align*} A(u)=\sum_{m=0}^\infty a_m u^m=\sum_{m=0}^\infty u^m [z^m]A(z) \end{align*}En (6) reordenar los términos, a fin de obtener otro binomio identidad de (1) en el paso siguiente.
En (7) se extrae el coeficiente de $[u^{n-2k-1}]$.
En (8) se aplican las mismas señas de identidad, como en (2).
En (9) se aplica el coeffcient de operador de nuevo dos veces.
En (10) vamos a hacer un reordenamiento de manera similar como en (4).
En (11) vamos a aplicar la norma de sustitución, como hicimos en (5).
En (12) vamos a hacer algunas simplificaciones.
En (13) vamos a seleccionar el coeficiente de $[z^k]$.
Notas: Dos pasos podrían ser de especial interés.
(5) a (6): Este es el punto esencial de la torsión para derivar a otro binomio identidad (8) de (1), que también nos permite finalmente se derivan de la RHS de OP.
(11): La transformación \begin{align*} (2+z)^N=\left(1+\frac{1}{1+z}\right)^N(1+z)^N \end{align*} puede ser útil a veces para deshacerse de los sumando $2$.
