The bound for $$\sum_{i=1}^n\binom{n}{i}2^i$$ is $O\left(3^n\right)$ but what will be the bound for $$\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$$ Any idea how should I proceed?
Asked
Active
Viewed 305 times
2
-
1It should be clear that $3^n$ is still an upper bound, so to say the second sum is $O(3^n)$ is correct, the real question is for a bound that is both an upper and lower bound. – DanielV Jul 23 '16 at 17:03
-
What you are asking is "what is the asymptotic bound of a partial binomial expansion", if that helps your research. – DanielV Jul 24 '16 at 07:00
-
@DanielV yes I need bound for partial binomial expansion. Specially, I need the binomial expansion bound from 1 to central. Thank you. One bound i found as $2.82^ n$ by multiplying all elements with $2^{n/2}$, but i seems it is not a tight bound. – NARAYAN CHANGDER Jul 24 '16 at 10:08
-
1This link may help you: http://math.stackexchange.com/questions/84746/bounds-on-sum-k-0m-binomnkxk-and-sum-k-0m-binomnkxk1. Use the symmetry of the summation coefficients to find the sum of negative powers, and try applying the last formula on the page. – meowgoesthedog Jul 28 '16 at 12:26
-
I do not see how you can get a bound of $2.82^n$. – user21820 Jul 31 '16 at 11:23
1 Answers
1
$\def\pp{\mathbb{P}}$$\Large\frac{1}{3^{2m}} \sum_{k=1}^m \binom{2m}{k}\ 2^k = \sum_{k=1}^m \binom{2m}{k}\ (\frac23)^k (\frac13)^{2m-k}$
$\large\ = \pp\Big(Bin(2m,\frac23) \in [1,m] \Big) < \exp(-\frac{m}{9})$ [by the tail bound via Hoeffding's inequality]
Numerically, this is far from asymptotically tight, but at least it shows that $\large\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i \in o(3^n)$.
user21820
- 57,693
- 9
- 98
- 256