Pebrudal's logarithmic sum

Observe that for $n=2^k$ to $(2^{k+1}-1)$ (i.e., for $(2^{k+1}-2^k)$ number of terms), $\lfloor{\log_2 n}\rfloor = k$ for some positive integer $k$ . [This is a trivial observation]

(Note that $\lfloor{\log_2 (2^{200}-1)}\rfloor = 199$ )

So we may transform the summation as

$\displaystyle\sum_{k=2}^{199} k*(2^{k+1}-2^k)$

$= 2(2^3-2^2) + 3(2^4-2^3) + 4(2^5-2^4) + ... + 199(2^{200} - 2^{199})$

$= 199\cdot2^{200} - 2^2 - (2^2 + 2^3 + 2^4 + ... + 2^{199})$

$= 199\cdot2^{200}-2^2 - (2^{200} - 2^2)= 198\cdot2^{200} = 99\cdot2^{201}$ .

So $a + b$ is 300 .

First, we note that $\lfloor \log_k(n) \rfloor = x$ where $x$ is the largest integer power of $k$ that is less than $n$ . This is because $k^x < n < k^{x+1} \to$ $x < \log_k(n) < x+1 \to \lfloor \log_k(n) \rfloor = x$ .

$\\$

We split our desired sum in the following way: $\displaystyle \sum_{n=2^2}^{2^3-1} \lfloor \log_2(n) \rfloor + \sum_{n=2^3}^{2^4-1} \lfloor \log_2(n) \rfloor + ... + \sum_{n=2^{199}}^{2^{200}-1} \lfloor \log_2(n) \rfloor$ . In the $k$ th sum in this expression (beginning with $k=2$ ), there are $2^k$ values being summed, and each of these values is $k$ , as we showed above, and so our desired sum is $\displaystyle \sum_{k=2}^{199} k \cdot 2^k$ .

The first few partial sums are $8 = (2-1) \cdot 2^{2+1}, 32 = (3-1) \cdot 2^{3+1}, 96 = (4-1) \cdot 2^{4+1}, ...$ , which suggests that the $k$ th partial sum is $(k-1) \cdot 2^{k+1}$ . We can prove this using induction.

We already have the base case, so we assume it's true for $k = j$ and then show it's true for $k = j + 1$ :

$\displaystyle \sum_{n=2}^{j+1} n \cdot 2^n =$ $\displaystyle \sum_{n=2}^j n \cdot 2^n + (j+1) \cdot 2^{j+1} =$

$\displaystyle (j-1) \cdot 2^{j+1} + (j+1) \cdot 2^{j+1} =$ $\displaystyle (2 \cdot j) \cdot 2^{j+1} =$

$\displaystyle ((j+1)-1) \cdot 2^{(j+1)+1}$

QED .

Thus, our desired sum is $(199 - 1) \cdot 2^{199 + 1} = 99 \cdot 2^{201}$ , and so the answer is $99 + 201 = \fbox{300}$ .

$\displaystyle \sum_{n=4}^{2^{200} - 1} ⌊\log_2 n⌋$

$= 2 + 2 + \ldots + 2 + 3 + 3 + \ldots + 3 + \ldots + 199 + 199 + \ldots + 199$

$= 2 \times 2^2 + 3 \times 2^3 + 4 \times 2^4 + \ldots + 199 \times 2^{199}$

$= \displaystyle \sum_{k=2}^{199} k2^k$

Since $\displaystyle \sum_{i=0}^{n-1} ia^i = \frac{a - na^n + (n-1)a^{n+1}}{(1 - a)^2}$ then $\displaystyle \sum_{k=2}^{n-1} k2^k = (k-2)2^k$

Hence,

$\displaystyle \sum_{k=2}^{199} k2^k = (200 - 2) \times 2^{200} = 99 \times 2^{201}$

$a = 99, b = 201, a + b = 300$

$\displaystyle \sum_{n = 4}^{2^{200} - 1} \lfloor{log_{2}n} \rfloor$

= $\displaystyle \sum_{n = 2^2}^{2^3 - 1}2 + \sum_{n = 2^3}^{2^4 - 1}3 +\sum_{n = 2^4}^{2^5 - 1}4 + \dots + \sum_{n = 2^{198}}^{2^{199} - 1}198 + \sum_{n = 2^{199}}^{2^{200} - 1} 199$

= $2*2^2 + 3*2^3 + 4*2^4 + \dots + 198*2^{198} + 199*2^{199}$

Now, this is a simple Arithmetico - Geometrico Sequence , whose sum comes out to be $198*2^{200} = 99*2^{201}$ . Hence, $a + b = \fbox{300}$

$\lfloor log_{2}n\rfloor$ = k, for n $\in$ { $2^k,2^k+1,...,2^{k+1}-1$ }

This set contain $2^k$ elements.

Then, the sum $S=\sum_{n=4}^{2^{200}-1}\lfloor log_{2}n\rfloor$ = $\sum_{k=2}^{199} k \times 2^k$

S = $2\sum_{k=2}^{199} k \times 2^{k-1}$

$S = \lim_{a \rightarrow 2} 2\sum_{k=2}^{199} k \times a^{k-1}$

$S = \lim_{a \rightarrow 2} 2\sum_{k=2}^{199} \frac{d(a^k)}{da}$

$S = \lim_{a \rightarrow 2} \frac{d}{da}(2\sum_{k=2}^{199} k \times a^k)$

$S = \lim_{a \rightarrow 2} \frac{d}{da}2\frac{a^{200}-a^2}{a-1}$

$S = 99 \times 2^{201}$

Therefore, $a=99$ and $b=201$ $\rightarrow a+b=300$ .