Vollständige Induktion

17.11.2018, 15:18	FelixRTU	Auf diesen Beitrag antworten »
Vollständige Induktion Meine Frage: Für eine natürliche Zahl n definieren wir die n-te Fibonacci-Zahl rekursiv über F(n)=F(n-1)+F(n-2) mit den Anfangsbedingungen F(0)=F(1)=1. (a) Beweisen Sie mittels vollständiger Induktion, dass die folgende Gleichung für alle n>=1 gilt: F(n)F(n+1)-F(n-1)F(n+2)=(-1)^n . (b) Für eine natürliche Zahl n>=1 betrachten wir ein rechteckiges Brett mit Seitenlängen 2 und n. Ein Domino ist ein rechteckiger Spielstein mit Seitenlängen 1 und 2. Zeigen Sie mittels vollständiger Induktion, dass es genau F(n) Möglichkeiten gibt, das Brett mit exakt n Dominos zu überdecken. Meine Ideen: zu a: IA: n=1, F(1)F(1+1)-F(1-1)F(1-2)=-1=(-1)^1 IV: F(n)F(n+1)-F(n-1)F(n+2)=(-1)^n IS: ???=(-1)^(n+1) zu b: Ich habe die Menge der Möglichkeiten m(n) genannt, bin mir aber unsicher, ob das legitim ist. IA: n=1, m(1)=1=F(1-1)+F(1-2) IV: m(n)=F(n-1)+F(n-2) IS: ???=F((n+1)-1)+F((n+1)-2)
17.11.2018, 19:46	Leopold	Auf diesen Beitrag antworten »
Die Induktionsbehauptung ist $\begin{align} F(n+1) F(n+2) - F(n) F(n+3) = (-1)^{n+1} \end{align}$ Um das zu zeigen, habe ich mit der linken Seite begonnen und für $\begin{align} F(n+1) \end{align}$ und $\begin{align} F(n+3) \end{align}$ die Rekursionsvorschrift eingesetzt. Nach Ausmultiplizieren und Vereinfachen erhielt ich einen aufschlußreichen Term.
18.11.2018, 14:39	FelixRTU	Auf diesen Beitrag antworten »
$\begin{eqnarray} F(n+1)=F(n)+F(n-1) \end{eqnarray}$ $\begin{eqnarray} F(F+3)=(n+2)+F(n+1) \end{eqnarray}$ $\begin{eqnarray} (F(n)+F(n-1))F(n+2)-F(n)(F(n+2)+F(n+1)) \end{eqnarray}$ $\begin{eqnarray} F(n+2)(F(n)+F(n-1)F(n+2)-F(n)F(n+2)+F(n)F(n+1) \end{eqnarray}$ (Ausmultipliziert) $\begin{eqnarray} F(n-1)F(n+1)-F(n)F(n+1)=(-1)^2 \end{eqnarray}$ (Vereinfacht) Und jetzt? Ich sehe nicht wie mich das zur Lösung führt.
18.11.2018, 14:44	Leopold	Auf diesen Beitrag antworten »
Der vereinfachte Term stimmt nicht (vielleicht ist es nur ein Schreibfehler). Und wie du auf $\begin{align} (-1)^2 \end{align}$ kommst, ist mir schleierhaft. Die Induktionsverankerung sagt etwas anderes.
19.11.2018, 13:42	FelixRTU	Auf diesen Beitrag antworten »
Ja, da haben sich zwei Schreibfehler eingeschlichen So ist es richtig: $\begin{eqnarray} (F(n)+F(n-1))F(n+2)-F(n)(F(n+2)+F(n+1)) \end{eqnarray}$ $\begin{eqnarray} F(n+2)(F(n)+F(n-1)F(n+2)-F(n)F(n+2)+F(n)F(n+1) \end{eqnarray}$ (Ausmultipliziert) $\begin{eqnarray} F(n-1)F(n+2)-F(n)F(n+1)=(-1)^{n+1} \end{eqnarray}$ (Vereinfacht)
19.11.2018, 13:58	HAL 9000	Auf diesen Beitrag antworten »
In der zweiten Zeile sind immer noch zwei Fehler: Die überzählige öffnende Klammer kann man noch als Schreibfehler verbuchen, aber der zweite Fehler hinten ist schlicht falsche Klammerauflösung. Richtig ist insgesamt $\begin{eqnarray} (F(n)+F(n-1))F(n+2)-F(n)(F(n+2)+F(n+1)) \end{eqnarray}$ $\begin{eqnarray} = F(n+2) F(n)+F(n-1)F(n+2)-F(n)F(n+2)-F(n)F(n+1) \end{eqnarray}$ (Ausmultipliziert) Und die Umformung sollte nach Streichung der sich weghebenden $\begin{eqnarray} F(n)F(n+2) \end{eqnarray}$ weitergehen mit $\begin{eqnarray} = -\left(F(n)F(n+1)-F(n-1)F(n+2)\right) \end{eqnarray}$ . Dann erst ist die Zeit reif, nun die Induktionsvoraussetzung heranzuziehen!
Anzeige

19.11.2018, 19:29	FelixRTU	Auf diesen Beitrag antworten »
Vielen Dank, jetzt ist es vollbracht. $\begin{eqnarray} -(F(n)F(n+1)-F(n-1)F(n+2))=(-1)^{n+1} \end{eqnarray}$ nach einsetzen der IV $\begin{eqnarray} -((-1)^n) = (-1)^{n+1} \end{eqnarray}$ Soll/kann ich Aufgabe b noch mal extra posten, oder habt Ihr da noch Ideen?
19.11.2018, 20:43	Leopold	Auf diesen Beitrag antworten »
[attach]48370[/attach]

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »