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


(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.

| cite | improve this answer | |

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

| cite | improve this answer | |

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$

| cite | improve this answer | |
  • $\begingroup$ 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)$. $\endgroup$ – River Li Aug 9 '19 at 6:11
  • $\begingroup$ Thanks for the feedback. I fixed it. $\endgroup$ – Mostafa Ayaz Aug 9 '19 at 13:13
  • $\begingroup$ 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}$. $\endgroup$ – River Li Aug 9 '19 at 14:01
  • $\begingroup$ Please check the last inequality $2H_{n+1}+H_nH_{n+1}\le n$. It is not true for $9\le n \le 20$. $\endgroup$ – River Li Aug 9 '19 at 14:24
  • $\begingroup$ Fixed it. Thanks again... $\endgroup$ – 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.

| cite | improve this answer | |

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.