# What is the sum of half of the choices (weighted)?

I'd like to get the exact value of the following sum:

$\sum_{i=0}^{\lceil \frac{k}{2} \rceil}{({k \choose i}\cdot i)}$

I'd also like to know the asymptotic limits of the function.

-
What is k choose i if k is not integral? Otherwise, why the ceiling function? EDIT -- looks like it's fixed. – gatoatigrado Oct 29 '10 at 1:20
Very related: math.stackexchange.com/questions/7757 – J. M. Oct 29 '10 at 1:24
@gatoatigrado: Sorry, I'm not the best LaTeXter yet. @J.M.: I'm hoping that the asymptotics are different. It would mean that I have a noteworthy algorithm for a multiplication problem. – Matt Groff Oct 29 '10 at 1:58
I found this question: mathoverflow.net/questions/17202/… – Matt Groff Oct 29 '10 at 3:23
@muntoo: No you cannot. Definitely not. – J. M. Oct 29 '10 at 3:39

Use $\binom{k}{i} i = k \binom{k-1}{i-1}$ to get

$\sum_{i=0}^{\lceil k/2 \rceil} \binom{k}{i} = k\sum_{j=0}^{\lceil k/2 \rceil - 1} \binom{k-1}{j}$

If $k = 2m$ is even then

$k\sum_{j=0}^{m-1} \binom{2m-1}{j} = k 2^{2m-2} = k2^{k-2}$

If $k = 2m+1$ is odd then

$k\sum_{j=0}^m \binom{2m}{j} = k \left(2^{2m-1} +\frac{1}{2} \binom{2m}{m}\right) = k\left(2^{k-2} + \frac{1}{2} \binom{k-1}{(k-1)/2}\right)$

For the asymptotics, $\frac{k}{2} \binom{k-1}{(k-1)/2} \approx 2^{k-1} \sqrt{\frac{k}{2\pi}}$.

-
Very simple! Excellent! – Matt Groff Oct 29 '10 at 5:08