Rekursionsgleichung für mindestens zwei aufeinanderfolgende Einsen

22.03.2021, 18:06	gonzo91	Auf diesen Beitrag antworten »
Rekursionsgleichung für mindestens zwei aufeinanderfolgende Einsen Hallo zusammen, ich bin bei der Klausurvorbereitung über folgende Aufgabe gestolpert und komme auch nach intensivem Überlegen nicht auf die Lösung. Gesucht ist $\begin{eqnarray} x_n \end{eqnarray}$ , die Anzahl der Wörter mit Länge $\begin{eqnarray} n \end{eqnarray}$ über dem Alphabet $\begin{eqnarray} \{1,2,3,4\} \end{eqnarray}$ , die mindestens zwei aufeinanderfolgende Einsen enthalten. Nun soll eine Rekursionsgleichung für $\begin{eqnarray} x_n \end{eqnarray}$ gefunden werden. Meine Überlegungen bisher: $\begin{eqnarray} x_0 = x_1 = 0 \end{eqnarray}$ und $\begin{eqnarray} x_2 = 1 \end{eqnarray}$ sind trivial. Für $\begin{eqnarray} x_3 \end{eqnarray}$ habe ich mir überlegt, dass es in $\begin{eqnarray} x_2 \end{eqnarray}$ Wörter der Form X1 und 1X gibt. Für X1 habe ich 4 Möglichkeiten für ein Wort mit 11 und für 1X habe ich 3 Möglichkeiten. Im nächsten Schritt gilt das analog, so dass ich auf die Formel $\begin{eqnarray} x_n = 4^{n-2} + 3^{n-2} \end{eqnarray}$ komme. Jetzt bin ich mir aber einerseits unsicher, ob das überhaupt so stimmt und andererseits ist das natürlich keine rekursive Definition. Stehe auf dem Schlauch und wäre für etwas Input dankbar.
22.03.2021, 19:17	HAL 9000	Auf diesen Beitrag antworten »
Zählen wir doch mal alle Möglichkeiten durch mit mindestens einmal Sequenz 11 unter den ersten $\begin{eqnarray} n \end{eqnarray}$ Ziffern. Im Fall $\begin{eqnarray} n\geq 2 \end{eqnarray}$ gibt es folgende disjunkten Fälle für zwei Endziffern: Fall 1) Letzte Ziffer ist nicht 1: Anzahl Möglichkeiten $\begin{eqnarray} 3x_{n-1} \end{eqnarray}$ Fall 2) Letzte Ziffer ist 1. Der Fall wird weiter aufgeteilt: Fall 2.1) Vorletzte Ziffer ist nicht 1: Anzahl Möglichkeiten $\begin{eqnarray} 3x_{n-2} \end{eqnarray}$ Fall 2.2) Vorletzte Ziffer ist 1: Anzahl Möglichkeiten $\begin{eqnarray} 4^{n-2} \end{eqnarray}$ Summa summarum ergibt das die Rekursionsgleichung $\begin{eqnarray} x_n = 3\left(x_{n-1} + x_{n-2}\right) + 4^{n-2} \end{eqnarray}$ mit den Startwerten $\begin{eqnarray} x_0=x_1=0 \end{eqnarray}$ . Damit bekommt man die weiteren Werte $\begin{eqnarray} x_2 = 1 \end{eqnarray}$ $\begin{eqnarray} x_3 = 7 \end{eqnarray}$ $\begin{eqnarray} x_4 = 40 \end{eqnarray}$ $\begin{eqnarray} x_5 = 205 \end{eqnarray}$ . Aus dieser rekursiven Formel kann man auch eine explizite entwickeln - allerdings hat diese keinen sonderlich angenehmen Anblick: $\begin{eqnarray} x_n = 4^n-\frac{1}{3\sqrt{21}} \left[ \left(\frac{3+\sqrt{21}}{2}\right)^{n+2} - \left(\frac{3-\sqrt{21}}{2}\right)^{n+2}\right] \end{eqnarray}$ . P.S.: Man hätte auch statt $\begin{eqnarray} x_n \end{eqnarray}$ sich zunächst der Anzahl $\begin{eqnarray} y_n \end{eqnarray}$ aller Wörter der Länge $\begin{eqnarray} n \end{eqnarray}$ widmen können, welche nicht diese Sequenz 11 aufweisen. Da besteht ja offensichtlich der Zusammenhang $\begin{eqnarray} y_n = 4^n-x_n \end{eqnarray}$ , und für die Rekursion kann man (fast genauso wie oben argumentierend) die Gleichung $\begin{eqnarray} y_n = 3\left(y_{n-1}+y_{n-2}\right) \end{eqnarray}$ für $\begin{eqnarray} n\geq 2 \end{eqnarray}$ aufstellen, mit den Startwerten $\begin{eqnarray} y_0=1,y_1=4 \end{eqnarray}$ . Der Vorteil dieses Zugangs ist, dass man gleich von Anfang an eine homogene Differenzengleichung hat, also nicht eine inhomogene (d.h. mit Störglied) wie bei $\begin{eqnarray} (x_n) \end{eqnarray}$ .
23.03.2021, 18:42	gonzo91	Auf diesen Beitrag antworten »
Ach ja, so logisch. Vielen Dank für die schnelle Hilfe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »