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<x_k \le 2$ 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)$$
 A: (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.
A: 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)$$
A: 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$
A: 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.
