Udowodnij, że każdy zbiór skończony ma tyle samo podzbiorów o parzystej liczbie elementów,
co o nie parzystej liczbie elementów.
Zadanie na udowodnienie zbiorów
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
Icanseepeace
- Stały bywalec
- Posty: 437
- Rejestracja: 03 kwie 2021, 21:36
- Podziękowania: 6 razy
- Otrzymane podziękowania: 253 razy
- Płeć:
Re: Zadanie na udowodnienie zbiorów
Suma podzbiorów o liczbie parzystej: \(\sum\limits_{k \ parzyste}^n \binom{n}{k} \)
Suma podzbiorów o liczbie nieparzystej: \(\sum\limits_{k \ nieparzyste}^n \binom{n}{k} \)
Wystarczy pokazać, że ich różnica jest równa 0:
\( \sum\limits_{k \ parzyste}^n \binom{n}{k} - \sum\limits_{k \ nieparzyste}^n \binom{n}{k} =
\sum\limits_{k = 0}^n (-1)^k\binom{n}{k} \stackrel{WN}{=} 0\)
Edit
Każdy skończony i niepusty!!
Suma podzbiorów o liczbie nieparzystej: \(\sum\limits_{k \ nieparzyste}^n \binom{n}{k} \)
Wystarczy pokazać, że ich różnica jest równa 0:
\( \sum\limits_{k \ parzyste}^n \binom{n}{k} - \sum\limits_{k \ nieparzyste}^n \binom{n}{k} =
\sum\limits_{k = 0}^n (-1)^k\binom{n}{k} \stackrel{WN}{=} 0\)
Edit
Każdy skończony i niepusty!!