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}ⁿ. Es gibt außerdem einen Binärstring der Länge 0, welcher mit ε bezeichnet wird.

Beweisen: 

Für jedes n ≥ 0 gibt es 2 ⁿ⁺¹ − 1 Binärstrings der Länge höchstens n.

Answer 1

Verankerung.

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

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

Induktionsschritt: n --> n+1.

Strings der Länge n+1 gibt es genau 2ⁿ⁺¹. 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ⁿ⁺¹ - 1 + 2ⁿ⁺¹ = 2*2ⁿ⁺¹ - 1 = 2¹ * 2ⁿ⁺¹ - 1 = 2^((n+1)+1) - 1. q.e.d. Induktionsschritt.