Un binomio identidad de Matemática Reflexiones

Question

Aquí está el problema:

Deje $m,n$ ser enteros positivos con $n>m$. Demostrar que

$\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$

Este problema es O243 de Matemática Reflexiones. Solución había sido publicada mediante la integración compleja (https://www.awesomemath.org/assets/PDFs/MR5sol(1).pdf). Sin embargo, me gustaría ver una solución mediante el operador diferencia, si alguna, ya que la forma de los sumando los trae a la mente.

Answer 1

Primero de todo, vale la pena enunciar explícitamente que el problema se supone que $\binom{n}{k}$ es cero cuando $n < 0$ o $n>k$, incluso para $k\geqslant 0$. De hecho, de lo contrario

In[61]:= Table[
 Sum[(-1)^k Binomial[n, k] Binomial[n + m - 2 k, n - 1], {k, 0, 
   n}], {n, 1, 5}, {m, 0, n - 1}]

Out[61]= {{0}, {0, 0}, {0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0, 0}}

Con esas restricciones en el lugar de los pretendidos resultado es, de hecho, reproducido:

In[65]:= Table[
 Sum[(-1)^k Binomial[n, k] Binomial[n + m - 2 k, n - 1] Boole[
    0 <= n - 1 <= n + m - 2 k], {k, 0, n}], {n, 1, 5}, {m, 0, n - 1}]

Out[65]= {{1}, {2, 1}, {3, 3, 1}, {4, 6, 4, 1}, {5, 10, 10, 5, 1}}

In[66]:= Table[Binomial[n, m + 1], {n, 1, 5}, {m, 0, n - 1}]

Out[66]= {{1}, {2, 1}, {3, 3, 1}, {4, 6, 4, 1}, {5, 10, 10, 5, 1}}

Con esto, dijo, el límite superior de la suma de más de $k$$m_\ast = \left\lfloor \frac{m+1}{2} \right\rfloor$: $$ \mathcal{S}(n,m)= \sum_{k=0}^{m_\ast} (-1)^k \binom{n}{k} \binom{n+m-2k}{n-1} $$ El sumando es la hipergeométrica plazo, lo que significa que $$ r(k) = \frac{c_{k+1}}{c_k} = \frac{(-1)^{k+1} \binom{n}{k+1} \binom{n+m-2(k+1)}{n-1} }{(-1)^k \binom{n}{k} \binom{n+m-2k}{n-1} } = \frac{-n+k}{k+1} \frac{-\frac{m+1}{2} + k}{-\frac{m+n-1}{2} + k} \frac{-\frac{m}{2} + k}{-\frac{m+n}{2}+k} $$ y por lo tanto $$ c_k = c_0 \prod_{q=1}^{k} r(q) = \binom{m+n}{n-1} \frac{(-n)_k}{k!} \frac{\left(-\frac{m}{2}\right)_k \cdot \left(-\frac{m+1}{2}\right)_k}{\left(-\frac{m+n}{2}\right)_k \cdot \left(-\frac{m+n-1}{2}\right)_k} $$ Y así, desde la $r(m_\ast) = 0$ hemos $$ \mathcal{S}(n,m) = \binom{n+m}{n-1} \cdot {}_3F_2\left(\left.\begin{array}{cll} -n & -m/2 & -(m+1)/2 \\ & -(m+n)/2 & -(m+n-1)/2 \end{array} \right| 1 \right) $$ Ahora, por estaidentidad: $$ {}_3F_2\left(\left.\begin{array}{cll} -n & a & b \\ & d & 1+a+b-d-n \end{array} \right| 1 \right) = \frac{(d-a)_n \cdot (d-b)_n}{(d)_n \cdot (d-a-b)_n} $$ El uso de esta identidad para $a = -m/2$, $b = -(m+1)/2$ y $d=\epsilon-(m+n)/2$ con la intención de considerar el límite de $\epsilon \to 0$ hemos $$ \mathcal{S}(n,m) = \binom{n+m}{n-1} \lim_{\epsilon \to 0} \frac{ \left(-\frac{n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n}{2} + \epsilon \right)_n}{ \left(-\frac{m+n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n-m}{2} + \epsilon \right)_n } $$ El uso de $$ \left(-\frac{n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n}{2} + \epsilon \right)_n = \frac{1}{2^{2n}} \frac{\Gamma(n+2 \epsilon)}{\Gamma(-n+2\epsilon)} = (-1)^n \frac{\Gamma(1+n-2\epsilon) \Gamma(n+2\epsilon)}{2^{2n} \pi} \sin(2 \pi \epsilon) $$ $$ \left(-\frac{m+n}{2} + \epsilon \right)_n \cdot \left(\frac{1}{2}-\frac{n-m}{2} + \epsilon \right)_n = \frac{\Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) }{\Gamma\left(\frac{-n-m}{2} + \epsilon\right)\Gamma\left(\frac{1+m-n}{2} + \epsilon\right)} = \frac{\Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) }{-\frac{2\pi^2}{\sin(\pi m) + \sin(\pi n - 2 \pi \epsilon)}} \Gamma\left(1 + \frac{m+n}{2} - \epsilon\right) \Gamma\left( \frac{1+n-m}{2} - \epsilon\right) = (-1)^n \frac{\sin(2\pi \epsilon)}{2 \pi^2} \Gamma\left(\frac{n-m}{2} + \epsilon\right) \Gamma\left(\frac{n+m+1}{2} + \epsilon\right) \Gamma\left(1 + \frac{m+n}{2} - \epsilon\right) \Gamma\left( \frac{1+n-m}{2} - \epsilon\right) $$ La combinación y el uso de la duplicación de la fórmula obtenemos $$ \mathcal{S}(n,m) = \binom{n+m}{n-1} \frac{n! (n-1)!}{(n+m)! (n-m-1)!} = \binom{n}{m+1} $$

