Induction

http://www.artofproblemsolving.com/wiki/index.php?title=2013_IMO_Problems/Problem_1

This is exactly the wiki solution, but anyways.. We use induction of $k$. For $k=1$, we can just take $m_1=n$ to finish. Assume that it is true for $k-1$, and we prove the statement for $k$. Now it suffices to find the two integers $l$ and $m_k$ such that $$1+\frac{2^k-1}{n}= \left(1+\frac{2^{k-1}-1}{l}\right)\left(1+\frac{1}{m_k}\right)$$If we find these two integers, by our induction hypothesis, we can write $\left(1+\frac{2^{k-1}-1}{l}\right)$ as $$\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k-1}}\right)$$finishing the induction. To get rid of the difference of the exponents of $2$ in $2^{k-1}$ and $2^k$, let us take $l=\frac{n+c}{2}$. This $c$ will be determined later. Now we have $$\frac{n+2^k-1}{n} = \left(\frac{n+c+2^k-2}{n+c}\right)\left(\frac{m_k+1}{m_k}\right)$$ We can easily find that $c=1$ and $m_k=n$ works, but only for $n \equiv 1 \pmod{2}$. If $n \equiv 0 \pmod{2}$, we take $c=0$ and note that $m_k=n+2^k-2$ works here. Therefore, we found a pair of $l, m_k$ for all $n$, which completes the induction as desired. $\blacksquare$

Use the induction on $k$. For $k=1$, then it is clear that $1+\frac{2^1-1}{n}=1+\frac{1}{n}$ for all $n\in\mathbb{N}$, and the result follows by taking $m_1=n$. Now, suppose that for some $N\in\mathbb{N}$, the result holds for all $k\leq N$ and for all $n\in\mathbb{N}$. We want to show that there exist positive integers $m_1,m_2,\ldots,m_{N+1}$ such that \begin{align*} 1+\frac{2^{N+1}-1}{n}=\left(1+\frac{1}{m_1}\right)\left(1+\frac{1}{m_2}\right)\cdots\left(1+\frac{1}{m_{N+1}}\right) \end{align*}Case 1: $n$ is even. \begin{align*} 1+\frac{2^{N+1}-1}{n} &=1+\frac{2^{N+1}-2}{n}+\frac{1}{n}=1+\frac{2^{N}-1}{\frac{n}{2}}+\frac{1}{n}\\ &=1+\frac{2^{N}-1}{\frac{n}{2}}+\left(\frac{\frac{n}{2}+2^N-1}{\frac{n}{2}}\cdot\frac{1}{n+2^{N+1}-2}\right)\\ &=\left(1+\frac{2^{N}-1}{\frac{n}{2}}\right)\cdot\left(1+\frac{1}{n+2^{N+1}-2}\right) \end{align*}Thus by the hypothesis and by taking $m_{N+1}=n+2^{N+1}-2$, we prove this case. Case 2: $n$ is odd. \begin{align*} 1+\frac{2^{N+1}-1}{n} &=1+\frac{2^{N+1}-2}{n}+\frac{1}{n}=1+\left(\frac{2^{N}-1}{\frac{n+1}{2}}\cdot\frac{n+1}{n}\right)+\frac{1}{n}\\ &=1+\left(\frac{2^{N}-1}{\frac{n+1}{2}}\right)\cdot\left(1+\frac{1}{n}\right)+\frac{1}{n}\\ &=1+\frac{2^{N}-1}{\frac{n+1}{2}}+\frac{1}{n}\cdot\frac{2^{N}-1}{\frac{n+1}{2}}+\frac{1}{n}\\ &=\left(1+\frac{2^{N}-1}{\frac{n+1}{2}}\right)\cdot\left(1+\frac{1}{n}\right) \end{align*}Thus by the hypothesis and by taking $m_{N+1}=n$, we prove this case.

