MetaMath '22

Dokažite da vrijedi $$\sum_{i=0}^n i\binom{n}{i}=n2^{n-1}.$$ \textbf{Rješenje} Razred od $n$ učenika potrebno je odabrati njih $i$ koji bi išli na šahovsko natjecanje (moguće je da nitko nije odabran) i od tih $i$ učenika treba odabrati kapetana momčadi koji će igrati na prvoj ploči. Od $n$ učenika biramo njih $i$, za što imamo $\binom{n}{i}$ mogućnosti. Zatim od tih $i$ biramo jednog koji će biti kapetan, za što imamo $i$ mogućnosti. Kako možemo odabrati od $0$ do učenika od $n$ učenika slijedi da je ukupan broj mogućnosti $$\sum_{i=0}^n\binom{n}{i}\cdot i.$$ Odabir možemo napraviti i na sljedeći način: najprije biramo kapetana ekipe, što možemo napraviti na $n$ načina. Zatim od preostalog broja učenika ($n-1$) za svakog imamo mogućnost da ide ili ne, što je $2^{n-1}$ mogućnosti. Stoga je ukupan broj mogućnosti $n\cdot 2^{n-1}$. Po principu dvostrukog prebrojavanja zaključujemo da ta dva broja trebaju biti jednaka, odnosno $$\sum_{i=0}^n\binom{n}{i}\cdot i=n\cdot 2^{n-1},$$ što smo i trebali vidjeti. Kao rješenje upišite $0$.