\(\displaystyle{ \sum_{i=0}^{n}{n \choose i}i=n2^{n-1}}\)
A wytłumaczenie następujące:
Teraz czego nie rozumiem.Aby to udowodnić, utwórzmy listę zawierającą kolejno elementy wszystkich podzbiorów zbioru n-elementowego \(\displaystyle{ X}\). Lista ta zawiera \(\displaystyle{ {n \choose i}}\) podzbiorów i-elementowych dla i = 0, ..., n, tak więc jej długość (tzn. liczba wystąpień elementów zbioru \(\displaystyle{ X}\)) wyraża się sumą po lewej stronie wzoru. Ponadto każdy element \(\displaystyle{ x \in X}\) występuje na liście \(\displaystyle{ n2^{n-1}}\) razy, gdyż taka jest liczba podzbiorów zawierających \(\displaystyle{ x}\) (jest ich tyle, ile wszystkich podzbiorów zbioru \(\displaystyle{ X \setminus \left\{x \right\} }}\)). Długość naszej listy jest więc równa \(\displaystyle{ n2^{n-1}}\). Dowód jest tym samym zakończony.
"Lista zawierająca kolejno elementy wszystkich podzbiorów". Czy to oznacza, że są to po prostu wszystkie elementu zbioru X? Czy może elementami tej listy są podzbiory zbioru X?
To, że lista ma \(\displaystyle{ {n \choose i}}\) podzbiorów to rozumiem i dlaczego je sumujemy chyba też kumam. Jednak nie dociera do mnie mnożenie każdego składnika przez i. Wg przytoczonej definicji jest to "liczba wystąpień elementów zbioru X". Ale weźmy przykład zbioru \(\displaystyle{ \{1, 2, 3, 4\}}\).
Czy ta lista ma wyglądać tak?:
\(\displaystyle{ \left\{\emptyset \right\},\left\{ 1\right\},\left\{ 2\right\},\left\{ 3\right\},\left\{ 4\right\},\left\{ 1, 2\right\}, \left\{1, 3\right\}\left\{ 1, 4\right\},\left\{ 2, 3\right\}\left\{ 2,4\right\},\left\{ 3,4\right\}}\)
Co w tym konkretnym przypadku będzie oznaczać i dla każdego wystąpienia? Mam rozumieć, że dla i = 2 liczba wystąpień, no właśnie - czego, ma się równać \(\displaystyle{ {n \choose 2}2}\)?
Na razie skupmy się na lewej części równania. Później, w razie potrzeby, przejdziemy do prawej.