Induction on $n$: Case $n=1$ is obvious. Assume that $n$ devides $m_i$ and that there exist $m_1,...,m_k$ satisfying the condition, we expand, multiply everything by $n+1$ notice that the left side is constant $2^k +1$ (delete $n+1$from both sides) so it is the same when taking $n$. Putting every product equal to the previous we get the new $m_i$ (for example $\frac{n+1}{m'_1}=\frac{n}{m_1}$ and since $n$ and $n+1$ are relatively prime and $n$ devides $m_1$ we get $m'_1$ an integer divisible by $n+1$) and we are done

There exist integers $q,r$ with $\ 0\leq r<2^{k-1}$ such that $-n=2^{k-1}q+r$ Let $r=2^{a_1}+2^{a_2}+\dots +2^{a_l}$ be the binary representation of $r$, where $0\le a_1<a_2<\dots <a_l<k-1$. If $r=0$, then $l=0$ and $\{a_1,a_2,\dots,a_l\} = \{\}$ Define $\{a_{l+1}\ge a_{l+2}>\dots >a_{k}\} = \{0,1,\dots,k-1\}-\{a_1,a_2,\dots,a_l\}$. Note that $a_{l+1}=k-1$ Define $n_1=n$, and $n_{i+1}=n_i+2^{a_i}$ for $i=1,2,\dots,k$ Note that $n_{k+1} = n+2^{a_1}+2^{a_2}+\dots +2^{a_k} =n+2^0+2^1+\cdots2^{k-1} = n+2^k-1$, since $\{a_1,a_2,\dots,a_k\} = \{0,1,\dots,k-1\}$ We will prove that $2^{a_i}\mid n_i$ for every $1\le i\le k$. For $1\le i\le l$, we have that $n_i = n+2^{a_1}+2^{a_2}+\dots+2^{a_{i-1}} = -2^{k-1}q - 2^{a_i} - 2^{a_{i+1}} -\dots-2^{a_l}$, which is multiple of $2^{a_i}$ since $a_i<\dots <a_l<k-1$ For $i=l+1$, we have $n_{l+1} = n+2^{a_1}+2^{a_2}+\dots +2^{a_l} = n+r$ which is multiple of $2^{k-1}=2^{a_{l+1}}$ For $l+2\le i\le k$, we have that $n_i = n+r+2^{a_{l+1}}+\cdots+2^{a_{i-1}}$, which is multiple of $2^{a_i}$, since $k-1= a_{l+1}>\dots >a_{i-1}>a_i$ Then $2^{a_i}\mid n_i$ for every $1\le i\le k$. Let's define $m_i=\frac{n_{i}}{2^{a_{i}}}$ for $1\le i\le k$ $$\prod_{i=1}^{k}\left(1+\frac{1}{m_i}\right) = \prod_{i=1}^{k}\left(1+\frac{2^{a_i}}{n_i}\right) = \prod_{i=1}^{k}\left(\frac{n_i+2^{a_i}}{n_i}\right) = \prod_{i=1}^{k}\frac{n_{i+1}}{n_i} = \frac{n_{k+1}}{n_1} = \frac{n+2^k-1}{n} = 1+\frac{2^k-1}{n}$$

By induction on $k \ge 1$. When $k = 1$ there is nothing to prove. For the inductive step, if $n$ is even, write \[ \frac{n + (2^k-1)}{n} = \left( 1 + \frac{1}{n + (2^k-2)} \right) \cdot \frac{\frac n2 + (2^{k-1}-1)}{\frac n2} \]and use inductive hypothesis on the second term. On the other hand if $n$ is odd then write \[ \frac{n + (2^k-1)}{n} = \left( 1 + \frac{1}{n} \right) \cdot \frac{\frac{n+1}{2} + (2^{k-1}-1)}{\frac{n+1}2} \]and use inductive hypothesis on the second term.

Oops this problem intimidated me and then took ten minutes

We will prove the statement by inducting on $k$. Base case: $k=1$. Then just choose $m_1=n$. Case 1: $n$ is odd. Then \begin{align*} 1+\frac{2^k-1}{n} &= \frac{2^k + (n-1)}{n} \\ &= \frac{n+1}{n} \cdot \frac{2^k+(n-1)}{n+1} \\ &= \left(1+\frac{1}{n} \right)\left( 1+\frac{2^k-2}{n+1} \right)\\ &= \left(1+\frac{1}{n} \right)\left( 1+\frac{2^{k-1}-1}{(n+1)/2} \right). \end{align*}By the induction hypothesis, there exist $m_1,\ldots,m_{k-1}$ such that \[1+\frac{2^{k-1}-1}{(n+1)/2} = \left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k-1}}\right), \]so we let $m_k=n$ and we are done. Case 2: $n$ is even. Let $n=2m$. Then \begin{align*} 1+\frac{2^k-1}{n} &= \frac{2^k + (2m-1)}{2m} \\ &= \frac{2^k+(2m-1)}{2^k+(2m-2)} \cdot \frac{2^k+(2m-2)}{2m} \\ &= \left(1+\frac{1}{2^k+(2m-2)} \right)\left( \frac{2^{k-1}+(m-1)}{m} \right)\\ &= \left(1+\frac{1}{2^k+(2m-2)} \right)\left( 1+\frac{2^{k-1}-1}{m} \right). \end{align*}By the induction hypothesis, there exist $m_1,\ldots,m_{k-1}$ such that \[1+\frac{2^{k-1}-1}{m} = \left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k-1}}\right), \]so we let $m_k=2^k+(2m-2)$ and we are done. $\blacksquare$

