Eine interessante Eigenschaft von Fibonacci-Zahlen

Ich habe heute eine Prüfung abgelegt, bei der es um folgende Frage ging:

A. Wir nennen eine binäre Folge „spärlich“, wenn es keine zwei aufeinanderfolgenden gibt 1 ist drin. Berechnen Sie die Anzahl der dünnen Zeichenfolgen der Länge N .

B. Beweisen Sie, dass jede ganze Zahl als Summe nicht aufeinanderfolgender unterschiedlicher Fibonacci-Zahlen ausgedrückt werden kann.

C. Beweisen Sie, dass die Summe in (b) eindeutig ist.

D. Leiten Sie entweder (a) unter Verwendung von (b) und (c) ab oder leiten Sie (c) unter Verwendung von (a) und (b) ab .

Jetzt weiß ich sehr gut, wie man die Wiederholungsrelation in (a) findet . Ich habe vor ein paar Jahren auch die Beweise von (b) und (c) studiert und hatte keine großen Schwierigkeiten, sie aus dem Gedächtnis zu konstruieren.

Aber ich bin in (d) stecken geblieben . Ich habe versucht zu verstehen, wie man die Ergebnisse von (a) , (b) und (c) verbindet . Nachdem ich darüber nachgedacht hatte, kam ich auf diesen Ausdruck

S ( X 1 , X 2 , … , X N ) = X 1 F 1 + X 2 F 2 + ⋯ + X N F N
für ein gegebenes k Wo F N ist die bisher größte Fibonacci-Zahl k Und X ich ∈ { 0 , 1 } ∀ ich ∈ { 1 , 2 , … , N } . Nun, wenn wir wollen S = k , dann die Folge X 1 , X 2 , … , X N muss spärlich sein. Aber aus (a) wissen wir, dass es nur gibt F N + 2 solche spärlichen Sequenzen. Auch besteht nach (b) eine Wahlmöglichkeit ( j 1 , j 2 , … , j N ) = ( X 1 , X 2 , … , X N ) mit j ich ∈ { 0 , 1 } ∀ ich ∈ { 1 , 2 , … , N } so dass S ( j 1 , j 2 , … , j N ) = k . Auch ist klar, dass die Werte von S die wir bekommen können, indem wir die Auswahl ändern X ich 's sind in einer strengen Reihenfolge angeordnet (dh zwei von ihnen können nicht gleich sein). Es gibt also genau eine Auswahl von X ich ist so das S = k .

Aber an meinem Beweis scheint etwas faul zu sein. Ich habe nicht die Tatsache verwendet, dass es gibt F N + 1 Auswahl von X ich ist irgendwo hier drin. Ist mein Beweis also richtig? Wenn nein, ist mein Ansatz richtig? Kann mir bitte jemand dabei helfen?

@Jean-ClaudeArbaut Ja, ich weiß. Aber das Problem, das ich habe, ist in Teil (d) , der uns auffordert, Teil (a) mit dem Satz von Zeckendorf zu verbinden.
Es gibt einen Vorbehalt im Eindeutigkeitsteil von Zeckendorfs Theorem, der nicht oft erwähnt wird: Sie können den ersten nicht verwenden 1 in der Fibonacci-Folge. Wenn Sie das zulassen 1 , hat jede geradzahlige indizierte Fibonacci-Zahl zwei Darstellungen: F 2 k Und ∑ ich = 1 k F 2 ich − 1 .
Ich denke auch, was sie verlangen, ist entweder zu beweisen, dass die Abbildung bijektiv ist und daher dieselbe Kardinalität hat, oder zu beweisen, dass sie, da die Mengen dieselbe Kardinalität haben und die Abbildung surjektiv ist, daher auch injektiv ist. Dein Ansatz scheint letzteres zu sein.
@arbashn Danke für den Hinweis

Antworten (1)

Die maximale Anzahl, die mit einer dünnbesetzten Sequenz der Länge dargestellt werden kann N Ist u N = F N + 1 + F N − 1 + F N − 3 + … , wo die Summe höchstens aufhört F 2 [1]. Das kannst du beweisen u N = F N + 2 − 1 .

Wenn Sie nun alle Zahlen eindeutig darstellen können, zwischen 0 Und F N + 2 − 1 , das ist F N + 2 Zahlen, das ist genau die Anzahl der dünn besiedelten Sequenzen der Länge N .

[1] Wie oben von Arbashn ausgeführt, beginnen die Fibonacci-Zahlen, die für die Zeckendorf-Darstellung verwendet werden, bei F 2 = 1 .

Ja, das scheint absolut richtig zu sein. Danke!
Eine interessante Eigenschaft von Fibonacci-Zahlen
AntwortenHierDatenschutz-Bestimmungen1y, 0v