# Unable to prove inequality using induction or understand intuitively

While evaluating the complexity of an algorithm, I got an inequality that I am unable to understand.

Let us consider this series:

$$x= n + (2^0 + 2^1 + 2^2 + ....... + 2^{\lfloor\log(n-1)\rfloor})$$

How do I prove that $x\leq 3n$ ?

Please help me understand this intuitively or otherwise.

-

## 1 Answer

The key is the identity $$\sum_{i=0}^{m}2^{i} = 2^{m+1}-1$$

Then just plugging in $m=\lfloor\log(n-1)\rfloor$ we get $$x = n + (2^{\lfloor\log(n-1)\rfloor+1}-1)$$ It should be obvious from there.

-