Can someone explain this to me? How can I approach this?

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

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

Consider the complete graph on $n_i$ vertices. How many edges does this graph have?

  • 2
    $\begingroup$ what has been tried ? $\endgroup$ – user451844 Oct 1 '17 at 0:58
  • 2
    $\begingroup$ Do you understand the hint? $\endgroup$ – N. F. Taussig Oct 1 '17 at 1:00

Elaborating on the hint, consider a graph formed by the disjoint union of complete graphs of sizes $n_1,n_2,n_3,\dots,n_k$

It will look something like this:

complete graphs

How many edges appear in the graph made from the disjoint union of complete graphs of size $n_1,n_2,\dots,n_k$?

If you are unable to immediately answer that, consider reading this related question.

What does the right side of the inequality count and how does that relate to our scenario here when considering graphs?

The LHS, $\binom{n_1}{2}+\binom{n_2}{2}+\dots+\binom{n_k}{2}$, is the number of edges in a graph on $n_1+n_2+\dots+n_k$ vertices made up of the disjoint union of complete graphs of sizes $n_1,n_2,\dots,n_k$ respectively. The RHS, $\binom{n_1+n_2+\dots+n_k}{2}$, is the largest number of edges in a graph on $n_1+n_2+\dots+n_k$ vertices and is in particular greater than or equal to the number of edges in the graph described in the first sentence. Q.E.D.

  • $\begingroup$ From what I understand now is : $ \binom{4}{2} + \binom{5}{2} + \binom{6}{2} = 30 \leq \binom{4+5+6}{2} = 105 $ I get it now! Thanks!! $\endgroup$ – moyass Oct 1 '17 at 2:28
  • $\begingroup$ @MohamadYassine I do not understand your comment and you appear to be using equals signs incorrectly. All four of the expressions $\binom{4}{2},5\binom{5}{2},10\binom{6}{2},15$ are all unequal. Read again what I wrote more closely. I did not ask you to find the number of edges in the picture, I asked you to think about the number of edges in the general graph described with otherwise unknown values for $n_1,n_2,\dots,n_k$. $\endgroup$ – JMoravitz Oct 1 '17 at 2:32
  • $\begingroup$ That or perhaps you meant for these to be separate equations. If so, then separate them. You still have mistakes then, $\binom{4}{2}=6\neq 5$. And just noticing that $\binom{4}{2}+\binom{5}{2}+\binom{6}{2}\leq \binom{4+5+6}{2}$ is not by itself the proof. That is just one of infinitely many possible specific cases. $\endgroup$ – JMoravitz Oct 1 '17 at 2:34
  • $\begingroup$ Okay then if I say the LHS is the sum of edges (in terms of graphs) for disjoint graphs and the RHS is the sum of edges for the biggest possible graphs. $\endgroup$ – moyass Oct 1 '17 at 2:41

