Unable to prove inequality using induction or understand intuitively

Question

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.

Answer 1

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.