How to use combinatorial proof instead of induction? [duplicate]

Question

Let k ≥ 1 be an integer and consider a sequence $n_1, n_2, . . . , n_k$ of positive integers. Use a combinatorial proof to show that

$\binom{n_1}{2}$ + $\binom{n_2}{2}$ +...+ $\binom{n_k}{2}$ $\le$ $\binom{n_1 + n_2 + ...+ n_k}{2}$

Answer 1

Consider the disjoint union
$$ G=K_{n_1}+\dotsb+K_{n_k}. $$ The LHS counts the number of edges in $G$. But $G$ is also a subgraph of $$ H=K_{n_1+\dotsb+n_k}. $$ The RHS counts the number of edges in $H$.

Answer 2

Urn approach

Lets say you got $k$ urns with $n_1,...,n_k$ marbles. The number

$${n_1\choose 2}+\cdots +{n_k\choose 2}$$

corresponds to the number of possible (unordered) pairs you can pick from all those marbles under the restriction that both marbles are from the same urn. The number

$${n_1+\cdots+n_k\choose 2}$$

corresponds to the number of pairs without this restriction. But it includes all the former cases, so it must be bigger.

---

Graph approach

Having $k$ complete graphs with nodes $n_1,...,n_k$ and forming their union will give you a graph $G$ with

$${n_1\choose 2}+\cdots +{n_k\choose 2}$$

edges. This graph is not connected, so certainly not complete. But add all the missing edges to make it complete and it now has

$${n_1+\cdots+n_k\choose 2}$$

edges. As we added edges to come here, this new number must be bigger.