Finden Sie eine natürliche Zahl n, sodass |∑n| = 16

Question

Aufgabe:

Gegeben sei das Alphabet ∑={a, b}. Für jede natürliche Zahl n ist die Menge ∑ⁿ definiert
als ∑ⁿ={x₁,...,x_n | x₁,...,x_n ∈ ∑ }.

Finden Sie eine natürliche Zahl n, sodass |∑ⁿ| = 16 und geben Sie die Elemente von
∑ⁿ in quasi-lexikographischer Reihenfolge an.

Beweisen Sie, dass für jede natürliche Zahl n die Formel |Uⁿ_i=0|=2ⁿ⁺¹−1 gilt.

Problem/Ansatz:

Ich hab leider keine Ahnung, wie ich diese Aufgabe lösen kann, deshalb würde ich mich sehr freuen, wenn mir jemand dabei helfen kann^^

Answer 1

Jedes Element aus \( \Sigma^{n} \) ist ein \( n \) Tupel bestehend aus einer Sequenz von a's und b's. Für jede der \( n \) Positionen im Tupel kann man entweder a oder \( b \) wählen, also gibt es insgesamt \( 2^{n} \) Elemente in \( \Sigma^{n} \).
Nun sind die verschiedenen \( \Sigma^{i} \) disjunkt, also ist

\(\begin{aligned} \left|\bigcup_{i=1}^{n} \Sigma^{n}\right|=\sum \limits_{i=1}^{n} 2^{i}=2^{n+1}-1\end{aligned} \)

wobei die geometrische Reihe verwendet wurde.