TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 256

Stellen Sie eine Rekursion für die gesuchten Zahlen $a_n$ auf und lösen Sie diese:

Es sei $a_n$ die Anzahl aller Folgen der Länge $n$ aus 0 und 1, die keine zwei aufeinanderfolgenden Einser enthalten.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches von Har203

Differenzengleichung

In der Mathematik wird durch eine Differenzengleichung (auch als Rekursionsgleichung bezeichnet) eine Folge rekursiv definiert. Das heißt, dass jedes Folgenglied eine Funktion der vorhergehenden Folgenglieder ist:

$x_n=f(n,x_{n-1},x_{n-2},\dots ,x_{n-k})$

für natürliche Zahlen $n$. Die bekanntesten Beispiele sind die Fakultätsfunktion und die Fibonacci-Folge. Eine Spezialform sind die linearen Differenzengleichungen.

Lineare Differenzengleichung

Lineare Differenzengleichungen (auch lineare Rekursionsgleichungen, selten C-Rekursionen oder lineare Rekurrenz von engl. linear recurrence relation) sind Beziehungen einer besonders einfachen Form zwischen den Gliedern einer Folge.

Allgemeine Theorie Eine allgemeine lineare Differenzengleichung $k$-ter Ordnung über einem Körper $𝕂$ ist von der Form

$\sum _{i=0}^k{a}_i(n)f_{n-i}=b(n),$

wobei $a_i(n)\in 𝕂,a_0(n)\ne 0,n\in \mathbb{N},n\ge k$. Die lineare Differenzengleichung wird dabei von den Koeffizienten-Funktionen $a_0,a_1,\dots ,a_k:{\mathbb{N}}_{\ge k}\to 𝕂$ und der Funktion $b:{\mathbb{N}}_{\ge k}\to 𝕂$ charakterisiert.

Ohne Beschränkung der Allgemeinheit kann $a_0(n)=-1$ angenommen werden; das sieht man, weil man alle Koeffizienten und $b(n)$ einfach durch $-a_0(n)\ne 0$ teilen kann. Nach Umstellen erhält man eine alternative Darstellung, die die Berechnungsvorschrift für $f_n$ aus den $k$ vorhergehenden Werten anschaulicher verdeutlicht:

$f_n=a_1(n)f_{n-1}+\dots +a_k(n)f_{n-k}-b(n),$

wobei $a_i(n)\in 𝕂,n\in \mathbb{N},n\ge k$, also

$f_n=c(n)+\sum _{i=1}^k{a}_i(n)f_{n-i},$

wenn man $c(n):=-b(n)$ setzt.

Eine Zahlenfolge $F=(f_0,f_1,f_2,\dots )$, die für alle $n\ge k$ die Gleichung erfüllt, heißt Lösung der Differenzengleichung. Offenbar ist eine Lösung durch ihre $k$ Anfangswerte $f_0,f_1,\dots ,f_{k-1}$ also eindeutig bestimmt – das kann man aus der alternativen Form direkt ablesen. Ist $b(n)=0$ für alle $n\ge k$, so heißt die Gleichung Gleichungen homogen, ansonsten heißt sie inhomogen. Die Zahlenfolge $f_n=0$ für alle $n$ erfüllt alle homogenen Gleichungen und heißt deshalb triviale Lösung.

Rechenregeln

• Sind $F$ und $G$ Lösungen der homogenen linearen Differenzengleichung ${\sum }_{i=0}^k{a}_i(n)f_{n-i}=0$, dann ist auch $\alpha F+\beta G$ für beliebige $\alpha ,\beta \in 𝕂$ eine Lösung.
• Sind $F$ und $G$ Lösungen der inhomogenen linearen Differenzengleichung ${\sum }_{i=0}^k{a}_i(n)f_{n-i}=b(n)$, dann ist $F-G$ eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit $b(n)=0$ für alle $n\ge k$.
• Ist $F$ eine Lösung der inhomogenen linearen Differenzengleichung ${\sum }_{i=0}^k{a}_i(n)f_{n-i}=b(n)$ und $G$ eine Lösung der zugehörigen homogenen linearen Differenzengleichung mit $b(n)=0$ für alle $n\ge k$, dann ist auch $F+\alpha G$ für beliebige $\alpha \in 𝕂$ eine Lösung der inhomogenen linearen Differenzengleichung.

$[\ast ]$ Exzerpt aus dem Originalartikel Lineare Differenzengleichung

• Differenzengleichung
• Differenzenverfahren
• Fibonacci-Zahlen

Lösungsvorschlag von Har203

Wir haben ein binäres Alphabet bestehend aus "0" und "1", die in einer beliebigen Reihenfolge angeordnet werden sollen. Die einzige Einschränkung ist, dass zwei "1"er hintereinander nicht erlaubt sind. Die Zahlenfolge $<a_n>$ gibt dabei an, wie viele unterschiedliche binäre Folgen der Länge $n$ mit dieser Einschränkung erzeugt werden können.

Die Folge im Überblick

Anmerkung: Die leere binäre Folge ohne Zeichen werden wir auch als gültige Folge gelten lassen: $a_0=1$ - (aus mathematischer Sicht nach der Feststellung des Konstruktionsschemas).

Wir schauen uns die ersten Folgen genauer an:

$\begin{array}{cc}{a}_0=1& \\ a_1=2& 0,1\\ a_2=3& 00,01,10\\ a_3=5& 000,001,010,100,101\\ a_4=8& 0000,0001,0010,0100,1000,0101,1001,1010\\ a_5=13& 00000,00001,00010,00100,01000,10000,00101,01001,10001,01010,10010,10100,10101\end{array}$

Aus der Entwicklung der ersten binären Folgen kann man das Schema schon erkennen:

