# About the set of all the solutions $\mathbf x=(x_1,x_2,\cdots,x_m)$ to $\sum_{j=1}^m\frac{1}{x_j}=\frac1n$

Let $m,n$ be natural numbers, and let $S_{m,n}$ be the set of all the natural number solutions $\mathbf x=(x_1,x_2,\cdots,x_m)$ to the following equation : $$\sum_{j=1}^m\frac{1}{x_j}=\frac1n.$$ Also, letting $$k_{m,n}=\max_{\mathbf x\in S_{m,n}}\left(\max_{1\le j\le m}x_j\right)$$

then, here is my question.

Question : Is the following true for $m\ge 2$?

$$k_{m,n}=k_{m-1,n}\left(k_{m-1,n}+1\right).$$

Remark : This question has been asked previously on math.SE without receiving any answers:

Motivation : I've been asking the following question on MO.

What is the max of $n$ such that $\sum_{i=1}^n\frac{1}{a_i}=1$ where $2\le a_1\lt a_2\lt \cdots\lt a_n\le m$?

This got me interested in $S_{m,n}.$

In the following, I'm going to prove that $S_{m,n}$ is a finite set.

Proof : Let $S_{m,n}^{\gt}$ be the set of all solutions $\mathbf x=(x_1,x_2,\cdots,x_m)$ to the above equation such that $x_1\ge x_2\ge \cdots\ge x_m$. Since any solution $\mathbf x$ is one that we can get from the elements of $S_{m,n}^{\gt}$ by exchanging its coordinates, we get $$|S_{m,n}|\le m! |S_{m,n}^{\gt}|$$ where $|S|$ represents the number of the elements of a set $S$. Hence, in the following, let's prove that $S_{m,n}^{\gt}$ is a finite set for any natural number $n$ by induction on $m$.

The $m=1$ case is obvious. Then, let's suppose that $S_{m-1,n}^{\gt}$ is a finite set. Since $$\sum_{j=1}^{m-1}\frac1{x^j}=\frac1n-\frac1{x_m}=\frac{x_m-n}{nx_m},$$we get $$\sum_{j=1}^{m-1}=\frac{1}{(x_m-n)x_j}=\frac{1}{nx_m}\ \ \ \ \cdots(\star).$$ Now, $x_m$ satisfies the following inequality : $$n+1\le x_m\le mn\ \ \ \ \ \cdots(\star\star).$$ This is because if we deny $(\star\star)$, then $\mathbf x$ cannot be a solution of the equation. For a $x_m$ which satisfies $(\star\star)$, the number of solutions $\mathbf x^{\prime}=\left((x_m-n)x_1,(x_m-n)x_2,\cdots,(x_m-n)x_{m-1}\right)$ which satisfies $(\star)$ is finite by the supposition. Since the number of $x_m$ which satisfies $(\star\star)$ is finite as well, $|S_{m,n}^{\gt}|$ is finite. Now the proof is completed.

In the following, I'm going to represent $k_{3,n}$ by $n$.

First of all, note that $k_{2,n}=n(n+1)$. Next, we know that $$\left(n(n+1)(n(n+1)+1),n(n+1)+1,n+1\right)\in S_{3,n}^{\gt}.$$ Hence, by the definition of $k_{3,n}$, we get $$k_{3,n}\ge n(n+1)(n(n+1)+1).$$ Now, for any $\mathbf x=(x_1,x_2,x_3)$, we get $(rx_1,rx_2)\in S_{2,n(n+r)}^{\gt}$ by $(\star)$ where $r=x_3-n$ and $1\le r\le 2n$ by $(\star\star).$ Hence, by the definition of $k_{m,n}$, we get $$rx_1\le k_{2,n(n+r)}=n(n+r)(n(n+r)+1).$$ Hence, we get $$x_1\le \frac 1r n(n+r)(n(n+r)+1).$$ However, since $$n(n+1)(n(n+1)+1)-\frac 1r n(n+r)(n(n+r)+1)=\frac{1}{r}n^2(n^2-n+1)(r-1)\ge \frac 1r n^2(n^2-2n+1)(r-1)\ge 0,$$ we get $$x_1\le n(n+1)(n(n+1)+1).$$

After observing this question, I reached the above expectation. However I can neither prove that this is true nor find any counterexample. Can anyone help?