Looks pretty darn hard, but playing around with values of $k$ gives a pretty clear picture that an induction is the way to go here. Of course, base case, aka $k=1$ is obvious, so let's try to figure out what we should even try to induct... In our induction, all we really need to prove is that, for all $n$, there exists some integers $a$ and $t$ such that $\frac{n+2^k-1}n=(\frac{t+2^{k-1}-1}{t})(\frac{a+1}a)$. Expanding, cross-multiplying and grouping gives us the expression: $$a(t \cdot 2^k -t+n-n \cdot 2^{k-1})=n(t-1+2^{k-1})$$Here we can clearly see that putting $t$ in the neighbourhood of $\frac n2$ should immediately gives us the required integer $a$. Thus we divide our induction into $2$ branches based on the parity of $n$: Case $1$: $n$ is even Put $t= \frac n2 =>a(n \cdot 2^{k-1}- n \cdot 2^{k-1} +\frac n2)=n(\frac n2 - 1+2^{k-1}) =>a=n-2+2^{k}$ Case $2$: $n$ is odd Looks a little harder to deal with, but it turns out that $t=\frac{n+1}2$ works out just fine- $a(\frac{n+1}2 \cdot 2^k-n \cdot 2^{k-1} +\frac{2n-n-1}2)=n(\frac{n-1+2^k}2)$. Simplifying gives us $a(\frac{2^{k}+n-1}2)=n \cdot \frac{2^k+n-1}{2} =>a=n$. Thus we're done- two comments: Firstly, wow such different $a$s for the $n$ even and odd case? Well, it works, but just something that piqued my curiosity... Secondly, this is apparently the hardest P1 (!) in the last decade- probably just because of the monstrosity that is this expression, because the induction was relatively straightforward...

Nice and easy! The result is quite surprising, which makes the result all the nicer. However, one can deduce what's going on by taking small cases, like $k=2$. Congratulations to the problem author on the cool question! Induct on $k\ge 1$. The base case is trivial, set $m_1=n$. Induction Step: We take two cases. Case 1: $n$ is even. Let $n=2m$ for some $m$, then we have \[1+\frac{2^k-1}{n} = \frac{n+2^k-1}{n} = \frac{n+2^k-1}{n+2^k-2} \cdot \frac{n+2^k-2}{n} = \left(1+\frac{1}{n+2^k-2}\right)\left(1+\frac{2^{k-1}-1}{m}\right).\]Then we can find $m_1,\dots , m_{k-1}$ by the induction hypothesis and set $m_k=n+2^k-2$, hence we are done. Case 1: $n$ is odd. Let $n=2m-1$ for some $m$, then we have \[1+\frac{2^k-1}{n} = \frac{n+2^k-1}{n} = \frac{n+1}{n} \cdot \frac{n+2^k-1}{n+1} = \left(1+\frac{1}{n}\right)\left(1+\frac{2^{k-1}-1}{m}\right).\]Then we can find $m_1,\dots , m_{k-1}$ by the induction hypothesis and set $m_k=n$, hence we are done.

oops apparently the concept of induction doesn't exist in my brain Write $n+2^k-1$ in binary and apply the following algorithm: Part 1: Let $A = \{ 1 \leq a \leq k \mid \text{the a-th digit from the right is a 1} \}$. Step $i$ of part 1 is as follows: If $i \in A$, subtract $2^{i-1}$; otherwise do nothing. Perform steps $1$ to $k$ of part 1 in order. Part 2: Step $i$ of part 2 is as follows: If $i \in A$, do nothing; otherwise subtract $2^{i-1}$. Perform steps $k$ to $1$ of part 2 in that order (i.e. starting with step $k$ and ending with step $1$). This algorithm generates a decreasing list of $k+1$ numbers, which we let be $a_0, a_1, \dots , a_{k}$. Note that $a_0=n+2^k-1$ and $$a_k = a_0-2^0-2^1- \cdots -2^{k-1} = n$$. Furthermore, note that $a_i-a_{i+1}$ divides both $a_{i+1}$ and $a_i$ for each $0 \leq i \leq k-1$. Thus $\frac{a_{i}}{a_{i+1}}$ is of the form $1+\tfrac{1}{m}$ for some $m$, and we have $$1+\frac{2^k-1}{n} = \frac{a_0}{a_1} \cdot \frac{a_1}{a_2} \cdots \frac{a_{k-1}}{a_{k}}$$as desired. To follow along, here's an example for $k=4, n=6$: $$n+2^k-1=21=10101_2 \to 10100_2 \to 10000_2 \to 1000_2 \to 110_2$$which gives the example $$1+\frac{2^4-1}{6} = \frac{21}{20} \cdot \frac{20}{16} \cdot \frac{16}{8} \cdot \frac{8}{6}$$

