9
$\begingroup$

Does anyone know of a reasonable upper bound for the following: $$\sum_{i = 1}^m \frac{\binom{i}{k}}{2^i},$$ where we $k$ and $m$ are fixed positive integers, and we assume that $\binom{i}{k} = 0$ whenever $k > i$.

One trivial upper bound uses the identity $\binom{i}{k} \le \binom{i}{\frac i2}$, and the fact that $\binom{i}{\frac{i}{2}} \le \frac{2^{i+1}}{\sqrt{i}}$, to give a bound of $$2\sum_{i = 1}^m \frac{1}{\sqrt{i}},$$ where $\sum_{i = 1}^m \frac{1}{\sqrt{i}}$ is upper bounded by $2\sqrt{m}$, resulting in a bound of $4\sqrt{m}$. Can we do better?

Thanks!

Yair

  • 0
    Are you looking for bounds over all $k$ or as a function of $k$?2012-11-29
  • 0
    A general bound would be nice, but probably won't be much better than $O(\sqrt m)$; a function of $k$ would also be quite good.2012-11-29

4 Answers 4

7

Yes you can do better. In fact $$ \sum_{i=k}^m \binom{i}{k} 2^{-i} \leq 2 $$ and this bound is sharp if $k$ is fixed and $m \to \infty$.

To see this, consider the function $x^{k} (1 - x)^{-(k+1)}$ near $0$; this has a power series expansion $$ \frac{x^k}{(1 - x)^{k+1}} = x^k \left( \sum_{\ell \geq 0} x^\ell \right)^{k+1} = \sum_{\ell \geq 0} \binom{k + \ell}{k} x^{\ell + k}, $$ (see here) which, after changing the sum to start at $k$ rather than $0$, is equal to $$ \sum_{i \geq k} \binom{i}{k} x^i. $$ Now you can evaluate this function at $x = \frac12$ which gives $$ 2^{-k} 2^{k+1} = \sum_{i \geq k} \binom{i}{k} 2^{-i}. $$ Your series is a truncation of this sum, and so since each term is positive this gives an upper bound. Sharpness comes from taking $m \to \infty$, of course.

You can improve this bound if you know that $m$ is not much larger than $k$. Here is one estimate in the case when $m = k + O(k/\log k)$. Then, $$ \sum_{i = k}^m \binom{i}{k} 2^{-i} \leq \sum_{i=k}^m i^{i-k} 2^{-i} = \sum_{i=k}^m e^{(i - k) \log i} 2^{-i} $$ This series will be dominated by a geometric series $c^{-i}$ for any $1 < c < 2$ as long as the exponent $(i - k) \log i = O(i)$, where the implied constant depends on $c$. This in turn is satisfied by the requirement $m - k = O(k/\log k)$, (or $k > m - O(\frac{m}{\log(m)}$). Specifically, for any $\varepsilon > 0$ such that $e^\varepsilon < 2$, if $m \le k+ \frac{\varepsilon k}{\log(k)}$ or $k \ge m - \frac{\varepsilon m}{\log m}$, the argument goes through.

Therefore, for any $1 < c < 2$ we have $$ \sum_{i = k}^m \binom{i}{k} 2^{-k} \leq \sum_{i=k}^m c^{-i} = O(c^{-k}) $$ if $m = k + O(k/\log k)$, where the implied constant depends on $c$.

  • 0
    +1: Beautiful! I was about to post the same bound but with a more convoluted argument. Your argument is much nicer.2012-11-29
  • 0
    Joining Mike Spivey's comment here: indeed a great way of using generating functions. Now, a real treat would be that $o(1)$ bound. Thank you so much!2012-11-30
  • 0
    Thank you for the kind words. I've added a rough bound for short sums, where the number of terms is bounded like k/log k. There are no strong ideas here, though, since the exponential term is dominant, and I've made no attempt to keep estimates sharp.2012-12-01
  • 0
    @Yair, I do not understand where you are getting the upper bound of $e^{O(m)} \sum_{i=k}^m 2^{-i}$, as the bound for $\binom{i}{k}$ must depend on $i$ (indeed, that's why that argument only holds for sufficiently short sums). This gives the bound $e^{(i-k) \log i} 2^{-i}$ summed over $i$, which requires that $i - k$ be much smaller than $m$, as the trivial bound by $e^{i \log i} 2^{-i}$ does not work.2012-12-04
  • 0
    Hi Pot, sorry, I mixed up something in my paper, you are right, this result holds. I'll write a slightly more detailed argument and add it to your answer if it's alright with you.2012-12-06
  • 0
    Hi all, thanks a lot for all your comments and help! I would have both Mike Spivey's and Pot's answers as perfectly good answers, but it seems that I can't accept both as answers. I went with Pot's since it has more stuff in it now.2012-12-06
  • 0
    @Yair, Sure, go ahead2012-12-06
2

I like Pot's argument better, but here's another approach for those who may be interested.


I get an upper bound of $2$, independent of $k$ and $m$.

Applying summation by parts, we have, for $k \geq 2$, $$\begin{align*} \sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} &= \binom{m}{k} \sum_{i=1}^m \frac{1}{2^i} - \sum_{i=1}^{m-1} \left(\binom{i+1}{k} - \binom{i}{k}\right) \sum_{j=1}^i \frac{1}{2^j} \\ &= \binom{m}{k} \left(1 - \frac{1}{2^m}\right) - \sum_{i=1}^{m-1} \binom{i}{k-1} \left(1 - \frac{1}{2^i}\right)\\ &= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \sum_{i=1}^{m-1} \binom{i}{k-1} + \sum_{i=1}^{n-1} \binom{i}{k-1} \frac{1}{2^i}\\ &= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \binom{m}{k} + \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}\\ &= \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}- \binom{m}{k}\frac{1}{2^m}, \end{align*}$$ where, in the second-to-last step, we use the upper summation identity for the binomial coefficients, $\displaystyle \sum_{i=0}^m \binom{i}{k} = \binom{m+1}{k+1}$.

Letting $\displaystyle F(m,k) = \sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$, this means we have the recurrence $$F(m,k) = F(m-1,k-1) - \binom{m}{k}\frac{1}{2^m},$$ valid for $k \geq 2$.

Unrolling the recurrence is easy, and with $F(m-k+1,1) = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}},$ we have

$$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}} - \sum_{i=0}^{k-2} \binom{m-i}{k-i} \frac{1}{2^{m-i}}.$$

Therefore, $$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} \leq 2.$$

1

Another estimate for $\sum_{i=1}^m\frac1{\sqrt i}$ is $$2\sqrt{m-1}-2=\int_1^{m-1} x^{-1/2}\, dx \le \sum_{i=1}^m\frac1{\sqrt i}\le1+ \int_1^m x^{-1/2}\, dx=2\sqrt m-1. $$ Thus we can remove the summands with $i by considering $$ 4\sqrt m+2 -4\sqrt{k-2}$$

  • 0
    Thanks! I am looking for something that will be asymptotically better than $\sqrt{m}$, at least for some values of k. For example, if $k = 1$ then the resulting sum is a bounded by a constant.2012-11-29
1

Not an aswer but some simple results that might help. Letting $$S_{m,k} = \sum_{i=k}^m {i \choose k} 2^{-i}$$

then

$$ \sum_{k=0}^m S_{m,k} =m$$

$$ |S_{m,k+1} - S_{m,k} | \le \frac{m}{k}S_{m,k} $$