• It is true, the word "set" appears n the question's title. Why is this tagged [set-theory], though? – Asaf Karagila Oct 2 '13 at 9:24
• This is known to be true in the case $n=1$ - see oeis.org/A007018 for example ("Curtiss"). I bet the same techniques would establish it for other $n$. – Greg Martin Oct 2 '13 at 19:04

I've just been able to prove that my expectation is true.

In order to prove this, let us define the following sequence for $n\in\mathbb N$ : $$e_{1,n}=n+1,\ \ e_{m,n}=ne_{1,n}e_{2,n}\cdots e_{m-1,n}+1\ \ (m=2,3,4,\cdots).$$

Lemma 1 : \begin{align}\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}=\frac1n-\frac1{e_{m+1,n}-1}.\end{align}

Proof for lemma 1 : By the definition, we get $$(e_{m-1,n}-1)e_{m-1,n}=ne_{1,n}\cdots e_{m-2,n}\cdot e_{m-1,n}=e_{m,n}-1.$$ Since $$\frac1{e_{m-1,n}}=\frac1{e_{m-1,n}-1}-\frac1{e_{m,n}-1},$$ we get $$\sum_{i=2}^{m+1}\frac1{e_{i-1,n}}=\sum_{i=2}^{m+1}\left(\frac1{e_{i-1,n}-1}-\frac1{e_{i,n}-1}\right)=\frac1{e_{1,n}-1}-\frac1{e_{m+1,n}-1}=\frac1n-\frac1{e_{m+1,n}-1}.$$ Now the proof for lemma 1 is completed.

Lemma 2 : $$x_1y_1+x_2y_2+\cdots+x_my_m$$$$=(x_1-x_2)y_1+(x_2-x_3)(y_1+y_2)+\cdots+(x_{m-1}-x_m)(y_1+y_2+\cdots+y_{m-1})+x_m(y_1+y_2+\cdots+y_m)$$

Proof for lemma 2 : Let $S_i=y_1+y_2+\cdots+y_i\ (i\in\mathbb N)$.

Then, we get \begin{align}\sum_{i=1}^mx_iy_i & = x_1y_1+\sum_{i=2}^mx_i(S_i-S_{i-1}) \\ & = x_1y_1+\sum_{i=2}^mx_iS_i-\sum_{i=1}^{m-1}x_{i+1}S_i \\ & = x_1y_1+\sum_{i=2}^{m-1}(x_i-x_{i+1})S_i+x_mS_m-x_2S_1 \\ & = (x_1-x_2)y_1+\sum_{i=2}^{m-1}(x_i-x_{i+1})(y_1+\cdots+y_i)+x_m(y_1+\cdots+y_m). \end{align} Now the proof for lemma 2 is completed.

Lemma 3 : If $$\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\lt\frac1n$$ where $x_i\ (i=1,2,\cdots,m)$ are natural numbers, then \begin{align}\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\le\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}\qquad(\star)\end{align}

Proof for lemma 3 : Let us prove this by induction on $m$. We'll use the proof by contradiction. Also, by the symmetry about the letters, we may suppose that $x_1\le x_2\le \cdots\le x_m.$

If $m=1$, then since $x_1\gt n$ and $x_1\ge n+1=e_{1,n}$, we get $(\star).$

In the following, let's suppose $(\star)$ for any less than or equal to $m-1$.

Now, for $m$, let's suppose that there exists $(x_1,x_2,\cdots,x_m)$ which does not satisfy $(\star)$. (we'll use the proof by contradiction)

This means $(x_1,x_2,\cdots,x_m)$ satisfies \begin{align}\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}\lt \frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\lt \frac1n\qquad(\star\star)\end{align}

Hence, from the lemma 1, we know $$0\lt\frac1n-\left(\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\right)\lt\frac1n-\left(\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}\right)=\frac1{e_{m+1,n}-1}.$$

