Double sum, find upper bound

Question

I have a double sum $$\sum_{i=1}^{\log(n)} \sum_{j=\log(n) - i}^{\log(n)} \left(\frac{1}{2}\right)^i$$ And I'd like to show it's $\mathcal{O}(1)$ i.e. there is a constant $c$ that is an upper bound of that sum. With the help of Wolfram|Alpha I learnt that the compact, equivalent form is $$2^{-\log(n)} (-3+3 \cdot 2^{\log(n)}-\log(n))$$ hence I can safely put $c=3$. However, I'm more interested in finding potentially larger constant $c$ but using as simple tools and having as little transformations/inequalities on the way, as it is possible (so, something that can be derived on paper in one minute for instance ; )).

Answer 1

Differentiating $$ \sum_{i=1}^\infty x^{i+1} =-1-x+\frac1{1-x} $$ we get $$ \sum_{i=1}^\infty(i+1)x^i=-1+\frac1{(1-x)^2} $$ Plug in $x=\frac12$ to get $$ \begin{align} \sum_{i=1}^{\log(n)}\overbrace{\sum_{j=\log(n)-i}^{\log(n)}}^{\le i+1\text{ terms}}\left(\frac12\right)^i &\le\sum_{i=1}^\infty(i+1)\left(\frac12\right)^i\\ &=3 \end{align} $$

Answer 2

The sum of infinite geometric series with ratio $r<1$ is the initial term divided by $1-r$. So, the sum (finite or infinite) of integer powers of $\frac12$ is at most twice the largest term of the sum. This is all you need to estimate the sum here.

The sum is more symmetric if you allow $i=0$ in it. Then the summation is taken over all pairs $(i,j)$ such that $i+j\ge \log n$ and $0\le i,j\ \le \log n$. Change the order of summation: $$ \sum_{i=0}^{\log(n)} \sum_{j=\log(n) - i}^{\log(n)} \left(\frac{1}{2}\right)^i = \sum_{j=0}^{\log(n)} \sum_{i=\log(n) - j}^{\log n} \left(\frac{1}{2}\right)^i \tag{1}$$ Then use the estimate from the first paragraph to estimate (1) by $$ \sum_{j=0}^{\log(n)} 2 \left(\frac{1}{2}\right)^{\log(n) - j}\le 2 \cdot 2 \cdot 1 =4 $$