Rekursionsgleichung

Aufrufe: 148     Aktiv: vor 1 Woche

0

ich habe versucht, diese Aufgabe für meine Klausurvorbereitung zu lösen. Die fand ich schwer. Könnte jemand mir vielleicht helfen? würde auf eure Hilfe sehr freuen. Danke im Voraus

Fuer n ∈ N0 sei bn die Anzahl der 0-1-Folgen der Laenge n + 1, in denen mindestens einmal zwei Nullen direkt hintereinander stehen. Zum Beispiel ist b0 = 0, b1 = 1 und b2 = 3. Finden Sie eine (nicht notwendig lineare) Rekursionsgleichung fuer die Folge (bn)n∈N0 .

 

 

gefragt vor 1 Woche, 6 Tage
M
MinhHiu,
Punkte: 14

 

Es ist auf edenfall die Fibonacci Rekursion! Die aufgabe kam letztes jahr bei mir in der Klausur. Leider habe ich dazu die lösung nicht, aber im Gespräch mit paar leuten kam das heraus, falls dir das weiter hilft

  ─   labis.theodoros, vor 1 Woche, 6 Tage

Du solltest dir überlegen, wie sich bn verändert, wenn ein Zeichen an eine Folge angehängt wird. Das kann man mit Beispielen machen. So fängt es an, auf die Formel kommt man dann später.

  ─   mikn, vor 1 Woche, 6 Tage

also ich habe mich mal an der aufgabe versucht und würde mich sehr darüber freuen, wenn ich paar Stupser bekomme. die aufgabe sieht eigneltich nicht schwer aus, aber etwas fehlt mir.

{0,1}^1 = (01),
{0,1}^2 = {0,1}x{0,1} = (00,01,10,11)
{0,1}^3 = {0,1}x{0,1}x{0,1} = (000,001,010,011,100,101,110,111)

aber wir müssen ja nur die ersten zwei bestimmen. dann ist ja a_1 = 1, aber wie bestimme ich a_2? die doppel null bleibt weg, die wird ja laut definition ausgeschlossen, übrig bleiben drei Werte (01,10,11). ich verstehe nun nicht, wie ich aus dieser Menge den Wert a_2 generieren soll? bei a_1 hab ich addiert und 1+0 ist 1, aber hier geht das ja nicht, oder geht es nur um die anzahl der elemente? da gäbe es exakt 1. und bei a_2 sind es 3, bei a_3 sind es 5.

EDIT: ja es handelt sich um die anzahl der elemente. hab gerade noch mit a_4 probiert. da kommt für a_4 = 8 raus. daran lässt sich zumindest erkennen, dass es Fibonacci ist. Aber bei der Erstellung einer Rekursionsrelation verstehe ich eine sache nicht. Die Relation soll für n größer gleich 1 sein. das problem ist, dass zwar a_0 = 0 ist, aber wenn ich die relation aufstelle habe ich ja a_n = a_{n-1}+a_{n-2} und für n = 1 haut das nicht hin.

  ─   labis.theodoros, vor 1 Woche, 3 Tage

Du solltest die Folgen aufschreiben, die Du zählen sollst. Deine an sind andere. Ich weiß nicht, was Du da tust. Und vergiss die Fibonacci-Folge oder andere Lösungen. Aus Lösungen lernst Du nichts (und erst recht nicht falshe, es ist nicht die Fibonacci-Folge).

  ─   mikn, vor 1 Woche, 3 Tage

ich habe gesehen, dass meine Aufgabe etwas anders ist. in der hier geht es ja darum, dass direkt zwei nullen hintereinander stehen. in meiner geht es darum, dass sie nicht hintereinander stehen und diese aus der Menge fliegen.

Für n größer gleich 1 sei a_n = #{(x_1,...,x_n) in {0,1]^n mit für alle 1 \le j \le n-1 : x_j + x_{j+1} größer 0} die Anzahl alle Sequenzen von Nullen und Einsen der Länge n, sodass keine zwei aufeinander folgenden Folgeglieder gleich Null sind.
(i) bestimme a_1 und a_2 und die Rekursionsrelation
(ii) Finden Sie einen geschlossenen Ausdruck für a_n, n größer gleich 1.

ich hab wie oben ja schon steht, meine Gedanken dazu gemacht. Meine rekursion läuft aber erst ab n größer gleich 2 und das wäre falsch :/

  ─   labis.theodoros, vor 1 Woche
Kommentar schreiben Diese Frage melden
0 Antworten