From $ \sum^\infty_{\lfloor \log n \rfloor + 1}n/{2^r} $ to $ \sum^\infty_{r=0}1/2^r $?

Question

$$ E[h] = E[\sum^\infty_{r=1}I_r] = \sum^\infty_{r=1}E[I_r] $$

$$ = \sum^{ \lfloor \log n \rfloor}_{r=1}E[I_r] + \sum^\infty_{\lfloor \log n \rfloor + 1}E[I_r] $$

$$ \leq \sum^{ \lfloor \log n \rfloor}_{r=1}1 + \sum^\infty_{\lfloor \log n \rfloor + 1}n/{2^r} $$

$$ \leq \log n + \sum^\infty_{r=0}1/2^r $$

$$ = \log n + 2 $$

I'm trying to understand how you go from $ \sum^\infty_{\lfloor \log n \rfloor + 1}n/{2^r} $ to $ \sum^\infty_{r=0}1/2^r $

Answer 1

Assuming $\log$ here means the base-$2$ logarithm (since the inequality doesn't generally hold if the base is larger), we have

$$n < 2^{\lfloor \log n\rfloor+1},$$

and therefore

$$\sum_{r=\lfloor \log n\rfloor+1}^\infty \frac{n}{2^r} < \sum_{r=\lfloor \log n\rfloor+1}^\infty \frac{2^{\lfloor \log n\rfloor+1}}{2^r} = \sum_{r=\lfloor \log n\rfloor+1}^\infty \frac{1}{2^{r-(\lfloor\log n\rfloor+1)}} = \sum_{k=0}^\infty \frac{1}{2^k}.$$