Answer 2

Aquí está una primaria de la prueba, lo que he encontrado por el estudio de la diferencia finita de operaciones, pero finalmente formula algo más suave mediante la generación de funciones. En cuanto a la diferencia de la operación de enfoque, que fácilmente se demuestra que para la definición habitual de los coeficientes binomiales el lado izquierdo es siempre $0$. De hecho, con $\Delta$ la diferencia de operación definida por $(\Delta f)(x)=f(x+1)-f(x)$ uno tiene $$ (\Delta^n f)(x)=\sum_{k=0}^n(-1)^{n-k}\binom nkf(x+k) $$ y la mano izquierda de los partidos de este a $x=0$$f:x\mapsto(-1)^n\binom{n+m-2x}{n-1}$, que con la habitual definición de los coeficientes binomiales es una función polinómica de grado $n-1$, lo $\Delta^n f=0$.

Así que uno debe asumir la suma en la pregunta, se supone que se truncará cuando se $n+m-2k$ se convierte en negativo. Este puede ser obtenido por la reescritura de la mano izquierda en la pregunta $$ \sum_{k=0}^{n} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{m+1-2k}, $$ lo que hace el menor índice negativo cuando el índice es superior, y con la definición habitual de los coeficientes binomiales negativas de un índice inferior hace cero independientemente. Ahora resulta que este es el mejor interpretadas a partir de la binomial negativa poderes, así que vamos a hacer la parte superior del índice incondicionalmente negativo por "la negación de la parte superior del índice" ($(m+1-2k)-(m+n-2k)-1=-n$): $$ \sum_{k=0}^{n} (-1)^{k}\binom{n}{k}(-1)^{m+1-2k}\binom {n}{m+1-2k}. $$ Ahora vemos que esto es cierto convolución de los coeficientes de $(1-X)^n$ y la mitad de los coeficientes de $(1-X)^{-n}=\sum_i(-1)^i\binom{-n}iX^i$, es decir, aquellos cuya paridad es que de $m+1$. Esto es más convenientemente descrito por hacer la izquierda factor de un polinomio en $X^2$: la fórmula anterior se describe el coeficiente de $X^{m+1}$ en el poder de la serie (que resulta ser un polinomio) $$ (1-X^2)^n(1-X)^{-n}=((1-X)(1+X))^n(1-X)^{-n}=(1+X)^n. $$ Este coeficiente es de curso $\binom n{m+1}$.

Tenga en cuenta que con la pregunta reformulada correctamente, funciona para cualquier $n\in\mathbf N$$\def\Z{\mathbf Z}m\in\Z$.

