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)^n machen?

lul

---

Muss es nicht mit Induktion machen. Wie würde ich es denn mit (1+1)^n 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 ;-)