La forma cerrada de la suma de los coeficientes binomiales?

Question

Tengo la siguiente función:

$T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$ donde $n,d\in \mathbb{N}^0$, e $n,d$ tienen la misma paridad.

Mirando las secuencias de las distintas $d$, parece que la fórmula es un polinomio de grado $d$$n$. Esto es especulación, pero, por ejemplo, donde se define, parece que:

$T_{n}(1)=n$, $T_{n}(2)=\frac{1}{2}n^2$, $T_{n}(3)=\frac{1}{6}n^3-\frac{1}{6}n$, y $T_{n}(4)=\frac{1}{24}n^4-\frac{1}{6}n^2$

De hecho, después de más numérica de pruebas, parece que

$T_n(d)=\frac{n}{d!}\prod\limits_{j=1}^{d-1}(n-(2j-d))$

Así que mi pregunta es, hay alguna forma de confirmar los resultados anteriores y mostrar si o no $T_n(d)$ es un polinomio de grado $d$$n$? Si es así, ¿hay una razón intuitiva de por qué es un polinomio con espaciados uniformemente entero raíces? El resultado parece bastante elegante, si es verdad.

EDIT: Simplificar la expresión anterior, tenemos

$$T_n(d)=\frac{n}{d!}\prod\limits_{j=1}^{d-1}(n-(2j-d))=\frac{n}{d!}\frac{(n-1+(d-1))!!}{(n-1-(d-1))!!}=\frac{2^d n}{n+d}\cdot {\frac{n+d}{2} \choose d}$$

La tercera y la cuarta expresiones en particular, parece que sería muy útil para una combinatoria de la prueba. $n!!$ es el doble estándar factorial.

Answer 1

Aquí es puramente simbólico enfoque a través de la Serpiente método del Aceite. (Ver generatingfunctionology para más detalles). Para simplificar las cosas para leer, tenga en cuenta que $n=2m+d$ para algunos entero $m$ desde $n$ $d$ tienen la misma paridad. Por lo tanto la identidad de ser probado es equivalente a

$$T_n(d)=\sum\limits_{k}{k\choose m}{2m+d\choose 2k}=2^d \frac{2m+d}{2m+2d}{m+d\choose d} \tag{1}$$ La suma es sobre todos los números enteros $k$, con el entendimiento de que ${n \choose k}=0$ si $n\geq k\geq 0$.

Para aplicar el Aceite de la Serpiente método, se multiplica el lado izquierdo por $x^d$ y la suma de todos los $d$: $$\sum_{d,k} {k\choose m}{2m+d\choose 2k}x^d=\sum_k \binom{k}{m}\left[\sum_d\binom{2m+d}{2k}x^d\right]\tag{2}$$ El interior de la suma puede ser evaluado por el cambio de $d\to d-2m+2k$ obtener

$$\sum_d\binom{d+2k}{2k}x^{d+2k-2m}=\frac{x^{2k-2m}}{(1-x)^{2k}}$$ donde nos han recordado la binomial negativa de la serie $(1-x)^{-n-1}=\sum_k \binom{k+n}{n} x^k$. Esto deja al exterior suma, que nos movemos por $k\to k+m$ obtener

\begin{align} \sum_k \binom{k}{m} \frac{x^{2k-2m}}{(1-x)^{2k}} &=\sum_k \binom{k+m}{m} \frac{x^{2k}}{(1-x)^{2k+2m}} &(k\to k+2m) \\ &=\frac{1}{(1-x)^{2m}}\sum_k \binom{k+m}{m}\left(\frac{x^2}{(1-x)^2}\right)^k \\ &=\frac{1}{(1-x)^{2m}}\left[1-\frac{x^2}{(1-x)^2}\right]^{-m-1}&(\text{negative binomial series})\\ &=\frac{1}{(1-x)^{2m}}\left(\frac{(1-x)^2}{1-2x}\right)^{m+1}\\ &=\frac{1-x}{(1-2x)^{m+1}} \end{align}

Así hemos obtenido la suma de $d$ en forma cerrada. Pero podemos ampliar esta en un segundo paso, utilizando una vez más la binomial negativa de la serie:

