Binomialkoeffizient/Summe in Pascaldreieck/Fakt/Beweis2

Beweis

Es sei ${}M$ eine ${}(n+1)$-elementige Menge und ${}x\in M$ ein fixiertes Element. Nach Fakt ist die Anzahl der ${}k$-elementigen Teilmengen von ${}M$ gleich ${}{\binom {n+1}{k}}$. Eine solche Teilmenge enthält entweder ${}x$ oder aber nicht. Im ersten Fall entspricht dann eine solche Teilmenge einer ${}(k-1)$-elementigen Teilmenge von ${}M\setminus \{x\}$, das ergibt den Summanden ${}{\binom {n}{k-1}}$. Im zweiten Fall entspricht eine solche Teilmenge einer ${}k$-elementigen Teilmenge von ${}M\setminus \{x\}$, das ergibt den Summanden ${}{\binom {n}{k}}$.

Zur bewiesenen Aussage