1
$\begingroup$

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.

  • 0
    What is k choose i if k is not integral? Otherwise, why the ceiling function? EDIT -- looks like it's fixed.2010-10-29
  • 0
    *Very* related: http://math.stackexchange.com/questions/77572010-10-29
  • 0
    @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.2010-10-29
  • 0
    I found this question: http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n2010-10-29
  • 0
    You can factor out the $i$ like this: $i\cdot\sum_{i=0}^{\lceil \frac{k}{2} \rceil}{{k \choose i}}$2010-10-29
  • 2
    @muntoo: No you cannot. Definitely not.2010-10-29
  • 0
    I believe I've found a way to construct the generating function for this. I'm hoping I can get the information from this... It will take some time to make sure it is correct. I use three generating functions to exchange information to get the factorial term. Two contain all terms (on one side) except for possibly the middle. The third is Pascal's triangle; I subtract both sides to see if there is a middle term to add. I then use the terms on one side to construct functions that successively add terms closer to the middle. Summing this should give the correct GF for the original problem.2010-10-29
  • 0
    @J.M. Oh, woops! You're absolutely right.2010-10-29

1 Answers 1

3

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

  • 0
    Very simple! Excellent!2010-10-29