Rekursive Formel für Anzahl von per. Punkten finden

Neue Frage »

kev04 Auf diesen Beitrag antworten »
Rekursive Formel für Anzahl von per. Punkten finden
Meine Frage:
Ich habe einen Raum dessen Punkte aus unendlichen Folgen von 1en und 0en bestehen. Das für s auch dem raum gilt s=(s0s1s2s3.........) mit si=1 oder si=0.
Ich schränke den Raum nun noch ein, indem keine zwei 0en aufeinander folgen dürfen, d.h. si=0 => si+1=1.

Des Weiteren gibt es eine Abb f für die gilt f(s0s1s2s3....)=(s1s2s3s4......). Es wird also s0 vergessen. Zur Aufgabe:

Es soll eine rekursive Formel für die Anzahl der F.P. von f^n gefunden werden, d.h. an+2 soll mit Hilfe von an+1 und an dargstellten werden, wobei an die Anzahl der F.P. von f^n ist.

Meine Ideen:
Ich habe mir das ganze mal für die ersten nat. Zahlen aufgeschrieben. Dabei fällt auf, dass für diese gilt an+2=an+1 +an. Es handelt sich hier also um eine (verschobene) Fibonacci-Folge.
Soweit so gut.

Um meine Vermutung zu beweisen bin ich wie folgt vorgegangen.

Die F.P. von f^n habe die Form (s0s1s2s3.....sn-1,s0s1s2s3....sn-1,...)
1. Fall
s0=1 Dann ist s1.....sn-1 Folge von 1en und 0en der Länge n-1.

2. Fall s0=0 => s1=1 und sn-1=1
s2....sn-2 ist Folge von 1en und 0en der Länge n-3.
also ergibt sich an+2=an+1 + an-1

Das wollte ich aber nicht zeigen.
Wo liegt mein Denkfehler?
kev04 Auf diesen Beitrag antworten »

Hat den niemand eine Idee?
 
 
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von kev04
Ich schränke den Raum nun noch ein, indem keine zwei 0en aufeinander folgen dürfen, d.h. si=0 => si+1=1.

Des Weiteren gibt es eine Abb f für die gilt f(s0s1s2s3....)=(s1s2s3s4......). Es wird also s0 vergessen. Zur Aufgabe:

Es soll eine rekursive Formel für die Anzahl der F.P. von f^n gefunden werden, d.h. an+2 soll mit Hilfe von an+1 und an dargstellten werden, wobei an die Anzahl der F.P. von f^n ist.

Kurz gesagt:

Du suchst die Anzahl aller -stelligen Bitfolgen (bzw. zumindest eine Rekursionsformel für diese Anzahl), wo keine zwei Nullen hintereinander vorkommen, wobei das ganze "zirkulär" betrachtet wird (d.h. letzte und erste Stelle sind auch "Nachbarn") - richtig? verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Ok, führen wir noch ein paar Bezeichnungen ein.

... Anzahl der -stelligen Bitfolgen ohne Übergänge 00, auch ist verboten

ist die von dir eingeführte Folge, mit den Startwerten .

... Anzahl der -stelligen Bitfolgen ohne Übergänge 00 innerhalb, hier ist erlaubt

ist das Äquivalent in der "linearen" Variante. Aufgrund der etwas lockereren Bedingung, was die Bitfolgenenden betrifft, sind hier die Werte mit Ausnahme von n=2 größer als bei , konkret startet diese Folge mit .


Dann liegt hier

Zitat:
Original von kev04
1. Fall
s0=1 Dann ist s1.....sn-1 Folge von 1en und 0en der Länge n-1.

2. Fall s0=0 => s1=1 und sn-1=1
s2....sn-2 ist Folge von 1en und 0en der Länge n-3.
also ergibt sich an+2=an+1 + an-1

ein Trugschluss vor: Was du hier beschreibst, läuft tatsächlich auf die Formel hinaus. Mit ähnlichen Betrachtungen für wiederum bekommt man , was dann über die erste Beziehung rückwirkend auch zu führt.

Mit den o.g. Startwerten stellt sich heraus, dass tatsächlich eine verschobene Fibonacci-Folge ist, nämlich . Damit ist dann -


EDIT: Hallo? Erst drängeln, und dann aber trotz Vorbeischauen im Board keine Zeit für eine Reaktion? smile
kev04 Auf diesen Beitrag antworten »

Entschuldige, dass ich so spät antworte, hatte keine Zeit die Aufgabe ganz zu lösen und wollte erst antworten, wenn ich die Aufgabe erneut veruscht habe. Ich danke dir sehr, dass du meinen Denkfehler gefunden hast. Hab es verstanden und habe den Beweis nun aufgestellt. Gott Gott Gott
HAL 9000 Auf diesen Beitrag antworten »

Normalerweise bin ich geduldiger. Aber diese Retourkutsche musste einfach sein. Big Laugh
kev04 Auf diesen Beitrag antworten »

Big Laugh Damit muss ich dann wohl leben. Hast mir auf jeden sehr geholfen. Woher wussten du denn, dass ich on war?
HAL 9000 Auf diesen Beitrag antworten »

Die NSA merkt alles ... nein, im Ernst: Im Userprofil wird unter "Letzte Aktivität" der Zeitpunkt des letzten Besuches vermerkt - auch bei "nur reinschauen". smile
Neue Frage »
Antworten »



Verwandte Themen

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