Vollständige Induktion Binomialkoeffizient

Question

Aufgabe:

$\sum \limits_{k=0}^{n}\begin{pmatrix} n\\k \end{pmatrix} = 2^{n}$

Problem/Ansatz:

Könnte mir das bitte einer vorrechnen?
Ich habe da etwas Probleme und komme beim Induktions-Schritt nicht weiter.
Danke :)

Comments

Hallo

musst du das mit Induktion machen? oder kann~st es einfach mit (1+1)ⁿ machen?

lul

---

Muss es nicht mit Induktion machen. Wie würde ich es denn mit (1+1)ⁿ machen?

Answer 1

Binomischen Satz anwenden:

 $2^n = (1+1)^n = \sum \limits_{k=0}^n \begin{pmatrix} n\\k \end{pmatrix} \cdot 1^k \cdot 1^{n-k} = \sum \limits_{k=0}^n \begin{pmatrix} n\\k \end{pmatrix}$

Answer 2

$n\choose k$ ist die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge.

Für $k \notin \{0,\dots,n\}$ gibt es keine $k$-elementige Teilmenge einer $n$-elementigen Menge . Also ist $\sum\limits_{k=0}^n{n\choose k}$ die Anzahl der Teilmengen einer $n$-elementigen Menge.

Die Anzahl der Teilmengen einer $n$-elementigen Menge ist auch $2^n$.

Also ist $\sum\limits_{k=0}^n{n\choose k} = 2^n$.

Answer 3

Hallo,

es ist sicher am einfachsten es über den Binomischne Satz zu zeigen (siehe Antwort von mathef). Aber es geht natürlich auch via Induktion

Induktionsanfang:$$\sum \limits_{k=0}^{n}\begin{pmatrix} n\\k \end{pmatrix} = 2^{n} \\ n=1 \quad \implies {1\choose 0} + {1\choose 1} = 2^{1}\space \checkmark$$Für den Induktionsschritt nutzt man aus, dass$${n+1\choose k} = {n\choose k-1} + {n\choose k}$$und dann geht das z.B. so:$$\begin{aligned} \sum \limits_{k=0}^{n+1} {n+1\choose k} &={n\choose 0} + \sum \limits_{k=1}^{n} {n+1\choose k} + {n+1\choose n+1} \\ &= \sum \limits_{k=1}^{n} {n\choose k-1 } +\sum \limits_{k=1}^{n} {n\choose k} + 2 &&|\,\text{(s.o.)}\\ &= \sum \limits_{k=0}^{n-1} {n\choose k }+{n\choose n} +\sum \limits_{k=1}^{n} {n\choose k} + {n\choose 0} \\ &= \sum \limits_{k=0}^{n} {n\choose k } +\sum \limits_{k=0}^{n} {n\choose k} &&|\,\text{lt. Voraussetzung}\\ &= 2^n+2^n \\ &=2\cdot 2^n = 2^{n+1} \end{aligned}$$

Comments

Kleiner Tippfehler im IA. Dort sollte 2 rauskommen.

---

Kleiner Tippfehler im IA. Dort sollte 2 rauskommen.

Danke - einmal falsch hingeschrieben, und man sieht es nicht mehr ;-)