Well, no one can deny that they tried out the initial values before getting the solution. Mine is the same as most of yours.(Odd and Even cases).

We will use induction. If $n$ is even, then we may choose one $m_i$ to be $n + 2^k - 2$ since\[1 + \frac{2^k - 1}{n} = \left(1 + \frac{1}{n + 2^k - 2}\right)\left(1 + \frac{2^{k - 1} - 1}{\frac{n}{2}}\right)\]so it remains to do the problem for reduced $k - 1$ and $\frac{n}{2}$. If $n$ is odd, then we may choose one $m_i$ to be $n$ since\[1 + \frac{2^k - 1}{n} = \left(1 + \frac{1}{n}\right)\left(1 + \frac{2^{k - 1} - 1}{\frac{n + 1}{2}}\right)\]so it remains to do the problem for reduced $k - 1$ and $\frac{n + 1}{2}$. In this manner, we can keep on picking $m_i$ based on the parity of $n$ after each turn and eventually we will get to $k$ values of $m_i$ that will make the statement true. $\blacksquare$

My solution is also similar to you all.. But still posting for storage We will apply induction We will check the case when $k=1$ clearly then $1+\frac{2-1}{y}=1+\frac{1}{y}$ hence $m_1=y$ Let's assume that for some $k=x$ it's true then $1+\frac{2^x-1}{y}=(1+\frac{1}{m_1})(1+\frac{1}{m_2})...(1+\frac{1}{m_x})$ Then for $k=x+1$ we must have $1+\frac{2^{x+1}-1}{y}=(1+\frac{2^x-1}{z})(1+\frac{1}{m_{x+1}})=(1+\frac{2^x-1}{z})(\frac{m_{x+1}+1}{m_{x+1}}$ then $m_{x+1}=n$ then $z=\frac{n+1}{2}$ for odd $y$ satisfies. And if $y$ is even $z+2^x-1=m_{x+1},z=\frac{n}{2}$ satisfies.

We will use induction on $k$. Trivially, the base case $k = 1$ holds as $m_1$ is just $n$. For the inductive step, assume that this holds for $k-1$. Note that if $n$ is even, then: $$ 1 + \frac{2^k - 1}{n} = (1 + \frac{2^{k-1} - 1}{\frac{n}{2}})(1 + \frac{1}{2^k + n - 2}) = (1 + \frac{1}{m_1})...(1+\frac{1}{m_{k-1}})(1 + \frac{1}{2^k + n - 2}).$$ Letting $m_k = 2^k + n - 2$, we see that this holds for even $n$. Similarly, if $n$ is odd, then notice that: $$ 1 + \frac{2^k - 1}{n} = (1 + \frac{2^{k-1} - 1}{\frac{n+1}{2}})(1 + \frac{1}{n}) = (1 + \frac{1}{m_1})...(1+\frac{1}{m_{k-1}})(1 + \frac{1}{n}).$$ Letting $m_k = n$, we see that this holds for odd $n$. By induction we are done. $\Box$

Fun problem to play with We use strong induction. Base cases trivial. Case 1: $n=2a$ Then $\frac{2^k+2a-1}{2a}= (1+\frac{1}{2^k+2a-2})(\frac{2^{k-1}+a-1}{a})$. We can write this in $1+(k-1)$ terms, so we are done Case 2: $n=2a+1$ Then $\frac{2^k+2a}{2a+1}=(1+\frac{1}{2a+1})(\frac{2^{k-1}+a}{a+1})$ Again, done

Assume this is true up to $k=k'$, consider the $k+1^{\text{th}}$ case Case 1: $n=\text{even}=2a$. $$1 + \frac{2^{k'+1} - 1}{n} = \dfrac{2a + 2^{k' + 1} - 1}{2a} = \left(\frac{2a + 2^{k' + 1} - 1}{2a + 2^{k'+1} - 2}\right)\cdot \left(\frac{a+2^{k'} - 1}{a}\right)$$Which is equal to product of $k'+1$ 'such' numbers according to the hypothesis. Case 2: $n=\text{odd}=2a-1$. $$1 + \frac{2^{k'+1} - 1}{n} = \frac{2a + 2^{k' + 1} - 2}{2a-1} = \left(\frac{2a}{2a-1}\right)\cdot \left(\frac{a+2^{k'} - 1}{a}\right)$$Which is again equal to the product of $k' + 1$ 'such' numbers according to the hypothesis.

