Deje $n$ ser un entero no negativo, y $k$ un entero positivo. Podría alguien explicarme por qué la identidad $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ se mantiene?
Esta pregunta ya tiene respuestas:
- Prueba de la identidad del palo de hockey (5 respuestas )
Respuestas
¿Demasiados anuncios?
Una forma de interpretar esta identidad es tener en cuenta el número de formas de elegir los $k$ enteros del conjunto $\{1,2,3,\cdots,n+k\}$.
Hay $\binom{n+k}{k}$ maneras de hacer esto, y también puede contar el número de posibilidades teniendo en cuenta el entero más grande elegido. Esto puede variar de $k$$n+k$, y si el entero más grande elegido es $l$, entonces no se $\binom{l-1}{k-1}$ formas de elegir el resto de $k-1$ enteros.
Por lo tanto,$\displaystyle\sum_{l=k}^{n+k}\binom{l-1}{k-1}=\binom{n+k}{k}$, y dejando $i=l-k$ da $\displaystyle\sum_{i=0}^{n}\binom{i+k-1}{k-1}=\binom{n+k}{k}$.
gar
Puntos
3883
La generación de la función se puede hacer el trabajo con bastante facilidad: \begin{align*} \frac{1}{(1-x)^k} &= \sum_{i\ge 0} \binom{i+k-1}{k-1}\, x^i \end{align*} El uso de la convolución de las funciones de generación, \begin{align*} \frac{1}{(1-x)}\cdot \frac{1}{(1-x)^k} &= \sum_{n\ge 0} \left(\sum_{i=0}^n \binom{i+k-1}{k-1}\right) x^n \\ \frac{1}{(1-x)^{k+1}} &= \sum_{n\ge 0} \binom{n+k}{k} x^n \\ \implies \sum_{i=0}^n \binom{i+k-1}{k-1} &= \binom{n+k}{k} \end{align*}
Incnis Mrsi
Puntos
487
Estoy seguro de que hay algunos astutos argumentos combinatorios. Nunca he sido muy inteligente, así que voy a introducir en $n$.
Un sencillo cálculo muestra que el caso base $n=0$ mantiene.
Ahora, supongamos que inductivamente $$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$$ Entonces \begin{align*} \sum_{i=0}^{n+1}\binom{i+k-1}{k-1} &= \sum_{i=0}^n\binom{i+k-1}{k-1}+\binom{(n+1)+k-1}{k-1} \\ &= \binom{n+k}{k}+\binom{n+k}{k-1} \\ &\overset{\circledast}{=} \binom{(n+1)+k}{k} \end{align*} donde la igualdad marcó $\circledast$ utiliza la fórmula recursiva para los coeficientes binomiales. Esto completa la inducción.
barto
Puntos
6296
Cuántas soluciones hay para $a_1+\cdots+a_k\leq n$ en números enteros no negativos?
Por un lado, este es $$\begin{align*}&\sum_{i=0}^n\#\{(a_1,\ldots,a_k)\mid a_1+\cdots+a_k=i\}\\ =& \sum_{i=0}^n\binom{i+k-1}{k-1}\end{align*}$$
Por otra parte, cada una de las soluciones a $a_1+\cdots+a_k\leq n$ corresponde a una solución única de $a_1+\cdots+a_k+t=n$ mediante el establecimiento $t=n-(a_1+\cdots+a_k)$. Por lo tanto $$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}k.$$
