${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$

Question

In a proof, the author states that it is clear that:

Given $x\geq 1$ and $ n-x \geq 1$ and finally also $n\geq 2$

$${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$$

This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n \choose 2$.

I just don't see how it is smaller than $ {n-1\choose 2}$.

Answer 1

We need to prove that $$\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}\leq\frac{(n-1)(n-2)}{2}$$ or $$x^2-x+n^2-(2x+1)n+x^2+x\leq n^2-3n+2$$ or $$x^2-nx+n-1\leq0$$ or $$(x-1)(x+1-n)\leq0,$$ which is true for $1\leq x\leq n-1.$

Answer 2

\begin{align} {x\choose2} +{n-x\choose2} &=\frac{(x-1)x}2 +\frac{(n-x)(n-x-1)}2 \\ &=\tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \\ &=\tfrac12 (2x^2 -2nx+n^2-n) \\ &=\tfrac12 (2x(x-n) +n(n-1)) \end{align} Given $1 \leq x \leq n-1$ (and $x-n \leq -1$), then \begin{align} &\leq \tfrac12 (2(n-1)(-1) +n(n-1)) \\ &=\frac{(n-1)(n-2)}2 \color{blue}{\cdot \frac{(n-3)!}{(n-3)!}} \\ &=\frac{(n-1)!}{2!(n-3)!} \\ &={n-1\choose2}. \end{align}

Answer 3

$$ f(x)=\binom{x}{2}+\binom{n-x}{2}=\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}=\frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c $$ for some $a, b, c\in\mathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set $\{x:x\geq 1$ or $n-x\geq 1\}$, that is $x=1$ or $n-x=1\Leftrightarrow x=n-1$.

Finally we have $$ f(x)\leq f(1)=f(n-1)=\binom{n-1}{2} $$

Answer 4

Writing them out, ${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$ becomes $x(x-1)+(n-x)(n-x-1) \le (n-1)(n-2) $ or $x^2-x+n^2-n(x+x+1)+x^2-x \le n^2-3n+2 $ or $2x^2-2x \le n(2x+1-3)+2 $ or $2x^2-2x \le n(2x-2)+2 $ or $x^2-x \le n(x-1)+1 $ or $x(x-1) \le n(x-1)+1 $ or $(x-n)(x-1) \le 1 $ which is true for $x \ge 1$ and $x \le n-1$.

This is false for $x=0$ or $x=n$ where this algebra does not work.

Answer 5

Your method of splitting items in two groups actually gives an equality: $$ \binom{n}{2}=\binom{x}{2}+\binom{n-x}{2}+x(n-x) $$ (we can either choose both items from the first group, or both from the second, or one from each).

Now, \begin{align} \binom{n-1}{2}&=\binom{n}{2}-(n-1)\\ &=\binom{x}{2}+\binom{n-x}{2}+x(n-x)-(n-1) \end{align} and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 \leq x \leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.

Answer 6

Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x \le n-x$.

Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.

Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.