Is it possible to show ${k\choose 2} \ge \sum_{i } {x_i\choose 2} $ such that $\sum_i x_i =k$

Question

I want to know if this problem can be verified or rejected.

${k\choose 2} \ge \sum_i {x_i\choose 2 }$ such that $\sum_i x_i =k$ and $x_i, \;k\in \mathbb N.$

For example

$2+3=5$ and ${5 \choose 2} \ge {3\choose 2} + {2\choose 2} $

I tried to make a counterexample but I couldn't find anything, I wanted to prove it using the definition too, but I did not get anything. Is there a way to prove, or is there a counterexample?

Answer 1

Since $\dbinom{x}{2}=\frac{x(x-1)}{2}$, for $x\ge2$, your inequality can be written as $$\frac{k(k-1)}{2}\ge \sum_i \frac{x_i(x_i-1)}{2}=\sum_{i}\frac{x_i^2}{2}-\sum_i\frac{x_i}{2}=\sum_{i}\frac{x_i^2}{2}-\frac{k}{2}$$ since, by assumption $\sum_i x_i=k$. Also, assume that $x_i\ge 2$ for all $x_i$ (to avoid trivial complications). So, by rearranging terms, it suffices to show $$k^2\ge \sum_{i}x_i^2$$ or equivalently that $$\left(\sum_i x_i\right)^2\ge \sum_i x_i^2$$

Answer 2

The left-hand side of your inequality counts the distinct pairs from a size-$k$ set, while the right-hand side takes a partition into size-$x_i$ disjoint subsets, then counts the number of pairs that don't cut across partitions.

Answer 3

You have to prove $${k^2-k\over 2}\geq {x_1^2-x_1\over 2}+{x_2^2-x_2\over 2}+...+{x_k^2-x_k\over 2}$$

so $${(x_1+x_2+...x_k)^2}\geq x_1^2+x_2^2+...+x_k^2$$

which is obviously true since ali $x_i>0$