Como encontrar $ \binom {1}{k} + \binom {2}{k} + \binom{3}{k} + ... + \binom{n}{k} $

Question

Buscar $$ \binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k} $$ if $0 \le k \le n$

¿Cualquier método para solucionar este problema? Yo he no conseguido nada hasta ahora. ¡Gracias de antemano!

Answer 1

Para $k=0$, la respuesta es $n$.

Para $k>0$, la respuesta es ${{n+1}\choose{k+1}}$.

Esto puede ser visto por considerar cuántas maneras hay para elegir $k+1$ enteros del conjunto $\{1,2,\dots,n+1\}$ y acondicionado en el mayor entero elegido, porque no tiene que ser $k$ opciones a menos de la mayor entero elegido.

Por ejemplo, nos fijamos en ${{n+1}\choose{k+1}}={6\choose 4}$. Para elegir $4$ elementos de $\{1,2,3,4,5,6\}$, el mayor elemento seleccionado podría ser $4$, y entonces tendríamos que elegir a $3$ elementos de $\{1,2,3\}$; o el mayor elemento seleccionado podría ser $5$, y entonces tendríamos que elegir a $3$ elementos de $\{1,2,3,4\}$; o el mayor elemento seleccionado podría ser $6$, y entonces tendríamos que elegir a $3$ elementos de $\{1,2,3,4,5\}$.

Así que en total, ${6\choose 4}={3\choose 3}+{4\choose 3}+{5\choose 3}$.

Nota: los demás términos de la suma, de la forma${i\choose k}$$i<k$, son todos los $0$.

Answer 2

Polynom $P(x)=a_mx^m +\dots +a_1x+a_0$ denotan $[x^k]P(x)=a_k$.

Tenga en cuenta que para el $k\le i \le n$ % $ $$\dbinom{i}{k}=[x^k](1+x)^i$por lo tanto \begin{align} \sum_{i=1}^n\dbinom{i}{k}&=\sum_{i=k}^n\dbinom{i}{k}\\ &=\sum_{i=1}^n[x^k](1+x)^i\\ &=[x^k]\sum_{i=k}^n(1+x)^i\\ &=[x^k]\frac{(1+x)^{n+1}-(1+x)^k}{(1+x)-1}\\ &=[x^k]\frac{(1+x)^{n+1}-(1+x)^k}{x}\\ &=[x^{k+1}]\left((1+x)^{n+1}-(1+x)^k\right)\\ &=[x^{k+1}](1+x)^{n+1}+[x^{k+1}](1+x)^{k}\\ &=\dbinom{n+1}{k+1}+0\\ &=\dbinom{n+1}{k+1} \end {Alinee el}

Answer 3

Ninguna respuesta formal, pero una buena ilustración:
La solución puede exemplarically se muestra por medio de una matriz de multiplicación de esquema. La siguiente muestra $S \cdot P = X$ donde $X$ es simplemente un cambio de $P$ .
La izquierda-inferior es la matriz de $S$ que realiza el parcial sumatorias de las columnas de la matriz $P$, que está en la parte superior derecha de la matriz, y el resultado $X$ es la inferior derecha de la matriz: $$ \pequeño \begin{matrix} . & . & . & . & . & | & 1 & . & . & . & . & | \\ . & . & . & . & . & | & 1 & 1 & . & . & . & | \\ . & . & . & . & . & | & 1 & 2 & 1 & . & . & | \\ . & . & . & . & . & | & 1 & 3 & 3 & 1 & . & | \\ . & . & . & . & . & | & 1 & 4 & 6 & 4 & 1 & | \\ - & - & - & - & - & + & - & - & - & - & - & + \\ 1 & . & . & . & . & | & 1 & . & . & . & . & | \\ 1 & 1 & . & . & . & | & 2 & 1 & . & . & . & | \\ 1 & 1 & 1 & . & . & | & 3 & 3 & 1 & . & . & | \\ 1 & 1 & 1 & 1 & . & | & 4 & 6 & 4 & 1 & . & | \\ 1 & 1 & 1 & 1 & 1 & | & 5 & 10 & 10 & 5 & 1 & | \\ - & - & - & - & - & + & - & - & - & - & - & + \end{de la matriz} $$

A partir de este hipotético resultado puede fácilmente ser formulado y le da la dirección de la tentativa de una prueba...

Answer 4

Se puede demostrar por inducción que

$$\binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k}=\frac{(k-1)\binom{1}{k}+(n-k+1)\binom{n+1}{k}}{k+1}$$

sostiene para cada valor del $k$.

Answer 5

La solución automática: usando el algoritmo de Gosper maxima:AntiDifference(binomial(i,k),i);

$$\binom{i}{k}=\frac{\binom{i}{k}\,\left(k-i\right)}{k+1}-\frac{\binom{i+1}{k}\,\left(k-(i+1)\right)}{k+1}$ $ y los telescopios de la suma.