He aquí una descripción puramente en términos de la diferencia de los operadores. La expresión en la pregunta, naturalmente, conduce a considerar la secuencia de $\binom k{n-1}_{k\in\mathbf N}$ y repetidamente diferencias de elemento dos lugares separados. Por simplicidad extender la secuencia de términos $0$ a la izquierda, por lo que es indexado por $\Z$, y definir el derecho de cambio de operador $R$ en las secuencias de $f$ $R(f)_i=f_{i-1}$ todos los $i\in\Z$; el uso de definir el "atraso diferencia por $2$ operador"$\nabla_2=I-R^2:f\mapsto(f_i-f_{i-2})_{i\in\Z}$. Ahora $I$ $R$ viaje, de manera que al aplicar la fórmula binominal a $(I-R^2)^n$ da $\nabla_2^n(f)_k=\sum_{k=0}^n(-1)^n\binom nkf_{i-2k}$. Con el fin de interpretar el lado izquierdo en la pregunta como tal a afirmar la diferencia, definir secuencias de $C^{(k)}$ a ser la columna "$k$ " de triángulo de Pascal cambiado con el fin de iniciar con un $1$, e $0$-extendido a la izquierda: $$ C^{(k)}_i=\begin{cases}\binom{k+i}k&\text{if %#%#%}\\ 0&\text{if %#%#%;}\end{casos} $$ a continuación, se pide demostrar que $$ \nabla_2^n(C^{(n-1)})_{m+1}=\binom n{m+1}. $$ Ahora observar que con $i\geq0$ ha $i<0$ todos los $\nabla_1=I-R$, e $\nabla_1(C^{(k)})=C^{(k-1)}$, la secuencia con un solo término distinto de cero $k>0$ en el índice de $\nabla_1(C^{(0)})=D=(\delta_{i,0})_{i\in\Z}$ (esto es donde el truncamiento de la negativa del índice de términos muy activa). Esto es suficiente para el cómputo de los $1$, pero tenemos la misma con $0$ en lugar de $\nabla_1^n(C^{(n-1)})$. Afortunadamente $\nabla_2$, y todo lo que los desplazamientos, de forma $$ \nabla_2^n(C^{(n-1)})=(1+R)^n(\nabla_1^n(C^{(n-1)})) =(1+R)^n(D)=\binom ni_{i\in\Z}. $$ La evaluación de este índice $\nabla_1$ da $\nabla_2=(1-R^2)=(1+R)(1-R)=(1+R)\nabla_1$, como se desee.

Answer 3

Maza es Gosper suma... ver Petkovsek, Wilf, Zeilberger "A = B". Que funciona, garantizado. La mayoría de álgebra computacional paquetes de implementar esto.

De lo contrario me agarró Graham, Knuth, Patashnik "Concreto de las matemáticas, las técnicas para manejar tales sumas inteligentes índice de la manipulación se explican claramente allí.

Otro lugar sería Wilf del "aceite de serpiente método" (ver su "generatingfunctionology").

Answer 4

Supongamos que buscamos para evaluar $$\sum_{k=0}^{\lfloor (m+n)/2 \rfloor} {n\elegir k} (-1)^k {m+n-2k\elegir n-1}.$$

Como el enlace en el OP ya no parece estar trabajando me presente la variable compleja prueba.

Observar que en el segundo coeficiente binomial debemos tener $m+n-2k\ge n-1$ a fin de evitar golpear el valor cero en el producto en el numerador del coeficiente binomial, por lo que la parte superior el límite para la suma es, de hecho, $m+1\ge 2k$ con la suma que se

$$\sum_{k=0}^{\lfloor (m+1)/2 \rfloor} {n\elegir k} (-1)^k {m+n-2k\elegir n-1}.$$

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

Esta integral correctamente codifica el rango de $k$ cero al $k$ es mayor que $\lfloor (m+1)/2 \rfloor.$ por lo Tanto, podemos dejar que $k$ ir hasta el infinito en la suma y obtenga $n\gt m$

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+n}}{z^{m+2}} \sum_{k\ge 0} {n\elegir k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+n}}{z^{m+2}} \left(1-\frac{z^2}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)^{n-m} z^{m+2}} (1+2z)^n \; dz.$$

Esto produce que la forma cerrada $$\sum_{q=0}^{m+1} {n\elegir q} 2^q (-1)^{m+1-q} {m+1-q+n-m-1\elegir n-m-1} \\ = (-1)^{m+1} \sum_{q=0}^{m+1} {n\elegir q} (-1)^q 2^q {n-p\elegir n-m-1}.$$

Este es $$(-1)^{m+1} \sum_{q=0}^{m+1} {n\elegir q} (-1)^q 2^q {n-p\elegir m+1-q}.$$

Introducir $${n-p\elegir m+1-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-p}}{z^{m+2-q}} \; dz$$

que una vez más correctamente codifica la gama con la pole en $z=0$ desapareciendo al $q\gt m+1.$ por lo Tanto, podemos ampliar el rango de a $n$ para obtener

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