Let $m_0=n$. Maintain a counter $c=1$. Consider the infinite binary representation of $m_{c-1}$ (prepend $0$s). Start from the right side of the binary representation. Also, maintain a stack. If the bit is $1$, then set $m_c=m_{c-1}+2^a$ where the bit you are on is the $a$th bit. Move one bit to the left, and increment $c$ by one. If the bit is $0$, then add $a$ to the stack, where the bit you are on is the $a$th bit. Move one bit to the left. Once you have gone through $k$ bits, go through the stack in order, and for each element, set $m_c=m_{c-1}+2^a$ where $a$ is what is on the stack, pop off the stack, and increment $c$ by one. To see this works, note that the problem is equivalent to choosing $m_0=n$ and thereafter $m_i=m_{i-1}+d$ where $d|m_{i-1}$, and where we have $m_k=n+2^k-1$. The process above ensures this as whenever we add a bit to $m_c$, all the bits "behind" that bit are $0$.

We proceed with (strong) induction on $k$. The base case $k=1$ is trivial. Suppose $k = m-1$ holds, or in other words, $\frac{n+(2^{m-1}-1)}{n}$ be expressed as the product of $m-1$ factors of the given form. Then the expression for $m$ can be written as \[\frac{n+(2^m-1)}{n} = \begin{cases} \frac{n+1}{n} \cdot \frac{n + (2^m-1)}{n+1} & \text{for odd n} \\ \\ \frac{n + (2^m - 1)}{n + (2^m - 2)} \cdot \frac{n + (2^m - 2)}{n} & \text{for even n} \end{cases}\]Note the first factor is the case for $k=1$ and the second is the case for $k=m-1$, thus completing our induction.

Solved with xonk, xook also known as popop614, sixoneeight. What's induction? For any permutation $b_i$ of $(0, 1, 2, \dots k-1)$, we can write \[ \frac{n+2^k-1}{n} = \prod_{i = 1}^{k}\frac{a_i+2^{b_i}}{a_i} \]where the sequence $a_i$ is defined by $a_0 = n$, and $a_i = a_{i-1} + 2^{b_{i-1}}$. We claim that some permutation $b_i$ exists such that each term in the product can be simplified into the form \[ \frac{m+1}{m} = 1+\frac{1}{m} \]To prove this, consider the binary representation of $n+2^k-1 \equiv n-1 \pmod{2^{k-1}}$ (the last $k-1$ digits of $n+2^k-1$ in binary). We assign the $b_i$ in order by taking the indices of the zeroes in the binary from left to right, then taking the indices of the ones from right to left. For example, if the binary is $010110_2$, we would take the sequence to be $(0,3,5,4,2,1)$. We now show that this works by verifying that $2^{b_i}$ divides $a_i$ for each $i$. If $b_i$ is defined by one of the ones in the binary representation, then the binary representation of $a_i$ will have all of the ones to the right removed from the binary representation of $n+2^k-1$, so the binary representation will end in at least $2^{b_i}$ zeroes. Thus, it will be divisible by $b_i$. If $b_i$ is defined by one of the zeroes in the binary representation, then it will occur by subtracting some powers of $2$ that are larger than $2^{b_i}$ from the a binary number ending in $k-1$ zeroes, so the binary representation will still end in $2^{b_i}$ zeroes. Thus, it will be divisible by $b_i$. Combining these, we have proved that our construction works.

Here's a non-inductive solution (that's actually just equivalent to induction, but like whatever); this is probably how the problem was constructed. Consider writing $$\frac{n+2^k-1}n = \frac{a_1}{a_2} \cdot \frac{a_2}{a_3} \cdots \frac{a_k}{a_{k+1}}$$where $a_1 = n+ 2^k - 1< a_2 < \cdots < a_{k+1} = n$. Notice that $\frac{a_i}{a_{i+1}}$ is of the form $1+\frac 1{m_i}$ if and only if $d_i = a_i - a_{i+1}$ divides $a_{i+1}$. In particular, let $\{d_1, d_2, \dots, d_k\} = \{1, 2, 2^2, \dots, 2^{k-1}\}$. At every step, If $\nu_2(a_{i+1}) = r \leq k-1$, then set $d_i = 2^r$. At some point we must reach $\nu_2(a_{i+1}) = k-1$. If there are still $a_i$ left, sort the remaining unused elements in $\{2^i\}$ in decreasing order, and pick $d_j$ for $j \geq i$ in order of the remaining elements. Both selections for $d_i$ satisfy the condition, and as $d_1+d_2+\cdots+d_k = 2^{k-1} - 1$, the product on the RHS matches the LHS. Hence we have given a valid construction.

Use induction For $k=1$, $m_1=n$ works Assume that $1+\frac{2^k-1}{n}=(1+\frac{1}{m_1})(1+\frac{1}{m_2})...(1+\frac{1}{m_k})$ $\frac{1+\frac{2^k-1}{n}}{1+\frac{1}{m_k}}=(1+\frac{1}{m_1})(1+\frac{1}{m_2})...(1+\frac{1}{m_{k-1}})=1+\frac{2^{k-1}-1}{\text{positive integer}}$ $\frac{2^{k-1}-1}{\frac{1+\frac{2^k-1}{n}}{1+\frac{1}{m_k}}-1}=\text{positive integer}$ If $n$ is odd, then $m_k=n$ works. If $n$ is even, then $m_k=2^k+n-2$ works.

