# Interesting four-sum inequality $n^2 \left(\sum \limits_{k=1}^n \frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n \frac{k}{k+1}\right) \ge…$

Prove that for all $$n \in \mathbb{N}$$ the inequality $$\left(\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n (2k-1)\frac{k}{k+1}\right) \le n^2 \left(\sum \limits_{k=1}^n \frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n \frac{k}{k+1}\right)$$ holds.

My work.In fact, I want to solve another problem ( Prove $\left(\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n (2k-1)\frac{k}{k+1}\right) \le \frac{9}{8}n^4$ ) This another problem has already been solved, but I want to solve it by the method that the author of the problem intended. The fact is that in the original problem there was another inequality ( Prove the inequality $\sum \limits_{k=1}^n \frac{k+1}{k} \cdot \sum \limits_{k=1}^n \frac{k}{k+1} \le \frac{9}{8}n^2$ ). It seems to me that the inequality $$\sum \limits_{k=1}^n \frac{k+1}{k} \cdot \sum \limits_{k=1}^n \frac{k}{k+1} \le \frac{9}{8}n^2$$ is proved as the author of the problem wanted. I think that the author of the problem wanted us to prove inequality $$\left(\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n (2k-1)\frac{k}{k+1}\right) \le \frac{9}{8}n^4$$ on the basis of inequality $$\sum \limits_{k=1}^n \frac{k+1}{k} \cdot \sum \limits_{k=1}^n \frac{k}{k+1} \le \frac{9}{8}n^2$$. To this end, it suffices to prove the inequality $$\left(\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n (2k-1)\frac{k}{k+1}\right) \le n^2 \left(\sum \limits_{k=1}^n \frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n \frac{k}{k+1}\right)$$ I checked this inequality by numerical methods on a computer. This inequality holds for all $$n$$. Interestingly, if $$n \to \infty$$ then this inequality (in the limit) is an equality.

Perhaps this will help to solve the problem: let $$x_k=\frac{k+1}{k}$$. Then $$1 and inequality takes the form $$\left(\sum \limits_{k=1}^n (2k-1)x_k\right) \left( \sum \limits_{k=1}^n (2k-1)\frac{1}{x_k}\right) \le n^2 \left(\sum \limits_{k=1}^n x_k\right) \left( \sum \limits_{k=1}^n \frac{1}{x_k}\right)$$

(update 2019/08/09)

Let $$H_n = \sum_{k=1}^n \frac{1}{k}$$. Since $$\frac{1}{k} \le -\ln (1 - \frac{1}{k})$$ for $$k\ge 2$$, we have $$H_n - 1 \le -\sum_{k=2}^n \ln (1 - \frac{1}{k}) = \ln n$$ or $$H_n \le \ln n + 1$$.

Rewrite the inequality as $$(n^2+2n-H_n)\left(n^2 - 2n - 3 + \frac{3}{n+1} + 3H_n\right) \le n^2(n+ H_n)\left(n + 1 - \frac{1}{n+1} - H_n\right)$$ or $$-(n^2-3)H_n^2 - \frac{n(n^2+10n+11)}{n+1}H_n + \frac{n^2(n+2)(n+5)}{n+1}\ge 0. \qquad (1)$$

When $$1\le n\le 12$$, the inequality in (1) is verified directly.

When $$n\ge 13$$, rewrite (1) as $$-H_n^2 - \frac{n(n^2+10n+11)}{(n+1)(n^2-3)}H_n + \frac{n^2(n+2)(n+5)}{(n+1)(n^2-3)} \ge 0.$$ Since $$\frac{n(n^2+10n+11)}{(n+1)(n^2-3)} \le \frac{7}{4}$$ and $$\frac{n^2(n+2)(n+5)}{(n+1)(n^2-3)} \ge n+6$$, it suffices to prove that $$-H_n^2 - \frac{7}{4}H_n + n+6 \ge 0$$ or $$-\frac{7}{8} + \frac{1}{8}\sqrt{433+64n} \ge H_n.$$ Since $$H_n \le \ln n + 1$$, it suffices to prove that $$-\frac{7}{8} + \frac{1}{8}\sqrt{433+64n} \ge \ln n + 1$$. Let $$f(x) = -\frac{7}{8} + \frac{1}{8}\sqrt{433+64x} - \ln x - 1$$. We have $$f(13) > 0$$ and $$f'(x) = \frac{4}{\sqrt{433+64x}} - \frac{1}{x} > 0$$ for $$x\ge 13$$. Thus, $$f(n) \ge 0$$ for $$n\ge 13$$. This completes the proof.

Just a partial approach.

For the different sums, we have $$\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}=n^2+2 n-H_n$$ $$\sum \limits_{k=1}^n (2k-1)\frac k{k+1}=3 H_{n+1}+(n-3) (n+1)$$ $$\sum \limits_{k=1}^n \frac{k+1}{k}=H_n+n$$ $$\sum \limits_{k=1}^n \frac k{k+1}=n+1-H_{n+1}$$

