Delimitación de una suma de coeficientes binomiales

Question

Me gustaría vinculado a la suma $$ \phi(n,k) = {n \choose k} + 2 {n-1 \choose k} + 3 {n-2 \choose k} + \cdots + (n-k+1) {k \choose k} $$ Estoy tratando de conseguir una manija en lo grande, esta suma. Específicamente, ¿cómo es de grande como una función de $k$ al $n=k^{1.5}$? ¿Qué acerca de la $n=k^2$? Necesito obtener este tipo de estimaciones, y me pregunto si uno puede sugerir los mejores métodos para ello.

Answer 1

$$S~=~\sum_{j=k}^n{j\choose k}(n-j+1)~=~\sum_{i=0}^{n-k}{k+i\choose k}\Big[(n-k+1)-i\Big]~=~(n-k+1)~S_0-S_1,$$

donde$~S_a~=~\displaystyle\sum_{i=0}^{n-k}{k+i\choose k}~i^a.\quad$, al mismo tiempo, $~\displaystyle{k+i\choose k}={k+i\choose i}=(-1)^i~{-k-1\choose i},$

y $~\displaystyle{a\choose i}~i~=~{a-1\choose i-1}~a.\quad$ a Continuación, dejando $a=-(k+1),~$ y el uso de la conocida identidad

$\displaystyle\sum_{i=0}^m(-1)^i{p\choose i}~=~(-1)^m{p-1\choose m},\quad$ $($finalmente,$)$ llegan a $~S=\displaystyle{n+2\choose k+2}.\quad$ QED.

Answer 2

$$\begin{align} \phi(n,k)&=\sum_{j=k}^n\binom jk\binom {n+1-j}1\\ &=\sum_{j=k}^n \binom j{j-k}\binom {n+1-j}{n-j}\\ &=\sum_{j=k}^n (-1)^{j-k}\binom {-k-1}{j-k}(-1)^{n-j}\binom{-2}{n-j}&&\text{(Upper Negation)}\\ &=(-1)^{n-k}\sum_{j=k}^n \binom {-k-1}{j-k}\binom{-2}{n-j}\\ &=(-1)^{n-k}\binom {-k-3}{n-k}&&\text{(Vandermonde)}\\ &=(-1)^{2(n-k)}\binom {n+2}{n-2}&&\text{(Upper Negation)}\\ &=\binom {n+2}{k+2}\quad\blacksquare \end{align}$$

Answer 3

De dicha suma, puede ser simplificado a $\frac{(n+1)(n+2)\binom{n}{k}}{(k+1)(k+2)}$

Lo siento, no tuve la oportunidad de proporcionar la explicación anterior.

Tenga en cuenta que estamos obligados a evaluar la siguiente suma: $$\sum_{t=0}^{n-k} (t+1) \binom{n-t}{k} = \sum_{t=0}^{n} \binom{t+1}{1} \binom{n-t}{k}$$

En la anterior suma, todos los términos correspondientes a $t =n-k$ $t=n$son cero.

Ahora considere la siguiente identidad:

$$\sum_{k = 0}^l \binom{l-k}{m} \binom{q+k}{n} = \binom{l+q+1}{m+n+1}$$ where $l, m, n, p \geq 0$

Vamos a usar los de arriba identidad: plug-in en la $(k,l,m,n,q) \leftarrow (t,n,k,1,1)$

Por lo tanto la respuesta es $$\binom{n+2}{k+2} = \frac{(n+1)(n+2)\binom{n}{k}}{(k+1)(k+2)}$$