0
$\begingroup$

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}$$

$\endgroup$
  • 2
    $\begingroup$ Is $n$ the index of the sum? $\endgroup$ – Frpzzd Jul 28 '17 at 13:34
  • $\begingroup$ @Nilknarf yes it is $\endgroup$ – math lover Jul 28 '17 at 13:43
  • $\begingroup$ 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. $\endgroup$ – Michael Jul 28 '17 at 13:56
  • $\begingroup$ 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 $\endgroup$ – math lover Jul 28 '17 at 14:02
  • $\begingroup$ for your first question wolframalpha.com/input/?i=sum+n((p-n)+choose+m)+n%3D1+to+p-m $\endgroup$ – serg_1 Jul 28 '17 at 14:41
5
$\begingroup$

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*}

$\endgroup$
5
$\begingroup$

$$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.