Binäre Folgen

Neue Frage »

Top-SecreT Auf diesen Beitrag antworten »
Binäre Folgen
Ich habe folgende Aufgabe:

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ängen 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. habe ich schon
Länge 1:
Länge 2:
Länge 3:

Und bei 2. haperts schon wieder.
Sei die Anzahl der binären Folgen.

Behauptung: Für alle ist
Induktionsanfang: Sei
Induktionsannahme: Sei und
Induktionsschritt: und hier hab ich keine richtige Idee. Rechts muss stehen aber links?


LG
klarsoweit Auf diesen Beitrag antworten »
RE: Binäre Folgen
Zitat:
Original von Top-SecreT
Sei die Anzahl der binären Folgen.

Behauptung: Für alle ist

Wenn man das etwas präziser schreibt, also etwa so:

Sei die Anzahl der binären Folgen der Länge n.

Behauptung: Für alle ist

dann hast du auch links ein n stehen.

Im Induktionsschritt kannst du dir überlegen, worin sich eine binäre Folge der Länge n sowie der Länge n+1 unterscheiden.
Top-SecreT Auf diesen Beitrag antworten »

Achsooo. Na auf sowas komm ich ja überhaupt nicht verwirrt Wie kommt man denn darauf? Ich habe langsam das Gefühl solche Aufgaben kann man nur "können" indem man sie alle mal gemacht hat denn ständig stoße ich auf Dinge die mir völlig neu sind. (Oder ich bin einfach schlecht in Mathe, keine Ahnung)

Also ist der Induktionsschritt
Es ist zu zeigen dass


Aber jetzt kann ich doch das nicht in der Gleichung nutzen oder? Es heißt ja von und beinhaltet keine Rechenart.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Top-SecreT
Achsooo. Na auf sowas komm ich ja überhaupt nicht verwirrt Wie kommt man denn darauf? Ich habe langsam das Gefühl solche Aufgaben kann man nur "können" indem man sie alle mal gemacht hat denn ständig stoße ich auf Dinge die mir völlig neu sind. (Oder ich bin


Aber das ist doch das Wesen der Induktion: Der Schluss von einer Formel/ Funktionswert/ Eigenschaft für auf die für .

Zitat:
Also ist der Induktionsschritt
Es ist zu zeigen dass


Aber jetzt kann ich doch das nicht in der Gleichung nutzen oder? Es heißt ja von und beinhaltet keine Rechenart.


ist eine Funktion, die jeder natürlichen Zahl einen Funktionswert zuordnet. Wenn du zeigen willst, dass die Formel allgemein gilt, dann kannst du annehmen, dass dies bereits für bewiesen ist und daraus folgt. Außerdem muss die Formel noch für einen Anfangswert direkt bewiesen werden, beispielsweise für .
Top-SecreT Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
Aber das ist doch das Wesen der Induktion: Der Schluss von einerFormel/ Funktionswert/ Eigenschaft für auf die für .


Ja das schon ich meine dass ich jetzt links von schreiben muss statt einer Gleichung/Summe/Formel. Wahrscheinlich habe ich einfach noch zu wenig Erfahrung.
Ich werde dann morgen mal versuchen das weiterzuführen. Danke erstmal.
klarsoweit Auf diesen Beitrag antworten »

Zitat:
Original von Top-SecreT
Aber jetzt kann ich doch das nicht in der Gleichung nutzen oder? Es heißt ja von und beinhaltet keine Rechenart.

Das ist im Grunde auch der Knackpunkt der Aufgabe. Letzten Endes mußt du zeigen, daß gilt. Da hilft nur, die besonderen Eigenschaften einer binären Folge der Länge n bzw. n+1 in Beziehung zu bringen.
 
 
Top-SecreT Auf diesen Beitrag antworten »

Also ich muss zeigen dass



ist. Richtig?

Dann würde ich als erstes aufschreiben



Aber ich weiß nicht so recht wie ich die Formel jetzt weiter umstellen kann Erstaunt1
klarsoweit Auf diesen Beitrag antworten »

Zitat:
Original von Top-SecreT
Dann würde ich als erstes aufschreiben



Das ist natürlich Unfug. Wieso sollte das gelten?

Ein Argumentations-Szenario könnte in etwa so aussehen:

Sei eine binäre Folge der Länge n. Zu dieser Folge gibt es 2 binäre Folgen der Länge n+1, nämlich: und .

Umgekehrt gibt es zu jeder binären Folge der Länge n+1 genau eine binäre Folge der Länge n. Hat mal also m binäre Folgen der Länge n, so gibt es 2*m binäre Folgen der Länge n+1.
Top-SecreT Auf diesen Beitrag antworten »

Ich muss doch bei der Induktion auf jeder Seite jeweils das +1 hinzufügen oder habe ich hier grundsätzlich was falsch verstanden?

Bei der gaußschen Summenformel wird zB geschrieben:



Und diese Formel wird dann umgestellt.
klarsoweit Auf diesen Beitrag antworten »

Zitat:
Original von Top-SecreT
oder habe ich hier grundsätzlich was falsch verstanden?

In der Tat. Im Induktionsschritt mußt du diese Implikation beweisen:

A(n) ==> A(n+1)

Dabei ist A(n) eine von n abhängige Aussage. Und nirgendwo steht, daß man die Aussage A(n+1) erhält, indem man zu A(n) eine 1 oder ein "n+1" (oder was einem sonst noch einfällt) addiert. smile
Top-SecreT Auf diesen Beitrag antworten »

Also ist ?
klarsoweit Auf diesen Beitrag antworten »

Ja, mit einer geeigneten (guten) Begründung. smile
Top-SecreT Auf diesen Beitrag antworten »

Naja reicht diese Zeile mit der Begründung (die du ja schon geschrieben hast)? Ist das ein korrekter Induktionsschritt wenn ich da gar keine Gleichung umgestellt habe oder sonstiges?
klarsoweit Auf diesen Beitrag antworten »

Zitat:
Original von Top-SecreT
Naja reicht diese Zeile mit der Begründung (die du ja schon geschrieben hast)?

In meinen Augen schon. smile

Zitat:
Original von Top-SecreT
Ist das ein korrekter Induktionsschritt wenn ich da gar keine Gleichung umgestellt habe oder sonstiges?

Nun ja, das kommt ja jetzt. Wir haben nun die Gleichung m(n+1) = 2*m(n) . Nun kannst du auf m(n) die Induktionsvoraussetzung anwenden.
Top-SecreT Auf diesen Beitrag antworten »

Idee!

klarsoweit Auf diesen Beitrag antworten »

Zur besseren Transparenz solltest du den Zwischenschritt drin lassen:



Hat also gar nicht weh getan. Augenzwinkern
Top-SecreT Auf diesen Beitrag antworten »

Okay. Nein hat es nicht. Nur Hirnwindungen beansprucht von denen ich noch nicht wusste dass ich sie habe Big Laugh

Vielen Dank.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »