Udowodnij, że suma dwumianów jest równa...

[budinho]

Udowodnij : \(\displaystyle{ \frac{ {n \choose 1} + 2 {n \choose 2} + 3 {n \choose 3} + ... + n {n \choose n} }{n} = 2 ^{n-1}}\)

Proszę o pomoc. Indukcyjnie mi nie wychodzi. A zadanie trzeba udowodnić sposobem nieindukcyjnym. Z góry dzięki:D

[Sylwek]

\(\displaystyle{ S=0 \cdot \binom{n}{0} + 1 \cdot \binom{n}{1}+\ldots+n \cdot \binom{n}{n} \\ S=0 \cdot \binom{n}{n} + 1 \cdot \binom{n}{n-1} + \ldots + n \cdot \binom {n}{0}}\)

Dodajemy stronami:
\(\displaystyle{ 2S=(0+n)\binom{n}{0} + (1+n-1) \binom {n}{1} + \ldots + (n+0) \binom{n}{n} = \\ = n \cdot (\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n})=n \cdot (1+1)^n = n \cdot 2^n}\)

Dzieląc stronami przez 2 dostajesz tezę.

[snm]

Na historyjkę
chcemy udowodnić, że \(\displaystyle{ {n \choose 1} + 2{n \choose 2} + ... + n {n \choose n} = n*2^{n-1}}\)

Weźmy klasę n-osobową. Pokażę, że suma ta jest równa ilości możliwych do utworzenia drużyn drużyn z dokładnie jednym liderem.
Dla każdego \(\displaystyle{ k}\) liczba możliwych do utworzenia drużyn k-osobowych wynosi \(\displaystyle{ {n \choose k}}\), a w każdej lidera wybrać możemy na \(\displaystyle{ k}\) sposobów, więc liczba k-osobowych drużyn z jednym kapitanem wynosi \(\displaystyle{ k {n \choose k}}\).
\(\displaystyle{ K}\) przyjmuje wartości od 1 do n, więc w ten sposób opisujemy sytuację po lewej stronie.
Z drugiej strony, możemy najpierw na \(\displaystyle{ n}\) sposobów wybrać kapitana. Wtedy z pozostałych \(\displaystyle{ n-1}\) osób utworzyć możemy \(\displaystyle{ 2^{n-1}}\) różnych podzbiorów, więc tę samą sytuację wyrazić można jako \(\displaystyle{ n*2^{n-1}}\). Zatem L=P.

[tkrass]

i takie rozwiązania jak to drugie sobie cenię.

[budinho]

O dzięki wielkie tak na "chłopski rozum" najlepiej sie przyswaja. Jeszcze raz dzięki:D