# Double sum with parameter at exponent and binomial coefficient partial sum

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 ?