For all $n,k$ in positive integers, there exists $m_1,...,m_k$ such that the following holds

Question

Let $n,k$ be two positive integers. Prove that there exists $m_1,...,m_k$ in the positive integers such that

$$1+\frac{2^k-1}{n}=\prod_{i=1}^k\left(1+\frac{1}{m_i}\right)$$ Here is my attempt

We're going to construct a solution for the $m_i$'s, but rather than presenting it right away I will take time to go through the motivation behind it.

Assume that $\exists m_1,...,m_k$ such that $$1+\frac{2^k-1}{n}=\prod_{i=1}^k\left(1+\frac{1}{m_i}\right)$$ And consider $$\begin{align} \prod_{i=1}^{k+1}\left(1+\frac{1}{m_i}\right)&=\left(1+\frac{1}{m_{k+1}}\right)\prod_{i=1}^k\left(1+\frac{1}{m_i}\right) \\ &= \left(1+\frac{1}{m_{k+1}}\right)\left(1+\frac{2^k-1}{n}\right) \\ &= 1+\frac{2^{k+1}-1}{n} \end{align} $$ Where the last step follows from the assumption. Hence $$\frac{1}{m_{k+1}}=\frac{2^k}{2^k+n-1} \text{ or } m_i=\frac{2^{i-1}+n-1}{2^{i-1}}$$ Now we have to prove this solution actually works. In other words, $$1+\frac{2^k-1}{n}=\prod_{i=1}^k\left(1+\frac{2^{i-1}}{2^{i-1}+n-1}\right)=\prod_{i=1}^k\left(\frac{2^{i}+n-1}{2^{i-1}+n-1}\right)$$ but expanding the RHS is not easy so let's go ahead and assume that the above is true $\forall k\le s$ we'll show that it's true for $k=s+1$

$$\begin{align}\prod_{i=1}^{s+1}\left(\frac{2^{i}+n-1}{2^{i-1}+n-1}\right)&=\frac{2^{s+1}+n-1}{2^{s}+n-1}\prod_{i=1}^{s}\left(\frac{2^{i}+n-1}{2^{i-1}+n-1}\right) \\&= \frac{2^{s+1}+n-1}{2^{s}+n-1}\left(1+\frac{2^s-1}{n}\right) \\&= 1+\frac{2^{s+1}-1}{n}\end{align} $$

Now my question is: Are the $m_i$'s integers? Since $$m_i=\frac{2^{i-1}+n-1}{2^{i-1}}$$ Then we should have $2^{i-1}\mid n-1$ but that's not true $\forall n,i$?

Answer 1

The $m_i$'s in your construction are not necessarily integers.

To illustrate the problem, consider the simple case of $k = 2$. You want to write $\frac{n + 3}n$ as a product $\frac{m_1 + 1}{m_1} \cdot \frac{m_2 + 1}{m_2}$.

Your strategy goes for $m_1 = n$ and $m_2 = \frac{n + 1}2$. However we see that $\frac{n + 1}2$ is not necessarily an integer.

In fact, the construction above works when $n$ is odd. For $n$ even, we can use instead $m_1 = \frac n 2$ and $m_2 = n + 2$.

---

This indicates how the solution would look like: you should separate the two cases of even/odd $n$.

We prove by induction on $k$. For $k = 1$, simply choosing $m_1 = n$ works. Now assume that the result is true for $k$ and we prove it for $k + 1$.

Thus we want to write $\frac{n + 2^{k + 1} - 1}n$ as a product $\prod_{i = 1}^{k + 1} \frac{m_i + 1}{m_i}$. As above, we will consider the parity of $n$.

If $n$ is odd, then we can write $$\frac{\frac{n + 1}2 + 2^k - 1}{\frac{n + 1}2} = \prod_{i = 1}^k \frac{m_i + 1}{m_i}$$ by induction hypothesis applied to $\frac{n + 1}2$. Choosing $m_{k + 1} = n$ gives us the willing identity.

If $n$ is even then we can write $$\frac{\frac n 2 + 2^k - 1}{\frac n 2} = \prod_{i = 1}^k \frac{m_i + 1}{m_i}$$ by induction hypothesis applied to $\frac n 2$. Choosing $m_{k + 1} = n + 2^{k + 1} - 2$ gives us the willing identity.

This finishes the induction step and hence the proof.

Answer 2

After thinking for some days, I would like to share my observations from the first answer and how it relates to binary notations and bit operations. This answer is based on the same recursion step and the same algorithm.

$$\frac{n_{k+1}+2^{k+1}-1}{n_{k+1}} = \frac{n_k+2^{k}-1}{n_{k}}\cdot \frac{m_{k+1}+1}{m_{k+1}} \tag 1$$

where $n_k$ is chosen depending on whether $n_{k+1}$ is even or odd,

