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$ – Lord Shark the Unknown Nov 29 '18 at 5:52
  • 1
    $\begingroup$ I tried it. Ran into a dead end. $\endgroup$ – marty cohen Nov 29 '18 at 6:53

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.


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.