5

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?

V.S.e.H.
  • 2,724
  • Holds for $n=1,2$ as well. – Thomas Andrews May 09 '21 at 22:37
  • @ThomasAndrews Sorry, not for 2, see https://www.wolframalpha.com/input/?i=1%2F4+n+%283+-+3+n+%2B+2+n+log%28n%29%29+%3E%3D+n%5E2log%28n%29%2F8 – V.S.e.H. May 09 '21 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.$ – Thomas Andrews May 09 '21 at 22:39
  • 1
    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. – Thomas Andrews May 09 '21 at 22:41
  • @ThomasAndrews yes, when you compare the sum directly, it's true. – V.S.e.H. May 09 '21 at 22:47
  • My original answer was wrong, because I forgot the $3$ in the minus term. To get a clearer proof, I had to use the stronger inequality from the trapezoids. – Thomas Andrews May 10 '21 at 01:01

2 Answers2

3

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

Thomas Andrews
  • 177,126
  • 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? – V.S.e.H. May 09 '21 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. – Thomas Andrews May 09 '21 at 23:26
  • We are just using $H_1>\frac{1}4+\log 2$ and $H_n-H_1>\log(n/2)$ – Thomas Andrews May 09 '21 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.$ – Thomas Andrews May 09 '21 at 23:50
  • Whoops, the comment starting “We are just using..” should read $H_{n-1}-H_1>\log(n/2).$ – Thomas Andrews May 09 '21 at 23:54
  • Very nice, thanks a lot of the answer! – V.S.e.H. May 10 '21 at 09:25
  • 1
    The trapezoid estimate is also called Hermine-Hadamard inequality, no? – V.S.e.H. May 10 '21 at 10:13
  • @V.S.e.H. Thanks for the name! Added it (and a link) to the answer. – Thomas Andrews May 11 '21 at 14:18
2

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.

heropup
  • 135,869