This should hopefully mostly be a combinatorial proof: the $LHS$ of the equality is the same as (let's call it $S_{left})$:

$$\frac{n_1!}{2!(n_1-2)!} + \frac{n_2!}{2!(n_2-2)!} + \frac{n_3!}{2!(n_3-2)!} + \ ... \ + \frac{n_k!}{2!(n_k-2)!} = S_{left}$$ $$\frac{n_1!}{(n_1-2)!} + \frac{n_2!}{(n_2-2)!} + \frac{n_3!}{(n_3-2)!} + \ ... \ + \frac{n_k!}{(n_k-2)!} = 2S_{left} \tag{1}$$

We know that $\frac{n!}{(n-k)!} = n(n-1)(n-2)...(n-(k-1))$. E.g. $\frac{10!}{(10-2)!} = \frac{10(9)(8)...(2)(1)}{8(7)(6)...(2)(1)}$ will just become $10(9)$ because everything else cancels out. Use this fact for $(1)$:

$$n_1(n_1-1) + n_2(n_2-1) + n_3(n_3-1) + \ ... \ + n_k(n_k-1) = 2S_{left} $$ $$n_1^2 + n_2^2 + n_3^2 + \ ... \ + n_k^2 - (n_1 + n_2 + n_3 + \ ... \ + n_k) = 2S_{left} \tag{2}$$

Now let's move on to the $RHS$, let's call it $S_{right}$:

$$\frac{(n_1 + n_2 + n_3 + \ ... \ + n_k)!}{2!(n_1 + n_2 + n_3 + \ ... \ + n_k - 2)!} = S_{right}$$ $$\frac{(n_1 + n_2 + n_3 + \ ... \ + n_k)!}{(n_1 + n_2 + n_3 + \ ... \ + n_k - 2)!} = 2S_{right} \tag{3}$$

What is $n_1 + n_2 + n_3 + \ ... \ + n_k$? Well it's just a sum of an arithmetic series so it's equal to $\frac{k(n_1+n_k)}{2}$, use that for $(3)$ (we will use it later for $(2)$ as well):

$$\frac{\Big(\frac{k(n_1+n_k)}{2}\Big)!}{\Big(\frac{k(n_1+n_k)}{2} - 2\Big)!} = 2S_{right} \tag{4} $$

Using the same logic here as we did for terms in $(1)$, we can see that $(4)$ is just the sum for $k$ terms times the sum for $k-1$ terms (in the same way that a term in $(1)$ was $n(n-1)$). Change $(4)$ to:

$$\Big(\frac{k(n_1+n_k)}{2}\Big)^2 - \frac{k(n_1+n_k)}{2} = 2S_{right} \tag{5}$$

Use the definition of an arithmetic series on $(2)$ and then compare to $(5)$:

$$n_1^2 + n_2^2 + n_3^2 + \ ... \ + n_k^2 - \frac{k(n_1+n_k)}{2} = 2S_{left} \tag{6} $$ $$\Big(\frac{k(n_1+n_k)}{2}\Big)^2 - \frac{k(n_1+n_k)}{2} = 2S_{right} \tag{7}$$

Use your equality to set $$2S_{left} \le 2S_{right} \tag{8}$$ $S_{left} \le S_{right}$ is the same as $(8)$ so it's valid for our comparison. Then use $(6)$ and $(7)$ in the equality: $$ n_1^2 + n_2^2 + n_3^2 + \ ... \ + n_k^2 - \frac{k(n_1+n_k)}{2}\le \Big(\frac{k(n_1+n_k)}{2}\Big)^2 - \frac{k(n_1+n_k)}{2}$$

$$ n_1^2 + n_2^2 + n_3^2 + \ ... \ + n_k^2\le \Big(\frac{k(n_1+n_k)}{2}\Big)^2 $$

Note that $\Big(\frac{k(n_1+n_k)}{2}\Big)^2 = \sum_{i=1}^{k} n_i^3$, and $n_1^2 + n_2^2 + n_3^2 + \ ... \ + n_k^2 = \sum_{i=1}^{k} n_i^2$.

So obviously for $k \ge 1$ and positive $n_i$ (for negative $n_i$ this is not true because the cubic series will become negative):

$$ \sum_{i=1}^{k} n_i^2 \le \sum_{i=1}^{k} n_i^3$$

Which completes the proof for the first question.

Regarding the second question: in a graph with $n$ vertices, the first vertex has $n-1$ vertices to draw edges to, the second vertex has $n-2$ vertices to draw edges to etc. Maybe you can figure it out by this? Alternatively, how many combinations of $2$ vertices connected together can a graph with $n$ vertices have? Where order doesn't matter because $v_1 \leftrightarrow v_2$ is the same as $v_2 \leftrightarrow v_1$.

  • $\begingroup$ This is an incredibly long proof to a problem which has a simple one or two sentence proof. It also appeals quite heavily on algebraic manipulation which is usually not the intended route when someone asks for a "combinatorial proof." $\endgroup$ – JMoravitz Oct 1 '17 at 2:09
  • $\begingroup$ Yes my sir, you are correct; I am probably bored so that's why I did this sort of proof instead, in my opinion it's much more clearer with simple algebraic manipulations instead of involving too many abstract ideas.. $\endgroup$ – Sam Anderson Oct 1 '17 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.