Question

Rekursionsgleichung

Aufrufe: 838 Aktiv: 21.08.2020 um 01:15

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 .

Teilen Diese Frage melden

gefragt 01.08.2020 um 09:16

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 01.08.2020 um 22:42

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.

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 04.08.2020 um 10:01

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 07.08.2020 um 11:09

Kommentar schreiben

2 Antworten

rodion26 · Answer 1 · 2020-08-20T23:51:23Z

Zuerst mal etwas Grundsätzliches zur Rekursion:

Meistens besitzt man zum Beenden der Rekursion nur einen bekannten Wert, z.B. \(f(0)\). Es ist aber völlig OK, wenn man zwei (oder viele) bekannte Werte benötigt (und diese auch besitzt), z.B. \(f(0)\) und \(f(1)\), wie bei Fibonacci.

Jetzt zu deiner Aufgabe:

Wie viele unterschiedliche Folgen der Länge \( n+1 \) kann man aus den Zeichen \( 0,1 \) bilden, in denen mindestens einmal zwei Nullen hintereinander stehen?

Zum Verständnis lohnt es sich, erst mal alle möglichen Folgen der Länge \( n+1 \) in drei Klassen einzuteilen:

\(A_n\) sind alle Folgen der Länge \( n+1 \). Davon gibt es \( a_n = 2^{n+1} \) Stück.

\(B_n\) sind die Folgen, die ein \(0,0\) Paar enthalten.

\(C_n\) sind die Folgen, die kein \(0,0\) Paar enthalten und auf eine \(0\) enden.

\(D_n\) sind die Folgen, die kein \(0,0\) Paar enthalten und auf eine \(1\) enden.

Sicher gilt \( a_n = b_n + c_n + d_n \).

In der Rekursion hängen wir an die Folgen der Länge \(n\) hinten eine \(0\) oder eine \(1\) an.

\( b_n = 2 \cdot b_{n-1} + c_{n-1} \), mit \(0\) oder \(1\) an einer \(B\)-Folge oder einer weiteren \(0\) an einer \(C\)-Folge.

\( c_n = d_{n-1} \), mit einer \(0\) an einer \(D\)-Folge.

\( d_n = c_{n-1} + d_{n-1} \), mit einer \(1\) an einer \(C\)- oder \(D\)-Folge.

Wenn man genau hinschaut, kann man jetzt eine Fibonacci-Folge erkennen:

\( d_n = d_{n-2} + d_{n-1} \)

und unsere Summenformel vereinfacht sich zu

\( a_n = b_n + d_{n+1} \)

Eine zulässige Lösung wäre also

\( b_n = 2^{n+1} - d_{n+1} \), ohne Rekursion.

\( d_n = d_{n-2} + d_{n-1} \), analog Fibonacci.

rodion26 · Answer 2 · 2020-08-21T01:15:46Z

0

Mit etwas mehr Arbeit bekommt man auch noch eine rein rekursive Formel für \(b_n\). Zuerst drehen wir die vorletzte Gleichung um, \( d_n = 2^n - b_{n-1} \), und setzen das ein

\[ b_n = 2^{n+1} - d_{n} - d_{n-1} = 2^{n+1} - (2^{n} - b_{n-2}) - (2^{n-1} - b_{n-1}) = 2^{n-1} + b_{n-2} + b_{n-1} \]

Ist es nicht schön! Leider kann man jetzt gar nicht mehr erkennen, wie die Formel mit den Folgen zusammenhängt.

Teilen Diese Antwort melden Link

geantwortet 21.08.2020 um 01:15

rodion26
Sonstiger Berufsstatus, Punkte: 242

Kommentar schreiben