0 Daumen
849 Aufrufe

Ein Binärstring der Länge n > 0 ist ein Element aus {0, 1}^n. Es gibt außerdem einen Binärstring der Länge 0, welcher mit ε bezeichnet wird.

Beweisen:

Für jedes n ≥ 0 gibt es 2 ^{n+1} − 1 Binärstrings der Länge höchstens n.

Avatar von

1 Antwort

0 Daumen

Verankerung.

Länge höchstens 0. Nur ein String: Epsilon. 2^1 -1 = 1. Richtig.

Länge höchstens 1 = Länge 0 + Länge 1 = 1 + 2 = 3 = ?= 2^2 -1 . Richtig.

Induktionsschritt: n --> n+1.

Strings der Länge n+1 gibt es genau 2^{n+1}. Jede Stelle kann mit 0 oder 1 gefüllt werden.

Strings der Länge höchstens n+1 gibt es so viele wie

(Strings der Länge höchstens n) + (Strings der Länge n+1)          | Ind.vor. einsetzen.

= 2^{n+1} - 1 + 2^{n+1} = 2*2^{n+1} - 1 = 2^1 * 2^{n+1} - 1 = 2((n+1)+1) - 1. q.e.d. Induktionsschritt.

Avatar von 162 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community