Dowód
Rozbijamy zbiór na podzbiorów: podzbiorów dwuelementowych postaci , gdzie oraz jeden podzbiór jednoelementowy . Dostajemy w ten sposób:
.
Wykorzystamy ten podział analizując własności –elementowych podzbiorów zbioru w dwóch przypadkach.
Przypadek 1
Najpierw zajmujemy się takimi –elementowymi podzbiorami zbioru , które nie są sumą czterech podzbiorów –elementowych uzyskanych z opisanego powyżej rozbicia.
Weźmy dowolny –elementowy podzbiór otrzymanego w ten sposób zbioru i rozpatrzmy dwa –elementowe zbiory: oraz .
Zauważmy, że sumy wszystkich elementów w rozpatrywanych zbiorach różnią się o . 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 , do których należy dokładnie jeden z elementów: lub (gdzie ) 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 –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 –elementowe podzbiory zbioru , których elementy możemy dobrać jedynie jako pary wybrane spośród par postaci , gdzie , tzn. spośród par .
Zauważmy, że:
ponieważ elementy do rozpatrywanych podzbiorów wybieramy jako pary spośród dostępnych, więc wszystkich podzbiorów –elementowych jest w tym przypadku ,
w każdym z rozpatrywanych w tym przypadku –elementowych podzbiorów zbioru są wyrazy parzyste i wyrazy nieparzyste, co oznacza, że każdy spośród tych podzbiorów –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 ,
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ż ,
w drugim przypadku nie ma podzbiorów o nieparzystej sumie wszystkich elementów, a podzbiorów o parzystej sumie wszystkich elementów jest .
Wobec tego liczbę wszystkich –elementowych podzbiorów zbioru o parzystej liczbie elementów możemy zapisać na dwa sposoby:
Oznacza to, że , skąd .
To spostrzeżenie kończy dowód.