Curioso Coeficiente Binomial De Identidad

Question

Considere el siguiente conjunto de identidades: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ...

Este conjunto de identidades puede ser escrito como

$${m+1\choose k}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}{m-i\choose k}\tag 1$$

o, alternativamente, como

$$\sum_{i=0}^k(-1)^i{k\choose i}{m-i\choose k}=1$$

Curiosamente, la forma en $(1)$ sugiere que cada coeficiente binomial puede ser escrito como una recurrencia sólo en términos de su propia línea (haciendo caso omiso de la $k\choose i+1$ términos como "predeterminado constantes"):

$$a_{n+1}=1+\sum_{i=0}^{k-1}(-1)^i{k\choose i+1}a_{n-i}$$

¿Cuál es la mejor manera de demostrar que estas identidades sostenga en general? Las pruebas de $k=1,2,3$ fueron muy sencillo con un simple factorial de expansión, pero incluso la inducción no parece estar trabajando en el caso general.

También, hacer estas identidades tienen un nombre?

Estas identidades apareció como yo estaba considerando la cantidad

$$\frac{x^n+y^n}{x+y}\pmod{(x+y)^k}$$

Answer 1

He aquí un enfoque a través de la generación de funciones (es posible hacer la prueba más corta, evitando ellos, pero este fue el enfoque directo sin mucha astucia).

Si usted tiene $$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$$ y $$B(x) = b_0 + b_1x + b_2 x^2 + b_3x^3 + \dots$$ (los objetos $A(x)$ $B(x)$ son llamados funciones de generación de las dos secuencias), entonces su producto $$A(x)B(x) = C(x) = c_0 + c_1x + c_2x^2 + c_3x^3+\dots$$ satisface $$c_n = \sum_{r = 0}^{n} a_r b_{n-r}.$$

Cuando, para algunos fijos $k$, las secuencias se $a_n = (-1)^n\binom{k}{n}$$b_n = \binom{n}{k}$, tenemos $$A(x) = \sum_{n=0}^{\infty}(-1)^n\binom{k}{n}x^n = (1 - x)^k $$

y $A$B(x) = \sum_{n=0}^{\infty}\binom{n}{k}x^n = \frac{x^k}{(1-x)^{k+1}} $$ (ver aquí; este es un buen ejercicio), de modo que su producto es $$C(x) = A(x)B(x) = (1-x)^k \frac{x^k}{(1-x)^{k+1}} = \frac{x^k}{1-x} = x^k(1 + x + x^2 + \dots)$$

para los que tenemos, por $n \ge k$, $$1 = c_n = \sum_{i=0}^{n}a_{r} b_{n-r} = \sum_{i=0}^n (-1)^r \binom{k}{r}\binom{n-r}{k} = \sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k} $$ (como $\binom{k}{r} = 0$$r > k$) que es lo que queríamos demostrar.

Answer 2

Como de costumbre, vamos a $[m]=\{1,\ldots,m\}$; contamos los $k$-tamaño de los subconjuntos de a $[m]$ que están contenidas en $[k]$. Por un lado, es evidente que hay exactamente uno de esos conjuntos, a saber, $[k]$ sí. Por otro lado, para cada una de las $i\in[k]$ deje $A_i$ ser parte de la familia de $k$-tamaño de los subconjuntos de a $[m]$ que no contengan $i$. Para cualquier $I\subseteq[k]$ hemos

$$\left|\bigcap_{i\in I}A_i\right|=\binom{m-|I|}k\;,$$

de manera directa de la inclusión-exclusión argumento muestra que

$$\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{m-i}k$$

y de ahí que

$$1=\binom{m}k-\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=0}^k(-1)^i\binom{k}i\binom{m-i}k\;.$$

Answer 3

Aquí es habitual el complejo de las variables de la prueba. Supongamos que tratamos de demostrar que $$\sum_{k=0}^n {n\choose k} (-1)^k {m-k\choose n} = 1$$ Introducir la representación integral $${m-k\elegir n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-k}}{z^{n+1}} \; dz.$$ Esto da por la suma de la integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \sum_{k=0}^n {n\elegir k} (-1)^k \frac{1}{(1+z)^k}\; dz$$ o $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \left(1-\frac{1}{1+z}\right)^n \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \left(\frac{z}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m n}}{z} \; dz.$$

Ahora, esto se evalúa a uno por la inspección, ya que tenemos una ordinaria binomio al $m\ge n$ y un binomio de Newton, que comienza en uno de los al $m<n.$ (Observar que tenemos el coeficiente constante.)

Answer 4

Para completarla, me las arreglé para crear un argumento inductivo para esta identidad, a pesar de que está en ninguna parte cerca de la sencillez y la elegancia de los otros aquí. También he encontrado una forma mucho más simple argumento usando diferencias finitas; les dejo la inducción argumento intacta a continuación el argumento por el polinomio de teoría:

