Beweisen Sie dass Summe (n über k) = 2^n mit einem Satz aus der Analysis

Question

Ich soll folgendes Beweisen:

$$ \sum \limits_{j=0}^{n} \begin{pmatrix} n\\j \end{pmatrix} = 2^{n} $$. Hierfür soll ich einen Satz aus der Analysis verwenden. hat jemand eine Idee, welchen ich verwenden könnte?

Answer 1

Hallo,

nach dem binomischen Lehrsatz ist $$(x+y)^n = \sum_{j=0}^n {n \choose j} x^{n-j} y^{j}$$Setze nun \(x=y=1\)

Comments

Stimmt. Danke. Ich soll auch ein kombinatorisches Argument nutzen. Weißt du vielleicht was man darunter versteht?

---

Ich soll auch ein kombinatorisches Argument nutzen.

Es gibt ja die Anzahl \(m\) der Möglichkeiten ein gewisse Anzahl \(k\) aus \(n\) Elementen auszuwählen (siehe Binominalkoeffizient in der Kombinatorik) $$m= \frac{n!}{k! (n-k)!}= {n \choose k}$$zum Beispiel 6 aus 49 (Lotto).

Wenn man jetzt alle Möglichkeiten betrachtet, irgendeine Anzahl \(k \in [0;n]\) aus \(n\) Elementen auszuwählen, so ist das identisch mit der Anzahl von Zahlen im Binärsystem mit \(n\) Stellen. Die \(k\) ausgewählten sind hier immer die Stellen, wo eine \(1\) steht. Und diese Anzahl ist \(2^n\), Daraus folgt$$\sum_{k=0}^n {n \choose k} = 2^n$$