Notice how choosing $m=\frac{n+\ell}{2^j}$ for $j \le \nu_2(n+\ell)$ yields \[\frac{n+\ell}{n}\cdot \left(1+\frac{1}{\frac{n+\ell}{2^j}}\right) = \frac{n+\ell + 2^j}{n}\]Thus, we may find a sequence $m_1, m_2, \dots, m_k$ such that the sequence $\prod \left(1 + \frac{1}{m_i}\right)$ becomes \[\frac{n+2^{\nu_2(n)}}{n}, \frac{n+2^{\nu_2(n)} + 2^{\nu_2(n) + 1}}{n}, \dots, \frac{n+2^{\nu_2(n)} + 2^{\nu_2(n) + 1} + \dots + 2^{k-1}}{n},\]\[\frac{n+2^{\nu_2(n)-1} + 2^{\nu_2(n)} + 2^{\nu_2(n) + 1} + \dots + 2^{k-1}}{n}, \dots, \frac{n + 1 + \dots + 2^{k-1}}{n} = \frac{n+2^k-1}{n}\]

We will induct on $k$. Our base case is $k=1$, which works for any $n$ by taking $m_1=n$. Now for the inductive step, assume that for some $k=x$, for any $n$ there exist integers $m_1,\dots m_{x}$ such that \[1+\frac{2^x-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_x}\right).\]If we select $m_{x+1}=2n-1$, then $\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{x+1}}\right) = \left(1+\frac{2^x-1}{n}\right)\left(\frac{2n}{2n-1}\right)=\frac{2n}{2n-1}+\frac{2^{x+1}-2}{2n-1}=1+\frac{2^{x+1}-1}{2n-1}$. This gives us a valid construction for $x=k+1$ for any odd $n$. If we instead select $m_{k+1}=2n+2^{k+1}-1$, then $\left(1+\frac{2^x-1}{n}\right)\left(\frac{2n+2^{k+1}-1}{2n+2^{k+1}-2}\right)=\left(\frac{n+2^k-1}{n}\right)\left(\frac{2n+2^{k+1}-1}{2(n+2^{k}-1)}\right)=\frac{2n+2^{k+1}-1}{2n}=1+\frac{2^{k+1}-1}{2n}$, which gives a construction for even $n$. Thus, we have now shown that there exists a set for any $n$ when $k=x+1$, completing the induction.

amogus We proceed with induction on $k$. The base case, $k=1$ is trivial to see. Notice that if $n$ is even,$$1+\frac{2^k-1}{n} = \frac{n+2^k-1}{n} = \left(1+\frac{1}{n+2^k-2}\right)\left(\frac{n+2^k-2}{n}\right) = \left(1+\frac{1}{n+2^k-2}\right)\left(1+\frac{2^{k-1}-1}{n/2}\right).$$Applying the inductive hypothesis to the second term in the RHS yields the desired result. If $n$ is odd,$$1+\frac{2^k-1}{n} = \left(1+\frac{1}{n}\right)\left(\frac{n+2^k-1}{n+1}\right) = \left(1+\frac{1}{n}\right)\left(1+\frac{2^{k-1}-1}{(n+1)/2}\right).$$Applying the inductive hypothesis on the second term in the RHS yields the desired result. Thus done. $\blacksquare$

We induct on $n$. For the base case $n=1$, setting all $m_i$ to $1$ works. Now assume some $n-1$ works. If $n$ is odd, we have \[ 1 + \frac{2^k-1}{n} = \frac{2^k + (n-1)}{n} = \frac{n+1}{n} \cdot \frac{2^{k-1} + \frac{n-1}{2}}{\frac{n+1}{2}}. \]If $n$ is even, we have \[ 1 + \frac{2^k-1}{n} = \frac{2^k + (n-1)}{n} = \frac{2^k + (n-1)}{2^k + (n-2)} \cdot \frac{2^k + \frac{n-2}{2}}{\frac{n}{2}}. \]Therefore, the result holds for all $n$.

