How do I prove that $\sum_{i=3}^{n} \frac{i-2}{\binom{i}{2}} < \frac n 4$ for all natural $n > 3$?

Question

How do I prove:

$$\frac{3-2}{\binom 3 2} + \frac {4 - 2}{\binom 4 2} + \dots + \frac{n-2}{\binom n 2} < \frac n 4$$ I tested this sum on a variety of $n$ from $2$ to $100$ and they all seem to be less than $\frac n 4$, however I can't find a way to prove it.

Answer 1

Is that what you meant? $\sum_{i=3}^{n}\dfrac{i-2}{\displaystyle {\tbinom {i}{2}}.}$

This is equal to:$$\sum_{i=3}^{n}\dfrac{i-2}{\frac{i!}{2(i-2)!}}=\sum_{i=3}^{n}\dfrac{2(i-2)(i-2)!}{i!}=\sum_{i=3}^{n}\dfrac{2i-4}{i^2-i}$$

By using Integral Test:

$$\int_{3}^{\infty}\dfrac{2i-4}{i^2-i}dx=4 \ln(|i|)-2 \ln(|i-1|)+C$$ Let's just assume $C=0$,so,when $x>3$, $$4 \ln(|i|)-2 \ln(|i-1|)> \ln(i+1),\forall n\in[3,+\infty)$$ Since $\ln(i+1)$ is divergent, so we conclude that your series is also a divergent series, therefore the limit doesn't exist.

But you want to see the behavior of this summation,so:

We know that the Euler Constant $$\gamma=\lim_{n\to\infty}\left(\sum_{i=1}^n\dfrac{1}{i}-\ln(i)\right)=\lim_{n\to\infty}\left(\dfrac{3}{2}+\sum_{i=3}^n\dfrac{1}{i}-\ln(i)\right)$$$$\approx\dfrac{3}{2}+\dfrac{\lim_{n\to\infty}\sum_{i=3}^n\dfrac{2i-4}{i^2-i}}{\lim_{n\to\infty}\dfrac{2i-4}{i-1}}-\lim_{n\to\infty}\ln(i)$$ $$=\dfrac{3}{2}+\dfrac{1}{2}\lim_{n\to\infty}\sum_{i=3}^n\dfrac{2i-4}{i^2-i}-\lim_{n\to\infty}\ln(i)$$

So, we conclude that for any $N$: $$\sum_{i=3}^N\dfrac{i-2}{\displaystyle {\tbinom {i}{2}}}\approx2\gamma+2\ln(N)-3$$

I proved the more percise value for each sum. As n becomes larger, we can see that the $sum<\dfrac{n}{4}$ by investigate the relationship between these two functions.

Answer 2

For any $n \ge 8$, we have $$\dfrac{n-2}{\binom{n}{2}} = \dfrac{n-2}{\tfrac{n(n-1)}{2}} = \dfrac{2}{n} \cdot \dfrac{n-2}{n-1} \le \dfrac{2}{n} \le \dfrac{1}{4},$$

and thus, $$\sum_{k = 3}^{n-1}\dfrac{k-2}{\binom{k}{2}} < \dfrac{n-1}{4} \implies \sum_{k = 3}^{n}\dfrac{k-2}{\binom{k}{2}} < \dfrac{n}{4}.$$

So if you can prove that $\displaystyle\sum_{k = 3}^{n}\dfrac{k-2}{\binom{k}{2}} < \dfrac{n}{4}$ for $3 \le n \le 7$, then you can use induction to finish the proof.

Remark: Obviously, Kevin Song's analysis gives a much better asymptotic bound. But if you only need to prove the upper bound $\dfrac{n}{4}$, this might be simpler.

Answer 3

The inequality is equivalent to: $$\sum_{i=3}^{n} \frac{i-2}{i(i-1)} < \frac n 8$$ Using partial fractions, $\frac{i-2}{i(i-1)} = \frac 2 n - \frac 1 {n-1} = \frac 1 n - \left(\frac 1 {n-1} - \frac 1 n\right)$. The given sum becomes: $$\sum_{i=3}^{n} \frac 1 i - \sum_{i=3}^{n} \left(\frac 1{i-1} - \frac 1 i\right)$$ $$= H_n - \frac 3 2 - \left( \frac 1 2 - \frac 1 3 + \frac 1 3 - \frac 1 4 + \dots + \frac 1 {n-1} - \frac 1 n \right)$$ $$= H_{n} + \frac 1 n - 2$$ Where $H_n$ is the $n$th harmonic number. The problem then transforms to proving the following inequality: $$H_{n} + \frac 1 n - 2 < \frac{n}{8}, \qquad n \ge 3$$ which can be done by checking cases for $n < 8$ and induction for $n \ge 8$.

Answer 4

$\displaystyle \sum\limits_{i=3}^n (i-2){\binom i 2}^{-1} = 2\sum\limits_{i=3}^n \frac{i-2}{i(i-1)}=2H_{n-1}-4+\frac{4}{n}$

From the assumption $\displaystyle~2H_{n-1}-4+\frac{4}{n}<\frac{n}{4}~$ we conclude for $~n\to n+1~$ :

$\displaystyle 2H_n-4+\frac{4}{n+1}= \left(2H_{n-1}-4+\frac{4}{n}\right) + \left(\frac{4}{n+1}-\frac{2}{n}\right)< $

$\displaystyle < \frac{n}{4} + \frac{4}{n+1}-\frac{2}{n}<\frac{n+1}{4}$

The right side of the inequation chain means $~n^2-7n+8>0~$,

it's the same as $\displaystyle~n>4+\frac{n}{n-2}~$, which is true for $~n\geq 6~$ .

The cases $~n\in\{3,4,5\}~$ can be checked by hand.