Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Are you looking for bounds over all $k$ or as a function of $k$? –  leonbloy Nov 29 '12 at 15:19
    
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. –  Yair Zick Nov 29 '12 at 15:21

4 Answers 4

up vote 7 down vote accepted

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

share|improve this answer
    
+1: Beautiful! I was about to post the same bound but with a more convoluted argument. Your argument is much nicer. –  Mike Spivey Nov 29 '12 at 17:34
    
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! –  Yair Zick Nov 30 '12 at 2:40
    
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. –  Pot Dec 1 '12 at 10:17
    
@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. –  Pot Dec 4 '12 at 19:55
    
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. –  Yair Zick Dec 6 '12 at 4:15

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

share|improve this answer

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

share|improve this answer

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<k$ by considering $$ 4\sqrt m+2 -4\sqrt{k-2}$$

share|improve this answer
    
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. –  Yair Zick Nov 29 '12 at 14:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.