Sei 
. Eine binäre Folge der Länge 
ist ein Ausdruck der Form 
, wobei 
für alle 
.
1. Bestimmen Sie alle binären Folgen der Länge 1, 2 und 3.
2. Finden Sie eine Formel für die Anzahl der binären Folgen der Länge , wobei eine feste natürliche Zahl ist, und beweisen Sie diese Formel mit Induktion nach .
1) {0} {1} {10} {11} {100} {101} {110} {111}
2) Die Formel lautet: Länge (n) = 2^n
Beweis mit Induktion nach n:
Induktionsanfang:
n=1
L (1) = 2 = 2^1
Induktionsannahme:
Sei n ≥ 1 und L(n) = 2^n
Induktionsschritt:
Zu zeigen ist, dass diese Annahme L(n+1) = 2^(n+1) impliziert.
L(n+1) = L(n) + L(n) = 2 * L(n) = 2 * 2^n = 2^(n+1)
LaTex hat leider nicht funktioniert… 🙁
Wir üben das demnächst mal per Videokonferenz… vielleicht kann dir auch Katarina helfen?
Hi Alex, wenn die Länge
ist (was richtig ist!), kann deine Lösung zu 1) ja nicht richtig sein, denn das sind ja (bis auf 
) keine 
Folgenglieder. Für 
fehlt beispielsweise die binäre Folge 
.
Beim Induktionsbeweis, der prinzipiell korrekt ist, muss du viel mehr dazu schreiben. Warum gilt denn
? Das musst du erklären.
Aber trotzdem vielversprechende Ansätze, prima! 😊
Zu 1)
n=1: (0) (1)
Es gibt 2^1 = 2 Folgen in n^1.
n=2: (0, 0) (0, 1) (1, 0) (1, 1)
Es gibt 2^2 = 4 Folgen in n^2
n=3: (0,0,0) (0,0,1) (0, 1, 0) (0,1,1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)
Es gibt 2^3 = 8 Folgen in n^3.
Ist es so besser?
Es gilt L(n+1) = 2 * L(n) , da jede Folge aus n in (n+1) einmal mit 0 und einmal mit 1 kombiniert wird. Hieraus folgt: In n+1 gibt es doppelt so viele Folgen wie in n.
Das ist nicht nur besser, sondern sehr gut und richtig! 👏✌️Du siehst es hoffentlich selbst so. Der Leser oder die Leserin deiner Lösung ist nicht jemand, die oder der lange nachdenken möchte, was du dir alles so gedacht hast. Du musst ihm oder ihr jeden Schritt ausführlich erklären, so dass man den Beweis möglichst ohne viel Mühe nachvollziehen kann. Am besten du stellst dir bei deinem Gegenüber gar keinen mitdenkenden Menschen vor, sondern eine Maschine, die deine Argumente nur nachvollziehen kann, wenn du sie formal
und logisch vollständig korrekt sowie ohne Lücken präsentierst. 😊
Ergänzung: „ da jede Folge aus n in (n+1) einmal mit 0 und einmal mit 1 kombiniert wird. “ Das könnte man noch etwas formaler aufschreiben, aber ich lasse es mal so durchgehen. 😉 Die Formalisierung kommt mit der Zeit dann von selbst, wenn du mehrere Beweise gelesen hast.
Danke für die Rückmeldung!