1. Endet eine Folge mit einem "0"er, dann kann jede weitere Ziffer folgen. Vor der "0" können alle $a_{n-1}$ gültigen Folgen stehen.
2. Endet eine Folge hingegen mit einem "1"er, dann muss vor diesem letzten Glied ein "0"er stehen. Das entspricht den $a_{n-2}$ gültigen Folgen vor diesem "0"er. Der binären Folge kann wiederum nur eine "0" nachfolgen.

D.h. die rekursive Zahlenfolge entspricht $<a_n>=<a_{n-1}>+<a_{n-2}>,n\ge 2$. Das ist das gleiche Konstruktionsschema wie die Fibonacci-Folge.

Die speziellen Anfangsbedingungen für diese Rekursion müssen wir uns am Ende des Beispiels noch überlegen. Voraussichtlich $a_0=1$ und $a_1=2$.

Die ersten Fibonacci-Zahlen sind$:(0,1,1,2,3,5,8,13,21,34,55,89,144,\dots )$

Anmerkung: Teils mit „0“ an erster Position, teilweise ohne dieser.

Exponentialansatz

Für lineare Differenzengleichungen mit konstanten Koeffizienten machen wir den Exponentialansatz:

$a_n={\lambda }^n$

Wir setzen in die Rekursion ein, dividieren durch ${\lambda }^{n-2}$, erhalten die quadratische Gleichung dieser Rekursion und lösen diese:

${\lambda }^n={\lambda }^{n-1}+{\lambda }^{n-2}\begin{array}{c}/{\lambda }^{n-2}\end{array}⟹{\lambda }^2=\lambda +1$

Charakteristische Gleichung

Für die charakteristische Gleichung erhalten wir als Lösungen:

${\lambda }_{1,2}=\frac{1}{2}\pm \sqrt{5/4}=\frac{1}{2}\pm \frac{1}{2}\cdot \sqrt{5}=\frac{1}{2}\cdot (1\pm \sqrt{5})$.

Da beide Nullstellen reell und unterschiedlich sind (${\lambda }_1\ne {\lambda }_2$) erhalten wir Lösungen der Form:

$\begin{array}{cc}& a_n^{(h)}=C_1\cdot {\lambda }_1^n+C_2\cdot {\lambda }_2^n=C_1\cdot {\left(\frac{1+\sqrt{5}}{2}\right)}^n+C_2\cdot {\left(\frac{1-\sqrt{5}}{2}\right)}^n,\text{ mit }C1,C_2\in ℝ.\end{array}$

Konstanten bestimmen

Wir müssen noch die Konstanten $C_1,C_2\in ℝ$ bestimmen$:a_0=1$ und $a_1=2$. Dafür setzen wir in die erhaltene Formel ($a_n^{(h)}$) mit $n=0$ bzw. $n=1$ ein und berechnen daraus $a_0$ bzw. $a_1$:

$\begin{array}{ccc}& a_0=1& =C_1\cdot {\left(\frac{1+\sqrt{5}}{2}\right)}^0+C_2\cdot {\left(\frac{1-\sqrt{5}}{2}\right)}^0⟹1=C_1+C_2⟹{𝐂}_{\mathrm{𝟏}}\mathbf{=}\mathbf{(}\mathrm{𝟏}\mathbf{-}{𝐂}_{\mathrm{𝟐}}\mathbf{)}\\ & a_1=2& =C_1\cdot {\left(\frac{1+\sqrt{5}}{2}\right)}^1+C_2\cdot {\left(\frac{1-\sqrt{5}}{2}\right)}^1=(1-C_2)\cdot \left(\frac{1+\sqrt{5}}{2}\right)+C_2\cdot \left(\frac{1-\sqrt{5}}{2}\right)⟹\\ & 0& =\frac{1}{2}+\frac{\sqrt{5}}{2}-C_2\cdot \frac{1}{2}-C_2\cdot \frac{\sqrt{5}}{2}+C_2\cdot \frac{1}{2}-C_2\cdot \frac{\sqrt{5}}{2}-2=\frac{1}{2}+\frac{\sqrt{5}}{2}-C_2\cdot \sqrt{5}-2⟹\\ & {𝐂}_{\mathrm{𝟐}}& =\frac{1+\sqrt{5}-4}{2\cdot \sqrt{5}}=\frac{5-3\cdot \sqrt{5}}{10}\surd \wedge {𝐂}_{\mathrm{𝟏}}=1-C_2=\frac{10}{10}-\frac{5-3\cdot \sqrt{5}}{10}=\frac{5+3\cdot \sqrt{5}}{10}\surd \end{array}$

Die Lösung

Und abschließend noch in die obere Formel $a_n^{(h)}$ einsetzen:

$⟹a_n^{(h)}=\frac{5+3\cdot \sqrt{5}}{10}\cdot {\left(\frac{1+\sqrt{5}}{2}\right)}^n+\frac{5-3\cdot \sqrt{5}}{10}\cdot {\left(\frac{1-\sqrt{5}}{2}\right)}^n$ $◼$

Probe

$\begin{array}{cccccccc}n=& <a_n>=& & n=& <a_n>=& & n=& <a_n>=\\ 0& 1& & 1& 2& & 2& 3\\ 3& 5& & 4& 8& & 5& 13\\ 6& 21& & 7& 34& & 8& 55\end{array}$

Links

Wikipedia:

• Differenzengleichung
• Lineare Differenzengleichung
• Differenzenverfahren
• Fibonacci-Zahlen

Ähnliche Beispiele:

• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_254
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_255
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_257
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_258
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_259
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_260
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_261
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_262

• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_237 bis
• TU_Wien:Algebra_und_Diskrete_Mathematik_VU_(diverse)/Übungen_2025W/Beispiel_253