Dowód

Rozbijamy zbiór $A$ na $n+1$ podzbiorów: $n$ podzbiorów dwuelementowych postaci $\left\{2k-1,2k\right\}$, gdzie $k=1,2,\dots ,n$ oraz jeden podzbiór jednoelementowy $\left\{2n+1\right\}$. Dostajemy w ten sposób:
$A=\left\{1,2\right\}\cup \left\{3,4\right\}\cup \dots \cup \left\{2n-1,2n\right\}\cup \left\{2n+1\right\}$.

Wykorzystamy ten podział analizując własności $8$–elementowych podzbiorów zbioru $A$ w dwóch przypadkach.

Przypadek 1
Najpierw zajmujemy się takimi $8$–elementowymi podzbiorami zbioru $A$, które nie są sumą czterech podzbiorów $2$–elementowych uzyskanych z opisanego powyżej rozbicia.

Weźmy dowolny $7$–elementowy podzbiór $B$ otrzymanego w ten sposób zbioru $\left\{1,2,\dots ,2k – 2, 2k + 1,\dots ,2n+1\right\}$ i rozpatrzmy dwa $8$–elementowe zbiory: $B\cup \left\{2k–1\right\}$ oraz $B\cup \left\{2k\right\}$.
Zauważmy, że sumy wszystkich elementów w rozpatrywanych zbiorach różnią się o $1$. Zatem w jednym z tych zbiorów suma wszystkich elementów jest parzysta, a w drugim suma wszystkich elementów jest nieparzysta. Oznacza to, że wszystkie ośmioelementowe podzbiory zbioru $A$, do których należy dokładnie jeden z elementów: $2k–1$ lub $2k$ (gdzie $k=1,2,\dots ,n$) możemy podzielić na pary tak, aby w każdej parze w jednym podzbiorze suma wszystkich elementów była parzysta, a w drugim – suma wszystkich elementów była nieparzysta.

W ten sposób pokazaliśmy, że wszystkie $8$–elementowe podzbiory rozpatrywane w tym przypadku spełniają następującą zależność:
podzbiorów o parzystej sumie wszystkich elementów jest tyle samo, co podzbiorów o nieparzystej sumie wszystkich elementów.

Przypadek 2

Pozostały nam do rozpatrzenia te $8$–elementowe podzbiory zbioru $A$, których elementy możemy dobrać jedynie jako $4$ pary wybrane spośród $n$ par postaci $\left\{2k-1,2k\right\}$, gdzie $k=1,2,3,\dots ,n$, tzn. spośród par $\left\{1,2\right\},\left\{3,4\right\},\dots ,\left\{2n-1,2n\right\}$.

Zauważmy, że:

• ponieważ elementy do rozpatrywanych podzbiorów wybieramy jako $4$ pary spośród $n$ dostępnych, więc wszystkich podzbiorów $8$–elementowych jest w tym przypadku $\left(\begin{array}{c}n\\ 4\end{array}\right)$,

• w każdym z rozpatrywanych w tym przypadku $8$–elementowych podzbiorów zbioru $A$ są $4$ wyrazy parzyste i $4$ wyrazy nieparzyste, co oznacza, że każdy spośród tych podzbiorów $8$–elementowych ma parzystą sumę wszystkich swoich elementów.

Podsumowując wnioski uzyskane w obu przypadkach, stwierdzamy, że:

• podzbiory o nieparzystej sumie wszystkich elementów występują wyłącznie w pierwszym przypadku – zgodnie z oznaczeniami przyjętymi w treści zadania jest ich $y$,

• w pierwszym przypadku podzbiorów o parzystej sumie wszystkich elementów jest tyle samo, co podzbiorów o nieparzystej sumie wszystkich elementów, a więc również $y$,

• w drugim przypadku nie ma podzbiorów o nieparzystej sumie wszystkich elementów, a podzbiorów o parzystej sumie wszystkich elementów jest $\left(\begin{array}{c}n\\ 4\end{array}\right)$.

Wobec tego liczbę wszystkich $8$–elementowych podzbiorów zbioru $A$ o parzystej liczbie elementów możemy zapisać na dwa sposoby:

• ich liczbę oznaczyliśmy przez $x$,

• sumując ich liczbę w obu rozpatrywanych przypadkach dostajemy $y+\left(\begin{array}{c}n\\ 4\end{array}\right)$.

Oznacza to, że $x=y+\left(\begin{array}{c}n\\ 4\end{array}\right)$, skąd $x-y=\left(\begin{array}{c}n\\ 4\end{array}\right)$.
To spostrzeżenie kończy dowód.