# is there a formula for this binomial sum?

Are there any formulas to calculate the below sum?

$$\sum_{n=1}^{1918}n\binom{2017-n}{99}$$

Or, more generally,

$$\sum_{n=1}^{1918}n\binom{2017-n}{k}$$

• Is $n$ the index of the sum? – Frpzzd Jul 28 '17 at 13:34
• @Nilknarf yes it is – math lover Jul 28 '17 at 13:43
• Hint: Roughly speaking, $n$ is the position of the second person when selecting 100 people. That's not quite right, in case this is an assignment question. – Michael Jul 28 '17 at 13:56
• the question state that A={1,2...2017} and r(x) is the least element in a sub list of A with 100 elements. find the mean of all sub lists minimum value – math lover Jul 28 '17 at 14:02
• for your first question wolframalpha.com/input/?i=sum+n((p-n)+choose+m)+n%3D1+to+p-m – serg_1 Jul 28 '17 at 14:41

A general solution where $p = 2017$ and $k = 99$ in your case:

First rewrite the sum to look nicer: \begin{align*} \sum_{n=0}^{p-k}n\binom{p-n}k &= \sum_{n=k}^p(p-n)\binom{n}k = p\sum_{n=k}^p\binom{n}k - \sum_{n=k}^p n\binom{n}k \\ &= p\sum_{n=0}^{p-k}\binom{n+k}k - \sum_{n=0}^{p-k}(n+k)\binom{n+k}k \\ &= (p-k)\sum_{n=0}^{p-k}\binom{n+k}k - \sum_{n=0}^{p-k}n\binom{n+k}k \end{align*}

Now the nice thing about this is that this looks like a well known generating function! We have that $$\frac1{(1-x)^{k+1}} = \sum_{n\geq0}\binom{n+k}kx^n.$$ To find the generating function for $n\binom{n+k}k$, we can differentiate both sides and multiply by $x$. $$\frac{(k+1)x}{(1-x)^{k+2}} = \sum_{n\geq0}n\binom{n+k}kx^{n-1}\cdot x = \sum_{n\geq0}n\binom{n+k}k x^n$$ But this is only the generating function for each of the terms, not the sum up to something. The trick for getting the generating function for the first $n$ terms of a sequence from the original generating function $A(x)$ is shifting the terms and adding them up: $$A(x) + xA(x) + x^2A(x) + \dots = A(x)\left(1+x+x^2+\dots\right) = \frac{A(x)}{1-x}.$$ So, the answer you want is the $(p-k)$th coefficient of the generating function $$\frac{p-k}{(1-x)^{k+2}} - \frac{(k+1)x}{(1-x)^{k+3}}.$$ The $n$th coefficient of the first term is $(p-k)\binom{n+k+1}{k+1}$ from before, and the $n$th coefficient of the second term is the $n-1$th coefficient of $\frac{(k+1)}{(1-x)^{k+3}}$, which is $(k+1)\binom{n+k+1}{k+2}$. So, we conclude that the answer is \begin{align*} (p-k)\binom{p+1}{k+1}-(k+1)\binom{p+1}{k+2} &= (p-k)\frac{k+2}{(p+1)-(k+1)}\binom{p+1}{k+2}-(k+1)\binom{p+1}{k+2} \\ &= ((k+2)-(k+1))\binom{p+1}{k+2} \\ &= \boxed{\binom{p+1}{k+2}.} \end{align*}

\begin{align} \sum_{n=1}^{1918}\binom n1\binom {2017-n}{99} &=\sum_{n=1}^{1918}\binom n{n-1}\binom {2017-n}{1918-n}\\ &=\sum_{n=1}^{1918}(-1)^{n-1}\binom {-2}{n-1}(-1)^{1918-n}\binom {-100}{1918-n} &&(*)\\ &=-\sum_{n=1}^{1918}\binom {-2}{n-1}\binom {-100}{1918-n}\\ &=-\binom {-102}{1917} &&(**)\\ &=-(-1)^{1917}\binom {2018}{1917} &&(*)\\ &=\color{red}{\binom {2018}{1917}=\binom {2018}{101}} \end{align}

Wolframalpha check here.

(*) using Upper Negation
(**) using the Vandermonde Identity

The general case is $$\sum_{n=1}^k \binom nm\binom {y-n}{y-k}=\binom {y+1}{y-k+m+1}=\binom {y+1}{k-m}$$ A simple way might be to think of it as an upside-down Vandermonde identity where the summation index appears in $+$ve and $-$ve form at the top instead of the bottom, and the result is to add across the non-index constants, and add $1$ to the top and bottom numbers after doing that.

• Wow so much simpler than my solution... – Taisuke Yasuda Jul 28 '17 at 15:15
• @TaisukeYasuda - Thank you :) Your solution is pretty interesting too! – hypergeometric Jul 28 '17 at 15:19