Dowód bez wykonywania rachunków

[Wojtolino]

Mam problem. W zbiorku mam zadanie z zastrzeżeniem, że nie mogę tego policzyć, tylko sam nie wiem nawet jak. A dowieść trzeba, że \(\displaystyle{ {n \choose k}= {n-1 \choose k-1} + {n-1 \choose k}}\).
Z tyłu mam wskazówkę, która mi nic nie daje
Niech \(\displaystyle{ \left| A\right|=n, B \subseteq A, \left| B\right| =k, a \in A}\). Wtedy albo \(\displaystyle{ a \in B}\), albo \(\displaystyle{ a\not\in B}\). Wydaje mi się to kompletnie bez sensu (też mi uwaga, albo należy albo nie...). Pomocy wzywam.

[Crizz]

Potraktuj \(\displaystyle{ {n \choose k}}\) jako k-elementową kombinację bez powtórzeń zbioru n-elementowego. Spróbuj zapisac liczbę takich kombinacji na dwa sposoby: raz jako zwykłe \(\displaystyle{ {n \choose k}}\) (to masz po lewej stronie), a za drugim razem "wyjmij" jeden element z n-elementowego zbioru i osobno policz, ile jest takich kombinacji, w których ten element jest, a ile takich, w których go nie ma. Ta wskazówka mówi pośrednio właśnie o takim podziale.

Możesz też podejść do problemu z drugiej strony, tzn. mamy ilość k-elementowych kombinacji zbioru \(\displaystyle{ n-1}\) - elementowego (czyli \(\displaystyle{ {n-1 \choose k}}\)), dokładamy jeden element i mamy zbadać, ile teraz istnieje k-elementowych kombinacji tego zbioru.