So, we need to prove that $$f(n)=n^2 \left(H_n+n\right) \left(n+1-H_{n+1}\right)-\left(n (n+2)-H_n\right) \left(3 H_{n+1}+(n-3) (n+1)\right)\geq 0$$

At least, for large value of $$n$$, we have $$f(n)=n^3-n^2 \left(\log \left({n}\right)+\gamma -2\right) \left(\log \left({n}\right)+\gamma +3\right)+O(n)$$

For small values of $$n$$ $$f(n)=\frac{1}{12} \left(120-22 \pi ^2+\pi ^4\right) n^2+O\left(n^3\right)$$

We have$$\sum \limits_{k=1}^n (2k-1)\frac{k+1}{k}{=\sum \limits_{k=1}^n (2k-1)\left\{1+{1\over k}\right\}\\=\sum \limits_{k=1}^n 2k-1+\sum \limits_{k=1}^n {2k-1\over k}\\=n^2+2n-\sum_{k=1}^{n}{1\over k}\\=n^2+n-H_n}$$where $$H_n$$ is the famous Harmonic Number. Similarly$$\sum \limits_{k=1}^n (2k-1)\frac{k}{k+1}=n^2-2n-3-3H_{n+1}$$and$$n^2 \left(\sum \limits_{k=1}^n \frac{k+1}{k}\right) \left( \sum \limits_{k=1}^n \frac{k}{k+1}\right)=n^2(n+H_n)(n+1-H_{n+1})$$which by substituting, leave us with the following inequality:

$$(n^2+n-H_n)(n^2-2n-3-3H_{n+1})\le n^2(n+H_n)(n+1-H_{n+1})$$

after expanding the terms we obtain$$LHS\le RHS$$where$$LHS=n^4-4n^2+3n^2H_{n+1}+6nH_{n+1}-3n^2-6n-n^2H_{n}+2nH_{n}-3H_{n}H_{n+1}+3H_{n}\\RHS=n^4+n^3-n^3H_{n+1}+n^3H_{n}+n^2H_{n}-n^2H_{n}H_{n+1}$$by rearranging the terms we can rewrite $$-n^3-7n^2-6n+H_n(-n^3-2n^2+2n+3)+H_{n+1}(n^3+3n^2+6n)+H_nH_{n+1}(n^2-3)\le0$$

or equivalently

$$3H_n+H_{n+1}(n^2+8n)+H_nH_{n+1}(n^2-3)\le n^3+6n^2+5n+{3n\over n+1}$$

For $$n=1$$ and $$n=2$$, this inequality obviously holds and for $$n\ge 3$$ we divide the two sides of the inequality to $$n^2-3$$ therefore

$${3H_n\over n^2-3}+H_{n+1}{n^2+8n\over n^2-3}+H_nH_{n+1}\le n+6+{8\over n}+{21n+24\over n^2-3}$$

since for $$n\ge 3$$ we have $${3H_n\over n^2-3}<1$$ we only need to show that

$$H_{n+1}{n^2+8n\over n^2-3}+H_nH_{n+1}\le n+5+{8\over n}+{21n+24\over n^2-3}$$

Also this inequality holds for $$3\le n\le 8$$ by simple hand calculations and for $$n\ge 9$$:$${n^2+8n\over n^2-3}<2$$and we only show that

$$2H_{n+1}+H_nH_{n+1}\le n+5+{8\over n}$$

which is obvious since the RHS and LHs are convex and concave functions respectively and the inequality holds for $$n=9$$. Therefore the proof is complete $$\blacksquare$$

• Please check $\Big\{(n^2-3)H_n+n^3+3n^2+6n\Big\}\Big\{(n^2-3)H_{n+1}-n^3-2n^2+2n+3\Big\}\le(n^3+7n^2+6n)(n^2-3)$. I think that the right hand side (RHS) should be $(n^3+7n^2+6n)(n^2-3)+(n^3+3n^2+6n)(-n^3-2n^2+2n+3)$. – River Li Aug 9 '19 at 6:11
• Thanks for the feedback. I fixed it. – Mostafa Ayaz Aug 9 '19 at 13:13
• Nice. Please check the equations after “we divide the two sides of the inequality to therefore”. Note that $\frac{n^3+6n^2+5n+{3n\over n+1}}{n^2-3}\ne n+6+{8\over n}+{21n+24\over n^2-3}$. – River Li Aug 9 '19 at 14:01
• Please check the last inequality $2H_{n+1}+H_nH_{n+1}\le n$. It is not true for $9\le n \le 20$. – River Li Aug 9 '19 at 14:24
• Fixed it. Thanks again... – Mostafa Ayaz Aug 9 '19 at 16:58

