1

I am working through Discrete Mathematics by Lovasz and Vesztergombi. In the chapter on graphs, they have the following:

$\binom{k}{2}$ + $\binom{n-k}{2}$ = $\binom{n-1}{2}$ - $\frac{(k-1)(n-k-1)}{2}$

I cannot see how the right-hand side is derived from the left-hand side. Is there a mistake in this equation?

dacastr
  • 149
  • 4
    If $n$ and $k$ are both even, I don't think that the RHS is an integer. – paw88789 Apr 16 '22 at 22:37
  • 2
    First of all, there are certain values for which there are not equality for example when $n$ and $k$ are both either even or odd, the RHS is not an integer. When $n$ is even and $k$ is odd or viceversa I've found some interesting values for example $n= 8$, $k=3$ or $n = 6$, $k=3$ because in the such cases the equation $ 2 \cdot
    [\binom{k}{2} + \binom{n - k}{2}] = \binom{n - 1}{2} - \frac{(k-1)(n-k-1)}{2} $ would be true, but with other values, the equality would totally crumble. It seems that the identetity isn't true.     – oscar AMVS Apr 17 '22 at 00:17
  • I have noticed a lot of errors in the text that I am using. From the comments above, it looks like there's a problem here too? – dacastr Apr 17 '22 at 00:22

1 Answers1

3

The lecture notes by Lovász and Vesztergombi are unedited because their content ended up in the textbook Discrete Mathematics: Elementary and Beyond by Lovász, Pelikán, and Vesztergombi. The textbook has the correct equation at the corresponding point in the text: $$\binom k2 + \binom{n-k}{2} = \binom{n-1}{2} - (k-1)(n-k-1).$$ The follow-up is the same in both versions: when $1 \le k \le n-1$, we have $\binom k2 + \binom{n-k}{2} \le \binom{n-1}{2}$, with equality only if $k=1$ or $k=n-1$.

The corrected equation can be justified in two ways.

First, we may simply expand and simplify both sides to $\frac{n^2}{2} - \frac n2 + k^2 - kn$.

Second, combinatorially, consider the set of unordered pairs chosen from $\{1,\dots,k\}$ together with the set of unordered pairs from $\{k,\dots,n-1\}$; there are $\binom k2 + \binom{n-k}{2}$ of these. Which of the $\binom{n-1}{2}$ unordered pairs from $\{1,2,\dots,n-1\}$ are not included? Precisely the $(k-1)(n-k-1)$ pairs where one element is from $\{1,\dots,k-1\}$ and the other is from $\{k+1,\dots,n-1\}$.

Misha Lavrov
  • 142,276