2

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).$$

Motivation : I've been asking the following question on MSE and 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 99$?

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?

Update : I crossposted to MO.

mathlove
  • 139,939
  • the terms $x_i$ are supposed to be naturals, right? – Integral Sep 28 '13 at 17:07
  • @Integral: Yes. Thanks. I edited it. – mathlove Sep 28 '13 at 17:10
  • This seems like your second cross-post on this topic, you may want to read http://meta.math.stackexchange.com/questions/10265/cross-posting-or-flag-for-migration – Asaf Karagila Oct 02 '13 at 09:26
  • @AsafKaragila: I think this is the first time to crosspost this question. What do you mean "second" and "topic"? You are pointing and counting the question "What is the max of $n\cdots$"? I think these are different questions though these are relevant. Also, I don't know why you showed the page. – mathlove Oct 02 '13 at 11:02
  • This topic, not this question. Your previous question, which is obviously related to this one, was also cross-posted. I linked to the meta thread because now you don't have to cross-post, and you can simply request that the question is migrated to MathOverflow; moreover only three-four days is usually an insufficient time between posting on one site and another. Patience is a key issue here. – Asaf Karagila Oct 02 '13 at 11:17
  • Thanks. I totally agreed with "Patience is a key issue here." However, I still have something unclear. Then, what do you think was the very problem in this situation? Crossposting two similar questions? Not waiting enough? I wrote this just to clarify because what I learned from this situation is only to be more patient. In other words, I'm not sure about requesting(I didn't know anything about requesting system, don't know how to, when to, where to). – mathlove Oct 02 '13 at 14:47

1 Answers1

1

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.

mathlove
  • 139,939