I am trying to get a tight upper bound for this formula : $$\sum\limits_{i=0}^{k} 2^i \sum\limits_{j=0}^{i} {{\frac{n}{2^i}}\choose{j}}$$

We can get a rough upper bound easily with the following :

  • by setting $i=k$ and multiplying $k$ times the expression inside the first sum to get rid of it : $$\sum\limits_{i=0}^{k} 2^i \sum\limits_{j=0}^{i} {{\frac{n}{2^i}}\choose{j}} \leq k.2^k \sum\limits_{j=0}^{k} {{\frac{n}{2^k}}\choose{j}}$$
  • by using the known upper bound $\sum\limits_{i=0}^{k} {{n}\choose{i}} \leq (n+1)^k$ for bounding the second sum : $$\sum\limits_{i=0}^{k} 2^i \sum\limits_{j=0}^{i} {{\frac{n}{2^i}}\choose{j}} \leq k.2^k.(\frac{n}{2^k} + 1)^k$$

But this is a rough upper bound.

Is it possible to get a tighter upper bound ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.