TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 157

Man beweise die Beziehung ${\binom {n+1}{k+1}}={\binom {n}{k+1}}+{\binom {n}{k}}$ durch Interpreation von ${\binom {n}{k}}$ als Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge.

Lösungsvorschlag von neo

Man kann die Auswahl von $k+1$ Elementen aus einer $n+1$-elementigen Menge auf eine $n$-elementige Menge zurückführen (d.h ohne ein Element $a$).
Man nimmt zuerst alle $k+1$ Elemente aus der $n$-elementigen Menge heraus. Dafür gibt es ${\binom {n}{k+1}}$ Möglichkeiten. Anschließend betrachtet man alle Auswahlen, welche das Element $a$ beinhalten. Da das Element $a$ zwangsweise dabei sein muss, kommen nur $k+1-1=k$ Elemente aus der $n$-elementigen Menge dazu.
Das ergibt ${\binom {n}{k}}$ Möglichkeiten. So kommt man auf ${\binom {n+1}{k+1}}={\binom {n}{k+1}}+{\binom {n}{k}}$.