Here's a probabilistic interpretation and solution to this problem, although the method itself may be negligibly faster than the existing answers. Let $$X$$ be a discrete random uniform random variable on $$\{1, \cdots, n\}$$. Then the problem can be rewritten as \begin{align*} \mathbb{E}\left[(2X-1)\frac{X+1}{X}\right]\mathbb{E}\left[(2X-1)\frac{X}{X+1}\right] = \mathbb{E}[2X-1]\mathbb{E}\left[\frac{X+1}{X}\right]\mathbb{E}[2X-1]\mathbb{E}\left[\frac{X}{X+1}\right] \end{align*} Rewritting the LHS in terms of $$\mathbb{E}[f(X)g(X)] = \text{Cov}(f(X), g(X)) + \mathbb{E}[f(X)]\mathbb{E}[g(X)]$$ and dividing by the RHS, \begin{align*} \left(1 + \frac{\text{Cov}\left(2X-1, \frac{X+1}{X}\right)}{n\mathbb{E}\left[\frac{X+1}{X}\right]}\right)\left(1 + \frac{\text{Cov}\left(2X-1, \frac{X}{X+1}\right)}{n\mathbb{E}\left[\frac{X}{X+1}\right]}\right) \le 1 \end{align*} Note that \begin{align*} \text{Cov}\left(2X-1, \frac{X+1}{X}\right) = 2\text{Cov}\left(X, \frac{X+1}{X}\right) = n+3 - (n+1)\mathbb{E}\left[\frac{X+1}{X}\right] \\ \text{Cov}\left(2X-1, \frac{X}{X+1}\right) = 2\text{Cov}\left(X+1, \frac{X}{X+1}\right) = n+1 - (n+3)\mathbb{E}\left[\frac{X}{X+1}\right] \end{align*} So we have to prove \begin{align*} \left(-\frac{1}{n} + \left(1 + \frac{3}{n}\right)\frac{1}{\mathbb{E}[\frac{X+1}{X}]}\right)\left(-\frac{3}{n} + \left(1 + \frac{1}{n}\right)\frac{1}{\mathbb{E}[\frac{X}{X+1}]}\right) \le 1 \end{align*} Let $$a_n = \mathbb{E}[\frac{X+1}{X}]$$ and $$b_n = \mathbb{E}[\frac{X}{X+1}]$$. Reorganizing, the statement we need to prove is \begin{align*} f(n) = (a_n b_n - 1)n^2 + (3b_n + a_n - 4)n + (a_n + 9b_n - 3a_nb_n - 3) \ge 0 \end{align*} It is straightforward to prove the bounds \begin{align*} 1 &< a_n = 1 + \frac{H_n}{n} \\ 1 + \frac{1}{n+1} - \frac{H_n}{n} &= b_n < 1 \\ a_n b_n &= 1 - \text{Cov}\left(\frac{X+1}{X}, \frac{X}{X+1}\right) \\ &= 1 + \text{Cov}\left(\frac{1}{X}, \frac{1}{X+1}\right) \\ &= 1 + \mathbb{E}\left[\frac{1}{X(X+1)}\right] - \mathbb{E}\left[\frac{1}{X}\right]\mathbb{E}\left[\frac{1}{X+1}\right] \\ &= 1 + \frac{1}{n}\left(1 - \frac{1}{n+1}\right) - \mathbb{E}\left[\frac{1}{X}\right]\mathbb{E}\left[\frac{1}{X+1}\right] \\ &\begin{cases} < 1 + \frac{1}{n} \\ > 1 + \frac{1}{n} - \frac{1}{n(n+1)} - \frac{H^2_n}{n^2} \end{cases} \end{align*} Therefore, \begin{align*} f(n) &> \left(\frac{1}{n} - \frac{1}{n(n+1)} - \frac{H^2_n}{n^2}\right)n^2 + \left(\frac{3}{n+1} - 2\frac{H_n}{n}\right)n + \left(4 + \frac{9}{n+1} - \frac{8H_n}{n} - \frac{3}{2n}\right) \\ &= n-\frac{n}{n+1} - H_n^2 + 3\frac{n}{n+1} - 2H_n + \left(4 + \frac{9}{n+1} - \frac{8H_n}{n} - \frac{3}{2n}\right) \\ &= n + \underbrace{2\frac{n}{n+1}}_{\ge 1.9 \text{ for } n \ge 20} - H_n^2 - 2H_n + \underbrace{\left(4 + \frac{9}{n+1} - \frac{8H_n}{n} - \frac{3}{2n}\right)}_{\ge 2.9 \text{ for } n \ge 20} \\ &> n + 4.8-2H_n - H_n^2 \end{align*} and the last expression is $$> 0$$ and increasing for $$n \ge 20$$. We can manually check the inequality is satisfied for $$1 \le n \le 19$$. With some better bounding, we can decrease the number of cases we need to check.