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