# 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?

• Holds for $n=1,2$ as well. May 9, 2021 at 22:37
• @ThomasAndrews Sorry, not for 2, see wolframalpha.com/input/… May 9, 2021 at 22:39
• Where you have $\log n$ you can put $\log(n-1).$ Don’t see that solving your problem. $$\frac{n^2\log(n-1)}{2}-\frac{3n^2}{4}=\frac{n^2(2\log(n-1)-3)} 4$$ so you need $$2\log (n-1)-3\geq \frac {\log n}{2}$$ or $4\log (n-1)-\log n\geq 6.$Are you sure this is true for all $n?$ So at least it is down to checking roughly 400 values of $n.$ May 9, 2021 at 22:39
• Yes for $n=2.$ The left side is $\frac12$ the right side is $\frac{4\log 2}8=\frac{\log 2}2<\frac12.$ Our estimates might fail, but Erdos didn’t. May 9, 2021 at 22:41
• @ThomasAndrews yes, when you compare the sum directly, it's true. May 9, 2021 at 22:47

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

• Sorry, I don't understand how you derive $H_{n-1}> \frac{1}{4} + \log(n)$ using convexity. Can you elaborate a bit further on that part? May 9, 2021 at 23:19
• The convexity means the curve is less than the trapezoidal estimate of $\int_1^2dx/x$ and the trapezoidal estimate is $\frac{1}{2}(1+1/2)=\frac34.$ So $\log 2<\frac{3}4$ then add $1/4$ to both sides. Basically, the line segment $(1,1)$ to $(2,1/2)$ is above $1/x$ due to convexity. May 9, 2021 at 23:26
• We are just using $H_1>\frac{1}4+\log 2$ and $H_n-H_1>\log(n/2)$ May 9, 2021 at 23:35
• You actually get a stronger result $$H_{n-1}>\log n +\frac12\left(1-\frac1n\right)$$ by doing the trapezoid trick on each $\int_{n-1}^n dx/x.$ But we only needed $\frac14.$ May 9, 2021 at 23:50
• The trapezoid estimate is also called Hermine-Hadamard inequality, no? May 10, 2021 at 10:13

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.

• Yes, makes sense. Was expecting that there might be a "nicer" bound. May 9, 2021 at 22:52