Ok, I just realized this problem was actually on IMO 2013. It's a really nice problem. Took me a while but it's a problem which can be motivated a lot by small cases. We prove the result by induction on $k$. We say a positive integer $n$ is $k-$good if the pair $(k,n)$ satisfies the given conditions. When $k=1$, simply let $m_1=n$ for all $n\in \mathbb{N}$. Thus, all positive integers are quite clearly $1-$good. Now, say that for some $k \ge 1$ we have that all positive integers $n$ are $k-$good. We attempt to show that all positive integers are also $(k+1)-$good. To do this, say $n$ is $k-$good. Then, consider the following. \[\left(1+\frac{2^k-1}{n} \right)\left( 1+\frac{1}{2n-1}\right) = \frac{2^k+n-1}{n} \cdot \frac{2n}{n+1} = \frac{2^{k+1+2n-2}}{2n-1} = 1+ \frac{2^{k+1}-1}{2n-1}\]Since $n$ is $k-$good, it thus follows that $2n-1$ is $(k+1)-$good. Further, we consider \[\left(1+\frac{2^k-1}{n} \right)\left( 1+\frac{1}{2^{k+1}+2n-2}\right) = \frac{2^{k}+n-1}{n} \cdot \frac{2^{k+1}+2n-1}{2^{k+1}+2n-2} = \frac{2^{k+1}+2n-1}{2n} = 1+\frac{2^{k+1}-1}{2n}\]which implies that $2n$ is also $(k+1)-$good. Thus, we can conclude that all positive integers are $(k+1)-$good, finishing the induction and solving the problem.

chat i lowkey forgot induction existed Consider a sequence $a_0<a_1<\dots<a_{k-1}<a_k$ such that $a_0=n$, $a_k=n+2^k-1$, and $(a_{i+1}-a_i) | a_i$ for $0\le i<k$. Then, $m_i=\frac{a_{i-1}}{a_i-a_{i-1}}$ for $1\le i\le k$ works since $1+\frac{1}{m_i}=\frac{a_i}{a_{i-1}}$, so we just gotta prove that such a sequence $a$ exists. We claim that letting $a_{i+1}=a_i+2^{\min(v_2(a_i), \lfloor\log_2(a_k-a_i)\rfloor)}$ for $0<i< k$ works. Clearly, the $(a_{i+1}-a_i) | a_i$ condition holds as $v_2(a_{i+1}-a_{i})=\min(v_2(a_i), \lfloor\log_2(a_k-a_i)\rfloor)\le v_2(a_i)$ and there are no primes over $2$ dividing $a_{i+1}-a_i$. ok so basically if a_0 is some binary num then we wanna add 1...1 (k ones) in binary to a_0 in k steps say like a_0 is 10110011 and we wanna add 1111 in 4 steps our recursion would basically add 1 then 100 then 1000 then 10 say like a_0 is 101001100 and we wanna add 111111 in 6 steps our recursion would basically add 100 then 10000 then 100000 then 1000 then 10 then 1 so the recursion from earlier basically adds the largest powers of 2 that divide a_0 until the amount we would add becomes too big (too big meaning the min thingy in the recurrence starts gives log_2 instead of v_2) (this part works cuz every time we add 2^v_2(a_i) to a_i, v_2(a_i) increases by at least 1) then we start adding the smaller powers of 2 we missed earlier in descending order (this works cuz using 2^floor(log_2(what we have left to add)) will give exactly the MSB) since every power of 2 in 2^(k-1)+...+2^0 gets added exactly once, there are k steps total, as desired.

It suffices to find $a_1,a_2,\dots,a_k$ such that \[2^{a_i}\mid n+2^{a_1}+2^{a_2}+\dots+2^{a_{i-1}}\]and $\{a_1,a_2,\dots,a_k\}=\{0,1,\dots,k-1\}$. This is because then we can construct \[m_i=\frac{n+2^{a_1}+2^{a_2}+\dots+2^{a_{i-1}}}{2^{a_i}}\]which clearly works. Let $x=\nu_2(n)$. If $x\le k-1$, we can have $\{a_i\}$ be $x,x+1,\dots,k-1,x-1,x-2,x-3,\dots,0$. Otherwise, we can have $\{a_i\}$ be $k-1,k-2,k-3,\dots,0$. $\blacksquare$

We proceed by strong induction on \(K\). For \(K = 1\), the result is obvious. Now suppose it holds for all integers less than \(K + 1\) and consider two cases. Case 1: \(n\) is even. \[ 1+\frac{2^{K+1}-1}{n}=1+\frac{2^K-1}{\left(\frac{n}{2}\right)}+\frac{1}{n}=\left(1+\frac{2^K-1}{\left(\frac{n}{2}\right)}\right)\left(1+\frac{1}{n+2(2^K-1)}\right) \]Case 2: \(n\) is odd. \[ 1 + \frac{2^{K+1} - 1}{n} = 1 + \frac{2^K - 1}{\left(\frac{n+1}{2}\right)} \cdot \frac{n+1}{n} + \frac{1}{n} = \left( 1 + \frac{2^K - 1}{\left(\frac{n+1}{2}\right)} \right) \left( 1 + \frac{1}{n} \right) \]

