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

Question

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.

Answer 1

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.