3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is true, the word "set" appears n the question's title. Why is this tagged [set-theory], though? $\endgroup$ – Asaf Karagila Oct 2 '13 at 9:24
  • 1
    $\begingroup$ 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$. $\endgroup$ – Greg Martin Oct 2 '13 at 19:04
2
$\begingroup$

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.

$\endgroup$

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.