Prove $\sum_{k=1}^{n-1}\frac{(n-k)^2}{2k} \geq \frac{n^2\log(n)}{8}$ As the title says, prove $$\sum_{k=1}^{n-1}\frac{(n-k)^2}{2k} \geq \frac{n^2\log(n)}{8},$$ for $n>1$. This inequality is from Erdős, "Problems and results on the theory of interpolation". I, Lemma 3.
My attempt: since $H_{n-1}=\sum_{k=1}^{n-1}\frac{1}{k} > \int_{1}^n\frac{1}{t}dt = \log(n),$ we then have
$$
\sum_{k=1}^{n-1}\frac{(n-k)^2}{2k} = \sum_{k=1}^{n-1}\frac{n^2 - 2kn + k^2}{2k} = \frac{n^2}{2}H_{n-1} - n(n-1) + \frac{n(n-1)}{4} > \frac{n^2\log(n)}{2} - \frac{3n(n-1)}{4}.
$$
Am I missing something here?
 A: Using the stronger inequality, for $n>1$ that:
$$H_{n-1}>\frac{1}{2}\left(1-\frac1n\right) +\log n$$
(see proof below) we get:
$$\frac{n^2H_{n-1}}{2}-\frac{3n(n-1)}4>\frac{n^2\log n}2 +\frac{n(n-1)}4-\frac{3n(n-1)}4\\
=\frac{n^2\log n}2-\frac{n(n-1)}2$$
So you need:
$$\frac{3n^2\log n}8>\frac{n(n-1)}2$$
or $$\frac{\log n^3}4> 1-1/n.$$
But for $n\geq 4,$ we have $\log n^3>4$ and $1-1/n<1.$ For $n=2,$ you have $\log 2^3>2$ so $$\frac{\log 2^3}{4}>\frac12=1-\frac 12$$
For $n=3,$ you need $\log 27 >3> \frac 83.$
If you don’t want to use a calculator to show $\log(4^3)>4,$ use the estimate:
$$3\log(4)/4 >3(1/2+1/3+1/4)/4=\frac{13}{16}>1-1/4.$$
For $n= 5,$ $$3\log(n)/4>3(1/2+1/3+1/4+1/5)/4=\frac{77}{80}>\frac45.$$
It’s easier to prove $e^2<8,$ rather than $\log(8)>2.$
Just show $$e^2<1+2+\frac{2^2}2+\frac{2^3}6\cdot\frac1{1-2/4}=\frac{23}3<8.$$


Theorem: $$H_{n-1} >\frac12\left(1-\frac 1n\right)+\log n$$

Proof: The key is that $1/x$ is convex. For any convex function, $f$, the trapezoid estimate of the integral overestimates the integral (part of the Hermite-Hadamard inequality):
$$\frac{b-a}2(f(a)+f(b))\geq \int_a^b f(x)\,dx$$ with equality only if $f$ is linear on $[a,b].$ so for $f(x)=1/x,$ this means: $$\frac12\left(\frac 1{k-1}+\frac1k\right)>\int_{k-1}^k \frac{dx}x$$
That can be rewritten:
$$\frac{1}{k-1}>\frac12\left(\frac1{k-1}-\frac1k\right)+\int_{k-1}^k \frac{dx}x$$
Summing $k=2,\dots,n$, you get: $$H_{n-1}>\frac12\left(1-\frac1n\right) +\log n$$
A: Your bound is much tighter for sufficiently large $n$.  Define $$f(n) = \frac{n^2 \log n}{8}, \\ g(n) = \frac{n^2 \log n}{2} - \frac{3n(n-1)}{4}.$$  Then the ratio $$\frac{g(n)}{f(n)} = 4 - \frac{6(n-1)}{n \log n}.$$  For $n \ge 5$, $\log n > 1.6$, hence $\frac{6(n-1)}{n \log n} < 3$, thus $g > f$.
In the case where $n \le 4$, we would directly compare the bound $\frac{n^2 \log n}{8}$ with the sum.
