4
$\begingroup$

While answering a question here I noticed that:

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

for every natural number $n$.

I tried to demonstrate it using Legendre's formula (alternate form), like in the answer mentioned above, but without success.

Anyone can help?

$\endgroup$
3
$\begingroup$

I'm not very knowledgeable about number theory, so I don't know any way to solve this using Legendre's formula (including its alternate form) or any other such thing. However, I believe what I show below may not be as "refined" as it could be, but it's correct. I tried to make it as simple & complete as possible, so it's quite possibly more wordy than necessary. I wanted to help ensure it's understandable not only to the OP, but also anybody else reading this who might not have very much number theory knowledge.

You can solve this by using mathematical induction. Note that your requested formula of

$$n = 1 + \sum_{k \, = \, 1}^{n} \left\lfloor \log_{2}\cfrac{2n - 1}{2k - 1} \right\rfloor \tag{1}\label{eq1} $$

works for $n = 1$ as it becomes just simply $n = 1 + \left\lfloor \log_{2}\cfrac{2 - 1}{2 - 1} \right\rfloor = 1 + 0 = 1$. Assume that \eqref{eq1} works for all $n <= m$ for some natural number $m$. To prove it works for $n = m + 1$, there are $3$ specific things to note.

  1. Going from $n = m$ to $n = m + 1$ involves summing one extra term, with the final term always being $0$ as it is $\left\lfloor \log_{2}\cfrac{2m + 1}{2m + 1} \right\rfloor$.
  2. For each term in both summations, i.e., for $k = 1, 2, 3, \ldots, m$, the value is non-decreasing, i.e., $\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor \ge \left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor$, since $\log_{2}$ is an increasing function.
  3. Based on the above considerations, to prove that \eqref{eq1} works, I need to show that exactly one of the terms always increases by exactly $1$.

For any $1 \leq k \leq m$,

$$\left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor = j \tag{2}\label{eq2} $$

for some integer $j \ge 0$, means that

$$2^j \leq \cfrac{2m - 1}{2k - 1} \lt 2^{j + 1} \tag{3}\label{eq3} $$

Note the "$\leq$" is only needed for $j = 0$, else it can be just "$\lt$" instead as the numerator and denominator of $\cfrac{2m - 1}{2k - 1}$ are odd integers and, thus, their division can't be an even integer. In a similar fashion, consider that if for any specific $k$ we get that

$$\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor = j + 1 \tag{4}\label{eq4} $$

then we also have that

$$2^{j + 1} \lt \cfrac{2m + 1}{2k - 1} \lt 2^{j + 2} \tag{5}\label{eq5} $$

Note the increase will not be by more than $1$ as, even for $k = 1$, going from $2m - 1$ to $2m + 1$ is not sufficient for such an increase. Since $2k - 1 \gt 0$, we can multiply everything in both \eqref{eq3} and \eqref{eq5} by $2k - 1$ and combine the $2$ equations through their common $2^{j + 1}$ value to get that

$$2m - 1 \lt 2^{j + 1}\left(2k - 1\right) \lt 2m + 1 \tag{6}\label{eq6} $$

This shows that $2^{j + 1}\left(2k - 1\right)$ must be the sole even integer between the $2$ consecutive odd integers of $2m - 1$ and $2m + 1$. This even integer is $2m$, with $j + 1$ being the power of $2$ of the factorization of this even integer and $2k - 1$ being the odd part of the integer. This confirms there always exists one, and only one, such value which will increase by $1$, as the steps are reversible. As such, this means by the inductive step that \eqref{eq1} works for $n = m + 1$ as well, thus finishing the proof by induction.

As an example, consider the case of $n = 5$ going to $n = 6$, so $2n - 1$ goes from $9$ to $11$. The value in between is $10 = 2 \times 5$. Thus, $j = 0$ here and $2k - 1 = 5$, so $k = 3$. This indicates that the $3$rd term, and no other, will increase by $1$, going from $0$ to $1$. First, here are the terms for $n = 5$

\begin{align} 5 & = 1 + \left\lfloor \log_{2} \cfrac{9}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{9} \right\rfloor \\ & = 1 + 3 + 1 + 0 + 0 + 0 \tag{7}\label{eq7} \end{align}

Next, here are the terms for $n = 6$

\begin{align} 6 & = 1 + \left\lfloor \log_{2} \cfrac{11}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{9} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{11} \right\rfloor \\ & = 1 + 3 + 1 + 1 + 0 + 0 + 0 \tag{8}\label{eq8} \end{align}

The final lines of \eqref{eq7} and \eqref{eq8} show that, as predicted, the $3$rd term is the only one to change, going up by $1$ from $0$ to $1$.

$\endgroup$
  • $\begingroup$ Nice deduction and proof. $\endgroup$ – marty cohen Jan 18 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.