Tratando de demostrar que$p$ prime divide$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

Question

Así que estoy tratando de demostrar que para cualquier número natural $1\leq k<p$, $p$ primer divide:

$$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$

La escritura de estos elección de las funciones en factorial forma, puedo obtener:

$$\frac{(p-1)!}{k!(p-(k+1))!} + \frac{(p-2)!}{(k-1)!(p-(k+1))!} + \cdots + \frac{(p-k)!}{1!(p-(k+1))!} + 1$$

Así como se puede ver cada término, excepto el último tiene un $(p-(k+1))!$ factor en su denominador. He intentado algunas cosas con el entero de las particiones, trató de hacer algunas factorización y simplificación, etc. Pero no puedo ver cómo demostrar que $p$ divide a esta expresión. Probablemente voy a tener que usar el hecho de que $p$ es primo de alguna manera, pero no estoy seguro de cómo. Alguien me puede ayudar? Gracias.

Edit: Prueba por inducción es también una posibilidad supongo, pero ese enfoque me parece muy complejo, ya que el cambio de k cambia cada término, pero la última.

Answer 1

$$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p k}{1} + 1= \sum_{i=0}^k\binom{p-k-1+i}i =\binom pk, $$ y es bien sabido que un primer $p$ divide a todos los coeficientes binomiales $\binom pk$ $k\notin\{0,p\}$ (cf. el Frobenius endomorfismo de los anillos de la característica $p$). El hecho de que $\sum_{i=0}^k\binom{n+i}i=\binom{n+k+1}k$ es inmediata por la recurrencia en $k$ desde el Pascal es la regla, la base de la recurrencia de la la definición de los coeficientes binomiales.

Si prefieres combinatoria argumentos para álgebra: usted puede entender la suma de identidad por la clasificación de la $k$-combinaciones de una $p$-ajuste de acuerdo con el primer elemento que es no en el $k$-combinación (si el primer elemento de la $p$no en el $k$-combinación, entonces uno tiene un $k$-combinación de los restantes $p-1$; si el primer elemento es en el $k$-combinación pero el segundo no, a continuación, $k-1$ restante de los $p-2$ elementos deben ser elegidos para completar el $k$-combinación; y así sucesivamente, hasta que el elemento $k+1$ que no puede ser en el $k$-combinación si todos los valores antes de que ya están en, contribuyendo $1$), y se puede entender la divisibilidad $p\mid\binom pk$ por el hecho de que por cíclicamente de la rotación $k$-combinaciones, se pueden agrupar en órbitas de $p$ diferentes $k$-combinaciones de cada uno.

Answer 2

Dejando $k=p-1$, encontramos que la expresión es igual a $p$ sumandos de valor de $1$ cada uno.

---

Tal vez el problema no fue destinada a la lectura "para algunos naturales", sino "para todos los naturales" números de $1\le k<p$. La declaración es verdad, una vez que observador que la suma es, simplemente,$p\choose k$. Para ver esta combinatoria, tenga en cuenta que usted puede elegir $k$ $p$ objetos mediante la selección de $r$$0\le r \le k$, luego tomar la primera a $r$ objetos, no tome la siguiente objeto y elija $k-r$ de los restantes $p-1-r$ objetos.

Finalmente, $p\choose k$ $0<k<p$ es un múltiplo de a $p$, debido, por ejemplo, $p$ divide $p!$ pero divide ni $k!$ ni $(p-k)!$. (Aquí es donde tenemos que $p$ es primo),