$$\begin{align*} n_{k+1} \mapsto n_k &= \begin{cases} \dfrac {n_{k+1}}2,& n_{k+1}\equiv 0 \pmod 2\\ \dfrac {n_{k+1}+1}2,& n_{k+1}\equiv 1 \pmod 2\\ \end{cases}\\ &= \left\lfloor\frac{n_{k+1}+1}2\right\rfloor = \left\lceil\frac{n_{k+1}}2\right\rceil \tag2 \end{align*}$$

---

From $n_{k+1}+2^{k+1}-1$ to $n_k+2^k-1$ in the numerators of $(1)$ is actually simple: it's a floored division by $2$, or a right shift by $1$ bit:

$$\begin{align*} n_k+2^k-1 &= \left\lfloor\frac{n_{k+1}+1}2\right\rfloor + 2^k-1\\ &= \left\lfloor\frac{n_{k+1}+1}2 +2^k-1\right\rfloor\\ &= \left\lfloor\frac{n_{k+1}+2^{k+1}-1}2\right\rfloor \end{align*}$$

But from $n_{k+1}$ to $n_k$ in the denominators is less obvious. Applying $(2)$ is not simply a floored division nor a right shift by $1$ bit. Repeated application of $(2)$ to a positive $n$ will also never get to $0$. But there's still some pattern, by noting the parity of $n \pmod 2$ at each step, for example when applying to $n=10$,

$$\underbrace{10}_{\equiv 0} \mapsto \underbrace{5}_{\equiv1} \mapsto \underbrace{3}_{\equiv1}\mapsto \underbrace{2}_{\equiv0}\mapsto \underbrace{1}_{\equiv 1} \mapsto \underbrace{1}_{\equiv 1} \mapsto \ldots$$

Writing the remainders as bits from the least to the most significant, this gives an infinite binary string $\ldots1111\ 0110_2$. And one might notice this is the two's complement notation of $-n = -10_{10}$! In fact, considering how $-n_{k+1}$ and $-n_k$ are related by $(2)$,

$$-n_k = -\left\lceil\frac{n_{k+1}}2\right\rceil = \left\lfloor\frac{-n_{k+1}}2\right\rfloor$$

so applying arithmetic right shift by $1$ bit to $-n_{k+1}$ does give $-n_k$.

Hence both the numerators and denominators in $(1)$ are related by binary right shifts or floored divisions:

$$-\frac{n_{k+1}+2^{k+1}-1}{-n_{k+1}} \overset{>>1}{\underset{>>1}\longmapsto} -\frac{n_k+2^k-1}{-n_k}$$

---

On the left hand side, if both the numerators and denominators were even, i.e. with last bits $0$, then the two sides would be equal. But the numerators and denominators always have opposite parity, and the $\frac{1+m_{k+1}}{m_{k+1}}$ multiplier is here to round the odd one down to even.

If $n_{k+1}$ is even, then the numerator is odd, so choose $m_{k+1}$ to reduce the numerator by $1$:

$$\begin{align*} -\frac{n_{k+1}+2^{k+1}-1}{-n_{k+1}} &= -\frac{n_{k+1}+2^{k+1}-2}{-n_{k+1}}\cdot \frac{n_{k+1}+2^{k+1}-1}{n_{k+1}+2^{k+1}-2}\\ &= -\frac{n_k+2^k-1}{-n_k}\left(1+\frac{1}{n_{k+1}+2^{k+1}-2}\right) \end{align*}$$

If $n_{k+1}$ is odd, then the denominator is odd, so choose $m_{k+1}$ to reduce the denominator by $1$ (to be more negative):

$$\begin{align*} -\frac{n_{k+1}+2^{k+1}-1}{-n_{k+1}} &= -\frac{n_{k+1}+2^{k+1}-1}{-n_{k+1}-1}\cdot \frac{-n_{k+1}-1}{-n_{k+1}}\\ &= -\frac{n_k+2^k-1}{-n_k}\left(1+\frac{1}{n_{k+1}}\right) \end{align*}$$

This explains why the $m_{k+1}$ appears to be quite different depending on the parity of $n_{k+1}$:

$$m_{k+1} = \begin{cases} n_{k+1}+2^{k+1}-2,& n_{k+1}\equiv 0 \pmod 2\\ n_{k+1},& n_{k+1}\equiv 1 \pmod 2\\ \end{cases} \tag3$$

To conclude, by considering the recursion step $(1)$ with negated denominators, the choices of $n_k$ and $m_{k+1}$ are related to binary notations and bit shifts. Running the recursion down to $k=0$ gives the last $m_1=n_1$ and a fraction that can be eliminated: $\dfrac{n_0+2^0-1}{n_0} = 1$.

---

Omitted detail on two's complement, which is non-standard:

$$-10_{10} \overset{???}= \ldots1111\ 0110_2 = 2+4+16+32+64+\cdots$$

Either all mentions of bit shifts can be ignored and consider floored division only.

Or a fixed and finite number $L$ can be chosen to be the number of bits for two's complement. $L$ bits should be long enough to represent the numerator $n+2^k-1$ (and hence also the denominator $\pm n$).