[Name of the Kendrick Lamar album that released in 2017],every solution uses induction,but I proved it using bezout theorem. $1+\frac{2^k-1}{n}=\frac{2^k+n-1}{n}$ Let $gcd(2^k+n-1;n)=d$. Divide both by $d$. $\frac{2^k+n-1}{d}=a\hspace{3mm}\frac{n}{d}=b\hspace{3mm}a>b$ $\frac{2^k+n-1}{n}=\frac{a}{b}$ Since $gcd(a;b)=1$, one can find $x;y\in\mathbb{Z}^+$ such that $ax-by=1\hspace{3mm}x<b\hspace{3mm}y<a\hspace{3mm}y>x\hspace{3mm}gcd(x;y)=1$ $\frac{a}{b}=\frac{ax}{by}\cdot\frac{y}{x}$ Repeat this again: $x_1;y_1\in\mathbb{Z}^+\hspace{3mm} yx_1-xy_1=1\hspace{3mm}x_1<x\hspace{3mm}y_1<y\hspace{3mm}y_1>x_1\hspace{3mm}gcd(x_1;y_1)=1$ $\frac{a}{b}=\frac{ax}{by}\cdot\frac{yx_1}{xy_1}\cdot\frac{y_1}{x_1}$ Repeat this again,and again,and again,and again,and again,and again,and again,and again,and again,you will get $\frac{a}{b}=\frac{ax}{by}\cdot\frac{yx_1}{xy_1}\cdot\frac{y_1x_2}{x_1y_2}\cdot ... \cdot\frac{y_i}{x_i}$ Claim:Eventually, $x_i$ will be equal to $1$. Proof:Since $x_j>x_{j+1}$ and $y_j>y_{j+1}$,and this can't be done forever,there will be a number $i$ which either $x_i$ or $y_i$ is equal to $1$. FTSOC take $y_i=1$. Then we can deduce the following $$y_{i-1}x_i-x_{i-1}=1$$SInce $y_{i-1}>x_{i-1}$, this holds if and only if $y_{i-1}=x_{i-1}+1$ and $x_i=1$ This means that in both cases($x_i=1$ and $y_i=1$), we can say that $x_i=1$ Plugging this gives us$$\frac{a}{b}=\frac{ax}{by}\cdot\frac{yx_1}{xy_1}\cdot\frac{y_1x_2}{x_1y_2}\cdot ... \cdot \frac{y_i}{1}=\frac{by+1}{by}\cdot\frac{xy_1+1}{xy_1}\cdot ... \cdot\frac{x_{i-1}y+1}{x_{i-1}y}\cdot(\frac{y_i}{y_i-1}\cdot\frac{y_i-1}{y_i-2}\cdot ...\cdot\frac21)=(1+\frac1{by})(1+\frac1{xy_1})...(1+\frac1{x_{i-1}y_i})(1+\frac1{y_i-1})(1+\frac1{y_i-2})...(1+\frac12)(1+\frac11)$$ Here is an example in case you didn't understand my solution $k=8$;$\hspace{3mm}n=7\Rightarrow$$$1+\frac{2^k-1}{n}=\frac{263}{8}=\frac{1841}{1840}\cdot\frac{230}{7}=\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{197}{6}=\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{985}{984}\frac{164}{5}=\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{985}{984}\frac{656}{655}\cdot\frac{131}{4}=\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{985}{984}\frac{656}{655}\cdot\frac{393}{392}\cdot\frac{98}{3}=\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{985}{984}\frac{656}{655}\cdot\frac{393}{392}\cdot\frac{98}{97}\cdot\frac{29}{1}$$$$\frac{1841}{1840}\cdot\frac{1380}{1379}\cdot\frac{985}{984}\frac{656}{655}\cdot\frac{393}{392}\cdot\frac{98}{97}\cdot\frac{29}{1}=(1+\frac1{1840})(1+\frac1{1379})(1+\frac1{984})(1+\frac1{655})(1+\frac1{392})(1+\frac1{97})\times(1+\frac1{28})(1+\frac1{27})(1+\frac1{26})....(1+\frac12)(1+\frac11)$$

We induct. For $k = 1,$ it is trivial(pick $m_1 = n$). Assume $k = N - 1$ works. We have two cases: If $n$ is odd, then $\left(1 + \frac1n\right)\left(1 + \frac{2^{N - 1} - 1}{\frac{n + 1}2}\right) = 1 + \frac{2^N - 1}{n}$ finishes the induction. If $n$ is even, then $\left(1 + \frac1{n + 2^{N} - 2}\right)\left(1 + \frac{2^{N - 1} - 1}{\frac n2}\right) = 1 + \frac{2^{N} - 1}{n}$ finishes the induction.