Find sum $ \sum\limits_{k=2}^{2^{2^n}} \frac{1}{2^{\lfloor \log_2k \rfloor} \cdot 4^{\lfloor \log_2(\log_2k )\rfloor}} $

Question

Calculate sum $$ \sum_{k=2}^{2^{2^n}} \frac{1}{2^{\lfloor \log_2k \rfloor} \cdot 4^{\lfloor \log_2(\log_2k )\rfloor}} $$

I hope to solve this in use of Iverson notation:

my try

$$ \sum_{k=2}^{2^{2^n}} \frac{1}{2^{\lfloor \log_2k \rfloor} \cdot 4^{\lfloor \log_2(\log_2k )\rfloor}} = \sum_{k,l,m}2^{-l}4^{-m} [2^l \le k < 2^{l+1}][2^{2^m} \le k < 2^{2^m+1}] $$

and now: $$ [2^l \le k < 2^{l+1}][2^{2^m} \le k < 2^{2^m+1}] \neq 0 $$ if and only if $$2^l \le k < 2^{l+1} \wedge 2^{2^m} \le k < 2^{2^m+1} $$

I can assume that $l$ is const (we know value of $l$) and treat $m$ as variable depence from $l$. Ok so:
$$2^l \le 2^{2^m} \wedge 2^{2^m+1} \le 2^{l+1} $$ but it gives me that $l=2^m$ I think that it is not true (but also I don't see mistake). Even if it is true, how can be it finished?

Answer 1

Here is an answer following rather closely OP's approach.

We obtain for $n\in\mathbb{Z}, n\geq 0$: \begin{align*} \color{blue}{\sum_{k=2}^{2^{2^n}}}&\color{blue}{\frac{1}{2^{\left\lfloor\log_2 k\right\rfloor}4^{\left\lfloor\log_2\left(\log_2 k\right)\right\rfloor}}}\\ &=\sum_{k=2}^{2^{2^n}}\sum_{l,m}2^{-l}4^{-m}\left[l=\left\lfloor\log_2 k\right\rfloor\right]\left[m=\left\lfloor\log_2\left(\log_2\left(k\right)\right)\right\rfloor\right]\tag{1}\\ &=\sum_{k=2}^{2^{2^n}}\sum_{l,m}2^{-l}4^{-m}\left[l\leq \log_2 k<l+1\right]\left[m\leq\log_2\left(\log_2\left(k\right)\right)<m+1\right]\tag{2}\\ &=\sum_{k=2}^{2^{2^n}}\sum_{l,m}2^{-l}4^{-m}\left[2^l\leq k<2^{l+1}\right]\left[2^{2^m}\leq k<2^{2^{m+1}}\right]\\ &=\sum_{p=0}^{n-1}4^{-p}\sum_{k=2^{2^p}}^{2^{2^{p+1}}-1}\sum_{l}2^{-l}\left[2^l\leq k<2^{l+1}\right]+2^{-2^n}4^{-n}\tag{3}\\ &=\sum_{p=0}^{n-1}4^{-p}\sum_{q=2^p}^{2^{p+1}-1}2^{-q}\sum_{k=2^q}^{2^{q+1}-1}1+2^{-2^n}4^{-n}\tag{4}\\ &=\sum_{p=0}^{n-1}4^{-p}\sum_{q=2^p}^{2^{p+1}-1}2^{-q}2^q+2^{-2^n}4^{-n}\\ &=\sum_{p=0}^{n-1}4^{-p}2^p+2^{-2^n}4^{-n}\\ &=\sum_{p=0}^{n-1}2^{-p}+2^{-2^n}4^{-n}\\ &=\frac{1-\left(\frac{1}{2}\right)^n}{1-\frac{1}{2}}+2^{-2^n}4^{-n}\tag{5}\\ &\,\,\color{blue}{=2-\frac{1}{2^{n-1}}+\frac{1}{2^{2^n}4^n}}\\ \end{align*}

Comment:

• In (1) we use Iverson brackets to get rid of the floor function.

• In (2) we use an equivalent representation of the floor function.

• In (3) we see the intervals inside the Iverson brackets suggest a partioning of the interval $\left[2,2^{2^n}\right]$. We do a first partitioning with respect to $m$ as union of right half-open intervals and add the value for $k=2^{2^n}$. This way we see $m$ takes precisely one value, namely $m=p$.

• In (4) we continue similarly as we did in (3). This way we see $l$ takes precisely one value, namely $l=q$.

• In (5) we use the finite geometric series formula.

Answer 2

Let's write $$\sum_{k=2}^{2^{2^n}} \frac{1}{2^{\lfloor \log_2(k) \rfloor}4^{\lfloor \log_2(\log_2(k))\rfloor}} = \sum_{i=0}^{n-1} \sum_{k=2^{2^i}}^{2^{2^{i+1}}-1} \frac{1}{2^{\lfloor \log_2(k) \rfloor}4^{\lfloor \log_2(\log_2(k))\rfloor}} + \frac{1}{2^{2^n}4^{n}}$$

$$= \sum_{i=0}^{n-1} \sum_{k=2^{2^i}}^{2^{2^{i+1}}-1} \frac{1}{2^{\lfloor \log_2(k) \rfloor}4^{i}} + \frac{1}{2^{2^n}4^{n}}$$

Moreover for all $i=0, ..., n-1$, $$\sum_{k=2^{2^i}}^{2^{2^{i+1}}-1} \frac{1}{2^{\lfloor \log_2(k) \rfloor}} = \sum_{j=2^i}^{2^{i+1}-1} \sum_{k=2^j}^{2^{j+1}-1} \frac{1}{2^{\lfloor \log_2(k) \rfloor}} = \sum_{j=2^i}^{2^{i+1}-1} \sum_{k=2^j}^{2^{j+1}-1} \frac{1}{2^j} = \sum_{j=2^i}^{2^{i+1}-1} \frac{2^j}{2^j} = 2^i $$

You deduce that $$S = \sum_{i=0}^{n-1} \frac{1}{2^i} + \frac{1}{2^{2^n}4^{n}} = 2 - \frac{1}{2^{n-1}} + \frac{1}{2^{2^n}4^{n}}$$