Kombinatoricky
Nech $|A|=n$ a skúsme počítať počet prvkov množiny $M=\{(x,X); x\in X\subseteq A\}$.
Počet takých dvojíc, kde $|X|=k$, je presne $k\binom nk$. Preto súčet na ľavej strane dáva $|M|$.
Súčasne ak zafixujeme prvok $x$, tak počet možností pre $X$ je $2^{n-1}$ (pretože každá množina $X$ taká, že $x\in X\subseteq A$ je jednoznačne určená množinou $X\setminus\{x\}\subseteq A\setminus\{x\}$, čiže rátame počet podmnožín $(n-1)$-prvkovej množiny $A\setminus\{x\}$.) Máme $n$ možností pre výber prvku $x$, čo nám celkovo dáva $n2^{n-1}$.
To isté povedané inak:
Máme $n$ študentov. Chceme z~nich vybrať nejaký výbor, výbor si má zvoliť jedného predsedu. Koľko je všetkých možností výberu? (T.j. koľko existuje dvojíc $($výbor, predseda$)$, ktoré vyhovujú týmto podmienkam.
Ak chceme zrátať počet všetkých takýchto dvojíc, môžeme postupovať dvoma spôsobmi.
a) Najprv vyberieme predsedu, potom ostatných členov výboru. Na výber predsedu máme $n$ možností. Potom ostatných členov výboru musíme vybrať spomedzi zvyšných $n-1$ študentov, počet takýchto možností je počet podmnožín $(n-1)$-množiny, teda $2^{n-1}$. Teda celkovo máme $n2^{n-1}$ možností.
b) Pozrime sa teraz na to, koľko je možností, ak výbor má $k$ členov. Na výber výboru máme $\binom nk$ možností. Potom na výber predsedu spomedzi $k$ študentov máme $k$ možností. To nám spolu dáva $k\binom nk$ možností.
Očividne možné hodnoty $k$ sú od $0$ po $n$. Keď sčítame počet možností pre jednotlivé hodnoty $k$, dostaneme celkový počet možností na výber výboru a predsedu.
Keďže sme dostali dve vyjadrenia, ktoré určujú počet prvkov tej istej množiny, tak tieto dve čísla sa musia rovnať a máme
$$\sum\limits_{k=0}^{n} k\binom{n}{k} = n2^{n-1}.$$
Úpravou všeobecného člena
Využijeme rovnosť
$$k\binom nk = n\binom{n-1}{k-1}.$$
Tá sa dokázať viacerými spôsobmi, niektoré sú spomenuté tu:
viewtopic.php?t=988
Pre samotnú sumu potom dostaneme:
$\sum\limits_{k=0}^{n} k \binom nk =
\sum\limits_{k=1}^{n} k \binom nk =
\sum\limits_{k=1}^{n} n \binom{n-1}{k-1} =
n \sum\limits_{k=1}^{n} \binom{n-1}{k-1} =
n \sum\limits_{j=0}^{n-1} \binom{n-1}{j} = n2^{n-1}$
Gaussov trik
Podobný trik ako sme použili pri výpočte $1+2+\dots+n$.
$$S=\sum\limits_{k=0}^{n} k\binom{n}{k} = \sum\limits_{k=0}^{n} (n-k)\binom{n}{k}$$
(Využili sme symetriu: $\binom nk = \binom n{n-k}$.)
$$2S= \sum\limits_{k=0}^{n} k\binom{n}{k} + \sum\limits_{k=0}^{n} (n-k)\binom{n}{k} =
\sum\limits_{k=0}^{n} n\binom{n}{k} = n \sum\limits_{k=0}^{n} \binom{n}{k} = n2^n,$$
a teda $S=n2^{n-1}$.
Indukciou
Pretože pre $k=0$ je súčin $k2^k$ nulový, je jedno či súčet beží od nuly alebo od jednotky, v tomto postupe používame obe možnosti.
\begin{align*}
\sum_{k=1}^{n+1} k\binom{n+1}k
&\overset{(1)}= \sum_{k=1}^{n+1} k\binom{n}k + \sum_{k=1}^{n+1} k\binom{n}{k-1} \\
&\overset{(2)}= \sum_{k=1}^{n} k\binom{n}k + \sum_{j=0}^{n} (j+1)\binom{n}{j} \\
&\overset{(3)}= \sum_{k=1}^{n} k\binom{n}k + \sum_{j=0}^{n} j\binom{n}{j} + \sum_{j=0}^{n} \binom{n}{j} \\
&\overset{(4)}= n2^{n-1} + n2^{n-1} + 2^n \\
&\overset{(5)}= 2n2^{n-1} + 2^n = n2^n+2^n = (n+1)2^n \\
\end{align*}
Tu je vysvetlené, čo sme robili v jednotlivých krokoch:
$(1)$ použili sme Pascalovu formulu $\binom{n+1}k=\binom nk + \binom n{k-1}$;
$(2)$ substitúcia $j=k-1$;
$(3)$ druhú sumu sme rozdelili na dve;
$(4)$ použili sme indukčný predpoklad; okrem neho sme použili známu sumu $\sum\limits_{j=0}^{n} \binom{n}{j}=2^n$ (súčet v riadku Pascalovho trojuholníka);
$(5)$ už iba algebraické úpravy.
Derivovaním
Spomeniem aj toto, hoci o deriváciách ste väčšina z vás ešte neučili.
Binomická veta nám dáva $$(1+x)^n = \sum\limits_{k=0}^n \binom nk x^k.$$
Po zderivovaní oboch strán máme $$n(1+x)^{n-1} = \sum\limits_{k=0}^n k\binom nk x^{k-1}.$$
Ak ešte dosadíme $x=1$, tak dostaneme $$n2^{n-1}=\sum\limits_{k=0}^n \binom nk.$$