Here, we know, by reducing the fractions to a common denominator, $$\frac1n-\left(\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\right)\ (\gt 0)$$ can be represented as $$\frac{M}{nx_1x_2\cdots x_m}$$ where $M\in\mathbb N.$ By the definition of the sequence $\{e_{m,n}\}$, we get $$\frac{1}{nx_1x_2\cdots x_m}\le\frac{M}{nx_1x_2\cdots x_m}\lt\frac{1}{ne_{1,n}e_{2,n}\cdots e_{m,n}}.$$ Hence, we get \begin{align}x_1x_2\cdots x_m\gt e_{1,n}e_{2,n}\cdots e_{m,n}\qquad (1)\end{align} Here, letting $$P=\frac{x_1}{e_{1,n}}+\frac{x_2}{e_{2,n}}+\cdots+\frac{x_m}{e_{m,n}},$$ we get the following by AM–GM inequality and $(1)$ : \begin{align} P\ge m\sqrt[m]{\frac{x_1x_2\cdots x_m}{e_{1,n}e_{2,n}\cdots e_{m,n}}}\gt m\qquad (2)\end{align} On the other hand, we get the following by lemma 2 : \begin{align} P= & (x_1-x_2)\frac1{e_{1,n}}+(x_2-x_3)\left(\frac1{e_{1,n}}+\frac1{e_{2,n}}\right)+\cdots \\ & +(x_{m-1}-x_m)\left(\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac{1}{e_{m-1,n}}\right) \\ & +x_{m}\left(\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}\right) \end{align}

Here, noting that $x_i-x_{i+1}\le0\ (i=1,2,\cdots,m-1)$ and that the inductive assumption leads $$\frac1{x_1}\le\frac{1}{e_{1,n}},$$ $$\frac1{x_1}+\frac{1}{x_2}\le\frac{1}{e_{1,n}}+\frac1{e_{2,n}},$$ $$\vdots$$ $$\frac1{x_1}+\cdots+\frac{1}{x_{m-1}}\le\frac1{e_{1,n}}+\cdots+\frac1{e_{m-1,n}},$$ we get \begin{align} P\le & (x_1-x_2)\frac1{x_1}+(x_2-x_3)\left(\frac1{x_1}+\frac1{x_2}\right)+\cdots \\ & +(x_{m-1}-x_{m})\left(\frac1{x_1}+\cdots+\frac1{x_{m-1}}\right) \\ & +x_m\left(\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m,n}}\right).\end{align} Here, using $(\star\star)$, since we get \begin{align}P\lt & (x_1-x_2)\frac1{x_1}+(x_2-x_3)\left(\frac1{x_1}+\frac1{x_2}\right)+\cdots \\ & +(x_{m-1}-x_{m})\left(\frac1{x_1}+\cdots+\frac1{x_{m-1}}\right)\\ & +x_m\left(\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_m}\right),\end{align} we get $P\lt 1+1+\cdots+1=m$, which contradicts $(2)$. Hence, by the proof of contradiction, we now know that there does not exist $(x_1,x_2,\cdots,x_m)$ which satisfies $(\star\star)$. Hence, the above leads $(\star)$ for $m$. The equality is attained when $x_1=e_{1,n}, x_2=e_{2,n},\cdots, x_m=e_{m,n}.$ Now the proof for lemma 3 is completed.

Proof for my expectation : Let us prove that \begin{align}\max_{\mathbf x\in S_{m,n}}\left(\max_{1\le i\le m}x_i\right)=e_{m,n}-1\qquad (3)\end{align} If we can prove $(3)$, then $k_{m,n}=e_{m,n}-1$ leads $$k_{m,n}=(k_{m-1,n}+1)k_{m-1,n}$$ by the relational expression about $\{e_{m,n}\}.$

Let us prove $(3)$ by induction on $m$.

If $m=1$, then we leads $x_1=n=e_{1,n}-1.$

In the $m\ge 2$ case, we may suppose that $x_1\le x_2\le \cdots\le x_m$. Since $$\sum_{i=1}^{m-1}\frac1{x_i}\lt\frac1n,$$ we get by lemma 3 $$\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_{m-1}}\le\frac1{e_{1,n}}+\frac1{e_{2,n}}+\cdots+\frac1{e_{m-1,n}}.$$ Hence, we get by lemma 1 $$\frac1{x_m}=\frac1n-\sum_{i=1}^{m-1}\frac1{x_i}\ge\frac1n-\sum_{i=1}^{m-1}\frac1{e_{i,n}}=\frac1{e_{m,n}-1}.$$ Since $x_m\le e_{m,n}-1$, we get $$\max_{\mathbf x\in S_{m,n}}\left(\max_{1\le i\le m}x_i\right)\le e_{m,n}-1.$$ By the way, since we know by lemma 1 $$(e_{1,n},e_{2,n},\cdots,e_{m-1,n},e_{m,n}-1)\in S_{m,0},$$ the equality of the above inequality is obtained. Now the proof for $(3)$ is completed. Hence, we now know that the proof for my expectation is completed.