Deje $p(x)$ ser un entero dado valores polinomio de grado $d$. El $n$th adelante finito diferencia está dada por

$$\Delta_p^n(x)=\sum_{i=0}^n(-1)^i{n\choose i}p(x+i)$$

Si $n=d$ obtenemos una constante, es decir, el coeficiente inicial de $p(x)$ tomadas en forma binomial, es decir, $p(x)=\sum_ia_i{x\choose i}$. La fórmula indicada en la pregunta es una consecuencia inmediata de estos hechos, teniendo en $p(x)=\binom xn$.

Aquí está la prueba por inducción para alguien que pueda estar interesado:

Para la prueba de $(1)$, el uso fuerte de inducción y empezar con $\binom {n+1}1 = 1 + \sum_{i=0}^{1-1}(-1)^i{k\choose i+1}{n-i\choose k} = 1+\binom n1 = n+1$. Asumiendo por $k = q$, obtenemos

$${n+1\choose q} = 1+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{n-i\choose q}$$

El establecimiento de una base de caso por $k=q+1$ es una cuestión de considerar

$${q+2\choose q+1}=q+2 = 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{q+1-i\choose q+1}=1+q+1 = q+2$$

después de que hemos vuelto a hacer una suposición de que nuestra fórmula contiene, esta vez para $n=r, r\ge q+1$: ${r+1\choose q+1}=1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}$. Todo lo que queda es poner a prueba la fórmula para $n=r+1$:

$$\begin{align}{r+2\choose q+1} &= 1+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\\ &= {r+1\choose q+1}+{r+1\choose q}\end{align}$$

Por la fuerte inducción, podemos usar las fórmulas para $r+1\choose q+1$ $r+1\choose q$ y escribir

$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+\sum_{i=0}^q(-1)^i{q+1\choose i+1}{r-i\choose q+1}+\sum_{i=0}^{q-1}(-1)^i{q\choose i+1}{r-i\choose q}\\ &=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}\right)\end{align}$$

Esto es un poco desordenado, pero funciona bien:

$$\begin{align}{q+1\choose i+1}{r-i\choose q+1}+{q\choose i+1}{r-i\choose q}&={q+1\choose i+1}{r-i\choose q+1}+\left[{q+1\choose i+1}-{q\choose i}\right]{r-i\choose q}\\ &={q+1\choose i+1}\left[{r-i\choose q+1}+{r-i\choose q}\right]-{q\choose i}{r-i\choose q}\\ &={q+1\choose i+1}{r-i+1\choose q+1}-{q\choose i}{r-i\choose q}\end{align}$$

Va en reversa, ahora tenemos

$$\begin{align}{r+1\choose q+1}+{r+1\choose q}&=2+(-1)^q{r-q\choose q+1}+\sum_{i=0}^{q-1}(-1)^i\left({q+1\choose i+1}{r+1-i\choose q+1}-{q\choose i}{r-i\choose q}\right)\\ &=2+(-1)^q{r-q+1\choose q+1}-(-1)^q{r-q\choose q}+\sum_{i=0}^{q-1}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q-1}(-1)^i{q\choose i}{r-i\choose q}\\ &=2+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-\sum_{i=0}^{q}(-1)^i{q\choose i}{r-i\choose q}\\ &=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1-\sum_{i=1}^{q}(-1)^i{q\choose i}{r-i\choose q}\\ &=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}-{r\choose q}+1+\sum_{j=0}^{q-1}(-1)^j{q\choose j+1}{r-j-1\choose q}\\ {r+2\choose q+1}&=1+\sum_{i=0}^{q}(-1)^i{q+1\choose i+1}{r+1-i\choose q+1}\end{align}$$

Tenga en cuenta que el último paso que sigue a partir de la fuerte inducción debido a la fórmula original (con $r\ge q+1$)

$$\binom rq = 1+\sum_{i=0}^{q-1}{q\choose i+1}{r-1-i\choose q}$$

Answer 5

$$\begin{align} \sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose k} &=\sum_{i=0}^k(-1)^i {k\choose i} {m-i\choose m-k-i}\\ &=\sum_{i=0}^k (-1)^i{k\choose i }{-k-1\choose m-k-i}(-1)^{m-k-i}&&(1)\\ &=(-1)^{m-k}\sum_{i=0}^k {k\choose i }{-k-1\choose m-k-i}\\ &=(-1)^{m-k}{-1\choose m-k}&&(2)\\ &=(-1)^{m-k}{m-k\choose m-k}(-1)^{m-k}&&(3)\\ &=1\qquad\blacksquare\end{align}$$

(1): Parte Superior De La Negación
(2): Vandermonde
(3): Parte Superior De La Negación