\begin{align} \frac{1-x}{(1-2x)^{m+1}} &=(1-x)\sum_d \binom{m+d}{d}(2x)^d\\ &=\sum_d \binom{m+d}{d}(2x)^d-\sum_d \binom{m+d}{d}2^d x^{d+1}\\ &=\sum_d \binom{m+d}{d}(2x)^d-\sum_d \binom{m+d-1}{d-1}2^{d-1} x^{d}&(\text{%#%#% on 2nd term})\\ &=\sum_d \left[\binom{m+d}{m}-\frac12\binom{m+d-1}{m}\right](2x)^d \end{align}

El término entre corchetes se simplifica a factorizando el primer coeficiente binomial:

\begin{align} 1-\frac12\binom{m+d-1}{m} \binom{m+d}{m}^{-1} &=1-\frac12 \frac{(m+d-1)!}{m!(d-1)!}\cdot \frac{m!\,d!}{(m+d)!}\\ &=1-\frac12 \frac{d}{m+d}\\ &=\frac{2m+d}{2m+2d} \end{align} Esto produce que el total coeficiente de $d\to d-1$

$x^d$$

la cual en comparación con $$2^d\frac{2m+d}{2m+2d}\binom{m+d}{m}$ da el deseo de identidad.

Answer 2

Hay dos maneras de probar su identidad. La primera manera es encontrar la combinatoria interpretación de su suma, y mostrar que coincide con la más obvia combinatoria interpretación de la fórmula.

La otra forma, siguiendo su propia sugerencia, consta de tres pasos:

1. Demostrar que la suma es un polinomio de grado $d$.
2. Encontrar $d$ distintas raíces del polinomio por el taponamiento de ellos en la suma y demostrando que se evalúa a cero. Ya que las raíces son distintas, esto determinar el polinomio de hasta un constante múltiples.
3. Determinar la constante mediante el cálculo de la suma en algunos valores de $n$ para que no se desvanezca.

El primer paso es fácil. En primer lugar, observe que cada una de las $\binom{n}{n-2k} $ es un polinomio de grado $n-2k$$n$. Segundo, los factores asociados puede ser escrito como $\binom{\ell+(n-d)/2}{\ell}$ donde $\ell=k-(n-d)/2$, que es un polinomio de grado $\ell$$n$. El total de grados de ambos factores es $n-2k+\ell=(n+d)/2-k\leq(n+d)/2-(n-d)/2=d$. Esto completa el primer paso.

El segundo paso es complicado por el hecho de que tenemos que lidiar con el negativo de los coeficientes binomiales, a pesar de que estos probablemente puede ser evitado para el tercer paso. Os dejo estas dos pasos.

Answer 3

Otro útil aparentemente clásica técnica de los usos básicos complejo variables.

Supongamos que buscamos para evaluar $$\sum_{k\ge m} {k\elegir m} {2m+d\elegir 2k} = \sum_{k\ge m} {k\elegir m} {2m+d\elegir 2m+d-2k}$$ donde el segundo coeficiente binomial sirve para delimitar la parte superior cota de la gama de $k$ que es finito.

Inicio de $${2m+d\elegir 2m+d-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m+d-2k+1}} (1+z)^{2m+d} \; dz.$$

Esto le da la siguiente integral por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k\ge m} {k\elegir m} \frac{1}{z^{2m+d-2k+1}} (1+z)^{2m+d} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{2m+d+1}} \sum_{k\ge m} {k\elegir m} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{2m+d+1}} \sum_{k\ge 0} {k+m\elegir m} z^{2k+2m} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{d+1}} \sum_{k\ge 0} {k+m\elegir m} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{d+1}} \frac{1}{(1-z^2)^{m+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+d-1}}{z^{d+1}} \frac{1}{(1-z)^{m+1}} \; dz.$$

La extracción de los coeficientes obtenemos $$\sum_{q=0}^d {m+d-1\choose q} {d-q+m\choose m}.$$

El uso de otro integral como en $${d-q+m\elegir m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{d-q+m} \; dz.$$ para obtener

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{q=0}^d {m+d-1\elegir q} \frac{1}{z^{m+1}} (1+z)^{d-q+m} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \sum_{q=0}^d {m+d-1\elegir q} (1+z)^{-q}\; dz.$$

La definición de la integral es cero para $m+d-1 \ge q>d$, por lo que podemos extender la suma de $m+d-1$, al pasar $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \sum_{q=0}^{m+d-1} {m+d-1\elegir q} (1+z)^{-q}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \left(1+\frac{1}{1+z}\right)^{m+d-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \left(\frac{2+z}{1+z}\right)^{m+d-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{m+1}} (2+z)^{m+d-1} \; dz.$$

Ahora podemos extraer los coeficientes para obtener $$[z^m] (1+z) (2+z)^{m+d-1} = [z^m] (2+z)^{m+d-1} + [z^{m-1} ] (2+z)^{m+d-1} \\ = 2^{d-1} {m+d-1\elegir m} + 2^d {m+d-1\elegir m-1}.$$

Esto necesita un poco de re-escritura para hacer que coincida con la otra respuesta. Tenemos $$2^{d-1} {m+d-1\elegir d-1} + 2^d {m+d-1\elegir d} \\ = 2^{d-1} \frac{d}{m+d} {m+d\elegir d} + 2^d \frac{m}{m+d} {m+d\elegir d} \\ = 2^d {m+d\elegir d} \left(\frac{1}{2} \frac{d}{m+d} + \frac{m}{m+d} \right) \\ = 2^d {m+d\elegir d} \frac{2m+d}{2m+2d}.$$

Ejercicio interesante. No hay otro igual en este MSE enlace.

Observe que estos cálculos fueron realizados sin la intervención de un equipo, excepto para comprobar la aritmética.

Un seguimiento de cuándo este método apareció en el MSE, y por el que se inicia en este MSE enlace.