How to prove $n = \sum_{k=0}^{\lfloor \log_2{n} \rfloor}{\left[ \left\lfloor \frac{n}{2^{k+2}} \right\rfloor + c_k \right](k+1)}$

Question

I would like to prove that:

$$n = \sum_{k=0}^{\lfloor \log_2{n} \rfloor}{\left[ \left\lfloor \frac{n}{2^{k+2}} \right\rfloor + \left(\left\lfloor \frac{n}{2^{k}} \right\rfloor \bmod 2 \right) \right](k+1)} \tag{1}\label{eq1}$$

for every natural number $n$. I have tested it numerically up to $n = 10000$.

Note that:

$$c_k = \left\lfloor \frac{n}{2^{k}} \right\rfloor \bmod 2, \quad k = 0 \ldots \lfloor \log_2{n} \rfloor$$

are the coefficients of the binary expansion of $n$.

Background

Starting from this formula, valid for every natural number $n$:

$$n=1+\sum_{j=1}^{n}{\left\lfloor{\log_2\frac{2n-1}{2j-1}}\right\rfloor} \tag{2}\label{eq2}$$

which is explained and proved here, it is possible to group together all $\left\lfloor{\log_2\frac{2n-1}{2j-1}}\right\rfloor$ terms such that:

$$\left\lfloor{\log_2\frac{2n-1}{2j-1}}\right\rfloor = k$$

for which we have:

$$2^k \le \frac{2n-1}{2j-1} \lt 2^{k+1}$$

$$\frac{2n-1}{2^{k+1}} \lt 2j-1 \le \frac{2n-1}{2^k}$$ $$\frac{2n-1+2^{k+1}}{2^{k+2}} \lt j \le \frac{2n-1+2^k}{2^{k+1}}$$ $$\left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor + 1 \le j \le \left\lfloor\frac{2n-1+2^k}{2^{k+1}}\right\rfloor$$

thus for every $k = 1 \ldots \lfloor \log_2{n} \rfloor + 1$ the number of those terms is:

$$\left\lfloor\frac{2n-1+2^k}{2^{k+1}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor$$

and so we can derive from $\eqref{eq2}$ the following, again for $n$ positive integer:

$$n = 1 + \sum_{k=1}^{\lfloor \log_2{n} \rfloor + 1} \left( \left\lfloor\frac{2n-1+2^k}{2^{k+1}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor \right)k \tag{3}\label{eq3}$$

One can then see with some numerical tests that the differences:

$$\left\lfloor\frac{2n-1+2^k}{2^{k+1}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor \frac{n}{2^{k+1}} \right\rfloor$$

are "nearly" the binary coefficients $c_{k-1}$ as defined above. More precisely, the following equation holds for every natural number $n$, or at least I have tested it up to $n = 10000$:

$$n - \sum_{k=0}^{\lfloor \log_2{n} \rfloor}\left(\left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+2}}{2^{k+3}}\right\rfloor - \left\lfloor \frac{n}{2^{k+2}} \right\rfloor\right)2^k = \begin{cases} 2^{\nu_2(n)-1}, & \text{if $n$ is even} \\ 1, & \text{if $n$ is odd} \end{cases} \tag{4}\label{eq4}$$

where $\nu_2(n)$ is the $2$-adic valuation of $n$ i.e. the highest exponent $\nu_2(n)$ such that $2^{\nu_2(n)}$ divides $n$.

Equation \eqref{eq4} led to conjecture \eqref{eq1}, so \eqref{eq1} and \eqref{eq4} are related, but I am not able to prove any of the two.

Note: I have posted a linked question specifically for equation \eqref{eq4}.

Answer 1

I have written a proof for your equation ($4$) in the linked question, with the procedure to prove your ($1$) in this question being similar. First, to reduce the algebra involved, define

$$m = \lfloor \log_2 n \rfloor, \; \; j = \nu_2(n) \tag{1}\label{eq1A}$$

Since $m$ is the index of the largest non-zero binary coefficient of $n$, this means

$$n = \sum_{i = 0}^{m}c_i 2^i, \; 0 \le c_i \le 1 \; \forall \; 0 \le i \le m \tag{2}\label{eq2A}$$

Next, using \eqref{eq1A} and a change of the index variable, your ($3$) can be written as

$$\begin{equation}\begin{aligned} n & = 1 + \sum_{k=1}^{\lfloor \log_2{n} \rfloor + 1} \left( \left\lfloor\frac{2n - 1 + 2^k}{2^{k+1}}\right\rfloor - \left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor \right)k \\ & = 1 + \sum_{k=0}^{m} \left(\left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n - 1 + 2^{k+2}}{2^{k+3}}\right\rfloor \right)(k + 1) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

With just the first floor function value which is being summed, using \eqref{eq2A} gives

