Summe n-1 über t-1 gleich 2^(n-1)

Question

Aufgabe:

\( \sum\limits_{t=1}^{n}{\begin{pmatrix} n-1\\t-1 \end{pmatrix}} \) =\( 2^{n-1} \)

Problem/Ansatz:

Wie komme ich darauf? Binomialkoeffizient ist das n-1 über t-1

Comments

Ist da kein Schreibfehler in der Aufgabe?

t kommt nur an einer einzigen Stelle vor.

---

Oh sorry hab es vergessen. Bearbeitet

---

Und was mach das n vor dem Gleichheitszeichen?

---

Habe ich auch korrigiert

Answer 1

Aloha :)

Wenn du die Summe etwas umschreibst:$$\sum\limits_{t=1}^n\binom{n-1}{t-1}=\sum\limits_{t=1\pink{-1}}^{n\pink{-1}}\binom{n-1}{(t\pink{+1})-1}=\sum\limits_{t=0}^{n-1}\binom{n-1}{t}=\sum\limits_{t=0}^{n-1}\binom{n-1}{t}\cdot\underbrace{\pink{1^{(n-1)-t}\cdot1^t}}_{=1}$$und mit dem binomischen Lehrsatz vergleichst$$(a+b)^n=\sum\limits_{t=0}^n\binom{n}{t}\cdot a^{n-t}\cdot b^t$$erkennst du mit \(a=1\) und \(b=1\), dass Folgendes gilt:$$\sum\limits_{t=1}^n\binom{n-1}{t-1}=(1+1)^{n-1}=2^{n-1}$$

Answer 2

Einige Ansätze geordnet von Low-Level zu High-Level:

1. \(\sum\limits_{t=1}^{n}\begin{pmatrix}n-1\\ t-1\end{pmatrix} = \sum\limits_{t=0}^{n-1}\begin{pmatrix}n\\ t\end{pmatrix} = \sum\limits_{t=0}^{n-1}\begin{pmatrix}n\\ t\end{pmatrix}1^t1^{n-1-t}=(1+1)^{n-1}=2^{n-1}\) nach Binomiallehrsatz.

2. Nutze Induktion und die Additionsformel für Binomialkoeffizienten.

3. "Offensichtlich" ist die Summe einfach nur "Die 0-elementigen Teilmengen von \(\{1,\ldots,n-1\}\)" + "Die 1-elementigen Teilmengen von \(\{1,\ldots,n-1\}\)" + ... + "Die n-1-elementigen Teilmengen von \(\{1,\ldots,n-1\}\)" = "Alle Teilmengen von \(\{1,\ldots,n-1\}\)" = \(2^{n-1}\) in Kardinalität.