I am trying to evaluate the sum

$\displaystyle \sum_{n=1}^N \sum_{k=1}^n k\binom{n}{k} \binom{N-n}{k}x^k$,

Here $x$ is some positive real

My approach so far has been to first to compute the summation $\displaystyle \sum_{k=1}^n \binom{n}{k} \binom{N-n}{k}x^k$ , then on differentiating with respect to x, we can find the inner summation in my original expression.

I am however not able to find a clean expression for this, though it looks quite structures. I was able to use the Vandermonde inequality to show that $\displaystyle \sum_{k=1}^n \binom{n}{k} \binom{N-n}{k} = \binom{N}{n}$, but was not able to get the $x^k$ into the summation.

Another approach I tried was to consider the constant term (in $x$) in $\displaystyle (1+x)^n\bigg(1+\frac{\alpha}{x}\bigg)^{N-n}$ , but was unable to obtain anything from this line.

Any ideas on how to proceed?

Edit: If $k<N-n$, then $\displaystyle \binom{N-n}{k}=0$.

  • 2
    $\begingroup$ Maybe reverse the summation? $\endgroup$ Nov 29, 2018 at 5:52
  • 1
    $\begingroup$ I tried it. Ran into a dead end. $\endgroup$ Nov 29, 2018 at 6:53

2 Answers 2


Hoping that you enjoy hypergeometric functions.

$$f_n=\sum_{k=1}^n k\,\binom{n}{k}\, \binom{N-n}{k}\,x^k=n x (N-n) \, _2F_1(1-n,n-N+1;2;x)$$ where appears the Gaussian or ordinary hypergeometric function. This was "simple".

Now, being stuck, using a CAS for a few values of $N$ (since the CAS also was stuck for the general case), it seems that there are two patterns depending on the parity of $N$ $$\left( \begin{array}{cc} N & \sum_{n=1}^N f_n \\ 2 & x \\ 4 & 2 x^2+10 x \\ 6 & 3 x^3+42 x^2+35 x \\ 8 & 4 x^4+108 x^3+252 x^2+84 x \\ 10 & 5 x^5+220 x^4+990 x^3+924 x^2+165 x \\ 12 & 6 x^6+390 x^5+2860 x^4+5148 x^3+2574 x^2+286 x \\ 14 & 7 x^7+630 x^6+6825 x^5+20020 x^4+19305 x^3+6006 x^2+455 x \\ 16 & 8 x^8+952 x^7+14280 x^6+61880 x^5+97240 x^4+58344 x^3+12376 x^2+680 x \end{array} \right)$$

$$\left( \begin{array}{cc} 3 & 4 x \\ 5 & 12 x^2+20 x \\ 7 & 24 x^3+112 x^2+56 x \\ 9 & 40 x^4+360 x^3+504 x^2+120 x \\ 11 & 60 x^5+880 x^4+2376 x^3+1584 x^2+220 x \\ 13 & 84 x^6+1820 x^5+8008 x^4+10296 x^3+4004 x^2+364 x \\ 15 & 112 x^7+3360 x^6+21840 x^5+45760 x^4+34320 x^3+8736 x^2+560 x \\ 17 & 144 x^8+5712 x^7+51408 x^6+159120 x^5+194480 x^4+95472 x^3+17136 x^2+816 x \end{array} \right)$$ and the coefficients seem to be corresponding to "simple" polynomials in $N$ (some of the sequences were found in $OEIS$).


I'll try Sharky's suggestion.

$\begin{array}\\ s( N) &=\sum_{n=1}^N \sum_{k=1}^n k\binom{n}{k} \binom{N-n}{k}x^k\\ &=\sum_{k=1}^N \sum_{n=k}^N k\binom{n}{k} \binom{N-n}{k}x^k\\ &=\sum_{k=1}^N kx^k\sum_{n=k}^N \binom{n}{k} \binom{N-n}{k}\\ &=\sum_{k=1}^N kx^k\sum_{n=k}^N \dfrac{n!(N-n)!}{k!(n-k)!k!(N-n-k)!}\\ &=\sum_{k=1}^N \dfrac{kx^k}{k!^2}\sum_{n=k}^N \dfrac{n!(N-n)!}{(n-k)!(N-n-k)!}\\ &=\sum_{k=1}^N \dfrac{kx^k}{k!^2}\sum_{n=0}^{N-k} \dfrac{(n+k)!(N-n-k)!}{(n)!(N-n-2k)!}\\ \end{array} $

And I don't see where to go from here.

So I'll leave this in the hope that someone else might find it useful.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .