msleziak.com

Dokážte, že pre ľubovoľné nezáporné celé čísla $k$, $m$, $n$ platí
$$\sum_{j=0}^k \binom mj \binom n{k-j}=\binom{m+n}k.$$

Toto sa volá Vandermondova identita - Wikipédia

Kombinatoricky
Počítajme počet možností ako sa dá vybrať $k$-členný výbor z $m$ mužov a $n$ žien.
Počet možností na výber $k$ ľudí je $\binom{m+n}k$.
Koľko je možných výborov takých, kde je práve $j$ mužov? Znamená to, že zvyšok výberu tvoria ženy, t.j. museli sme vybrať $j$ mužov spomedzi $n$ a $k-j$ žien spomedzi $n$. Teda počet takýchto možností je $\binom mj \binom n{k-j}$.
Ak sčítame tento výraz cez všetky možné hodnoty $j$, tak zistíme, že suma
$$\sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j}$$
tiež vyjadruje počet všetkých možných výborov.

Ak to chcete "matematickejšie", tak môžete počítať $k$-prvkové podmnožiny $\{1,2,\dots,m+n\}$ a rozdeliť ich podľa toho, koľko prvkov z podmnožiny patrí do $\{1,2,\dots,m\}$.

Binomická veta a súčin
Ak porovnáme člen pri $x^k$ vo výrazoch $(1+x)^{m+n}$ a $(1+x)^m(1+x)^n$, tak dostaneme presne uvedené výrazy.

Indukcia
Možno je zaujímavé zamyslieť sa aj nad dôkazom indukciou - pretože tu máme viacero premenných, nie je úplne jasné, vzhľadom na ktorú z nich by sa dala robiť indukcia.

Skúsme napríklad dokazovať indukciou vzhľadom na $m$ tvrdenie, že uvedená rovnosť platí pre ľubovoľné $n$ a $k$.

$1^\circ$ Báza indukcie: Chceme overiť, či rovnosť platí pre $m=0$.
Na ľavej strane máme $\binom nk$.
Na pravej strane máme sumu, v ktorej vystupujú členy tvaru $\binom 0j$. Jediný prípad, kedy je takýto člen nenulový je ak aj $j=0$. Dostaneme teda jediný sčítanec $\binom 00 \binom nk = \binom nk$.

$2^\circ$ Indukčný krok: Predpokladáme, že rovnosť platí pre $m$ a snažíme sa ju dokázať pre $m+1$.
\begin{align*}
\binom{m+n+1}k&=\binom{m+n}k+\binom{m+n}{k-1}\\
&\overset{(1)}=\sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} + \sum_{j=0}^{k-1} \binom{m}{j} \binom{n}{(k-1)-j}\\
&\overset{(2)}=\sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} + \sum_{j=1}^{k} \binom{m}{j-1} \binom{n}{k-j}\\
&\overset{(3)}=\sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} + \sum_{j=0}^{k} \binom{m}{j-1} \binom{n}{k-j}\\
&\overset{(4)}=\sum_{j=0}^{k} \left(\binom{m}{j} + \binom{m}{j-1} \right) \binom{n}{k-j}\\
&\overset{(5)}=\sum_{j=0}^{k} \binom{m+1}{j} \binom{n}{k-j}
\end{align*}
Všimnime si, že v kroku $(3)$ sme pridali k druhej sume nulu.

(Veľmi podobne by sa dala urobiť indukcia vzhľadom na $k$.)