Binomialkoeffizient Beweis diskrete Mathematik

Question

Hallo,

ich habe ein wenig Probleme bei dieser Aufgabe. Mit vollständiger Induktion komme ich nicht weit. Und der Hinweis unten verwirrt mich nur noch mehr.

Zeigen Sie
$$\sum \limits_{k=n}^{m}\left(\begin{array}{l} k \\ n \end{array}\right)=\left(\begin{array}{l} m+1 \\ n+1 \end{array}\right)$$
für $n, m \in \mathbb{N}_{0}$
Hinweis: Zählen Sie die $(n+1)$ -elementigen Teilmengen von $\{0, \ldots, m\}$ mit vorgegebenem Maximum.

Ich bin für jede Anregung oder Lösung dankbar.

Liebe Grüße

Answer 1

Hallo,

die rechte Seite gibt offenbar die Anzahl der (n+1)-Teilmenten von M:= {0,1,...,m} an. Diese Zahl kann ich durch eine alternative Abzählung dieser Teilmengen erhalten:

Wenn $T:=\{x_1, \ldots,x_{n+1}\} \subseteq M$, dann können wir annehmen, dass die $x_i$ aufsteigend angeordnet sind, so dass $x_{n+1}$ das Maximum dieser Elemente ist. Daher kann ich T auch so charakterisieren:

$$T=S \cup \{x_{n+1}\} \quad \text{ mit } S \subseteq \{0,1, \ldots, x_{n+1}-1\}$$

In Worten: Jede Teilmenge $T \subseteq M$ mit (n+1) Elementen ist eindeutig durch das maximale Element p und eine n-elementige Menge von kleineren Elementen charakterisiert, also aus $\{0, \ldots,p-1\}$. Davon gibt es ${p \choose n}$ Teilmengen und p muss mindestens n sein und ist maximal m.

Das erklärt die linke Seite.

Gruß