$$\begin{equation}\begin{aligned} \left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor & = \left\lfloor\frac{\sum_{i = 0}^{m}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\ & = \left\lfloor\frac{\sum_{i = k+1}^{m}c_i 2^{i+1} + \sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\ & = \left\lfloor\frac{\sum_{i = k+1}^{m}c_i 2^{i+1}}{2^{k+2}} + \frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\ & = \left\lfloor\sum_{i = k+1}^{m}c_i 2^{(i+1) - (k+2)} + \frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\ & = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + \left\lfloor\frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\ & = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + \left\lfloor\frac{(c_k + 1)\left(2^{k+1}\right) + (\sum_{i = 0}^{k - 1}c_i 2^{i+1} - 1)}{2^{k+2}}\right\rfloor \\ \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

Note the numerator of the fraction in \eqref{eq4A} is greater than or equal to $2^{k+2}$ iff $c_k = 1$ and there's at least one $c_i = 1$ for some $0 \le i \le k - 1$, with the latter condition only being true if $k \gt j$. To make this simpler to handle, define a boolean type indicator function of

$$B(e) = \begin{cases} 0 & e \text{ is false} \\ 1 & e \text{ is true} \end{cases} \tag{5}\label{eq5A}$$

Using this function, \eqref{eq4A} can be simplified to

$$\left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) \tag{6}\label{eq6A}$$

The second floor function being summed is basically the same, but with the powers of $2$ being $1$ larger, so it becomes

$$\left\lfloor\frac{2n - 1 + 2^{k+2}}{2^{k+3}}\right\rfloor = \sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k+1}B(k + 1 \gt j) \tag{7}\label{eq7A}$$

Using \eqref{eq6A} and \eqref{eq7A} gives

$$\begin{equation}\begin{aligned} & \left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n - 1 + 2^{k+2}}{2^{k+3}}\right\rfloor \\ & = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) - \left(\sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k+1}B(k + 1 \gt j)\right) \\ & = \left(c_{k+1} + \sum_{i = k+2}^{m}c_i 2^{i-k-1}\right) + c_{k}B(k \gt j) - \sum_{i = k+2}^{m}c_i 2^{i-k-2} - c_{k+1}B(k + 1 \gt j) \\ & = \left(c_{k+1} + 2\sum_{i = k+2}^{m}c_i 2^{i-k-2}\right) - \sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k}B(k \gt j) - c_{k+1}B(k + 1 \gt j) \\ & = \sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k+1} + c_{k}B(k \gt j) - c_{k+1}B(k + 1 \gt j) \\ & = \left\lfloor\frac{n}{2^{k+2}}\right\rfloor + \left(c_{k+1} + c_{k}B(k \gt j) - c_{k+1}B(k + 1 \gt j)\right) \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

Next, define

$$f(k, j) = c_{k+1} + c_{k}B(k \gt j) - c_{k+1}B(k + 1 \gt j) \tag{9}\label{eq9A}$$

For $k \lt j - 1$, you get $c_{k} = c_{k+1} = 0$, so $f(k, j) = 0 = c_{k}$. With $k = j - 1$, you then get $c_{k} = 0$, $c_{k+1} = c_j = 1$, $B(k + 1 \gt j) = 0$, so $f(k, j) = c_{k+1} = c_j$. Next, with $k = j$, you get $B(k \gt j) = 0$, $B(k + 1 \gt j) = 1$, so $f(k, j) = c_{k+1} - c_{k+1} = 0$. Finally, for $k \gt j$, since $B(k, j) = B(k + 1 \gt j) = 1$, you have $f(k, j) = c_{k+1} + c_{k} - c_{k+1} = c_{k}$. In summary, then, you have $f(k,j) = c_k$ for all $k$ except for $k = j - 1$ where it's $c_j$ and for $k = j$ where it's $0$, i.e., those $2$ values are mixed around.

Note, though, if $j = 0$, then $k = j - 1 = -1$. Nonetheless, since the right side multiplier in \eqref{eq3A} for $k = -1$ is $k + 1 = 0$, so changing the starting index to $-1$ doesn't change the sum, I do this below in \eqref{eq10A} to use just one set of calculations for $j = 0$ and $j \gt 0$, and then switch back to starting at $k = 0$ near the end.

Using \eqref{eq9A} in \eqref{eq8A} and then substituting the result into \eqref{eq3A}, plus using the results & issues discussed in the above $2$ paragraphs including $c_{j-1} = 0$ and $c_j = 1$, and also what you're already noted that $c_k = \left\lfloor \frac{n}{2^{k}} \right\rfloor \bmod 2$, gives

$$\begin{equation}\begin{aligned} n & = 1 + \sum_{k=0}^{m}\left(\left\lfloor\frac{n}{2^{k+2}}\right\rfloor + f(k,j)\right)(k + 1) \\ & = 1 + \sum_{k=0}^{m}\left\lfloor\frac{n}{2^{k+2}}\right\rfloor(k + 1) + \sum_{k=-1}^{m}f(k,j)(k + 1) \\ & = 1 + \sum_{k=0}^{m}\left\lfloor\frac{n}{2^{k+2}}\right\rfloor(k + 1) + \sum_{k=-1}^{j-2}c_k(k + 1) + c_j((j-1)+1) + \sum_{k=j+1}^{m}c_k(k + 1) \\ & = 1 + \sum_{k=0}^{m}\left\lfloor\frac{n}{2^{k+2}}\right\rfloor(k + 1) + \sum_{k=-1}^{j-1}c_k(k + 1) + (c_j)(j + 1) - 1 + \sum_{k=j+1}^{m}c_k(k + 1) \\ & = \sum_{k=0}^{m}\left\lfloor\frac{n}{2^{k+2}}\right\rfloor(k + 1) + \sum_{k=0}^{m}c_k(k + 1) \\ & = \sum_{k=0}^{m}\left[ \left\lfloor \frac{n}{2^{k+2}} \right\rfloor + \left(\left\lfloor \frac{n}{2^{k}} \right\rfloor \bmod 2 \right) \right](k+1) \end{aligned}\end{equation}\tag{10}\label{eq10A}$$