# Weighted sum of product of binomial coefficients

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, then $$\displaystyle \binom{N-n}{k}=0$$.

• Maybe reverse the summation? – Lord Shark the Unknown Nov 29 '18 at 5:52
• I tried it. Ran into a dead end. – 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.