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$?
Best Answer
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.