Vollständige Induktion

19.11.2008, 15:01

pr0xy

Vollständige Induktion

Moin Moin,
leider habe ich eine Aufgebe bei der ich null Ahnung habe wie ich vorgehen soll.

Es seien $\begin{eqnarray*} a , b \in \mathbb R \end{eqnarray*}$ . Wir betrachten die Differnzengleichung zweiter Ordnung

$\begin{eqnarray*} x_{n+1} = ax_{n} + bx_{n-1} \end{eqnarray*}$

mit gegenebenen Anfangsbedingungen $\begin{eqnarray*} x_{0} , x_{1} \in \mathbb R \end{eqnarray*}$ . Beweisen Sie folgende Aussage für alle $\begin{eqnarray*} n \geq 0 \end{eqnarray*}$ durch vollständige Induktion:

Besitzt die charakteristische Gleichung
$\begin{eqnarray*} \lambda^{2}-a\lambda-b=0 \end{eqnarray*}$

die verschiedenen Nullstellen $\begin{eqnarray*} \lambda_{1} \in \mathbb R \text{ und } \lambda \in \mathbb R \end{eqnarray*}$ , so gilt

$\begin{eqnarray*} x_{n}= \frac{1}{\lambda_{1}-\lambda_{2}}((\lambda_{2}x_{0}-x_{1})\lambda^{n}_{1}+(x_{1}-\lambda_{1}x_{0})\lambda^{n}_{2}), n \in \mathbb N_{0} \end{eqnarray*}$

Wir haben als Tipp bekommen das mit Vollständiger Induktion zu machen und das der Induktionsanfang zwei Werte hat.

Leider habe ich dieses mal keine Ahnung was ich machen muss irgendwie sieht das alles anders aus als das was in der Vorlesung vorgekommen ist.

Was soll ich den hier überhaupt machen? was hat $\begin{eqnarray*} x_{n+1} = ax_{n} + bx_{n-1} \end{eqnarray*}$ mit $\begin{eqnarray*} \lambda^{2}-a\lambda-b=0 \end{eqnarray*}$ zu tun?

Danke für eure Hilfe.

Gruß pr0xy

19.11.2008, 15:31

tigerbine

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Ich kann dir leider gerade bei der Induktion nicht helfen, aber Ziel der Aufgabe ist es wohl, xn direkt aus den Anfangswerten x0, x1 zu berechnen, anstatt die Dreitermrekursion zu verwenden.

Inwieweit man dafür die verschiedenen Nullstellen der quadratischen Gleichung braucht, kann ich dir nicht sagen. Vielleicht füllst du die Aufgabe mal mit Beispielwerten. GGf. erkennt man den Trick dann leichter.

Gruß Wink

19.11.2008, 15:50

pr0xy

Auf diesen Beitrag antworten »

Alles klar ich probiere das mal... Auch wenn ich die Aufgabe morgen Abgeben muss, das ist mir egal. Ich möchte sie nur gerne verstehen..

19.11.2008, 16:41

Reksilat

Auf diesen Beitrag antworten »

In der expliziten Vorschrift für $\begin{eqnarray*} x_n \end{eqnarray*}$ ist wohl ein Vorzeichenfehler drin. (Sieht man schnell, wenn man sie für n=0 und n=1 überprüft, wahrscheinlich einfach ein Minus vor den ganzen Ausdruck setzen)

Das hilft aber nur bedingt, deshalb noch ein Tipp:
Es ist $\begin{eqnarray*} \lambda^2-a\lambda-b=0 \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_1,\lambda_2 \end{eqnarray*}$ sind die Nullstellen. Also kann ich das Polynom ja auch als $\begin{eqnarray*} (\lambda-\lambda_1)(\lambda-\lambda_2) \end{eqnarray*}$ schreiben. Damit sollte Dir ein weiterer Zusammenhang zwischen a und b und den Lambdas auffallen.

Beispielwerte helfen meiner Meinung nach nicht wirklich weiter. Zunge

Wenn Du nicht weiterkommst, würde ich als Anfang eher mal das ganze für n=2 nachrechnen. (Also den Induktionsanfang machen)

19.11.2008, 17:20

pr0xy

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
In der expliziten Vorschrift für $\begin{eqnarray*} x_n \end{eqnarray*}$ ist wohl ein Vorzeichenfehler drin. (Sieht man schnell, wenn man sie für n=0 und n=1 überprüft, wahrscheinlich einfach ein Minus vor den ganzen Ausdruck setzen)

Was meinst du damit? soll ich ein Fahler beim Abschreiben gemacht habe?
Wenn du das meinst, nein ich habe das genau so auf meine Zettel stehen.

Aber auch egal.. ich verstehe leider immer noch Bahnhof.

Also eine einfachere Aufgabe zum Verständniss der Vollständigen Induktion

Zeigen Sie, dass $\begin{eqnarray*} \sum_{k=0}^n~\binom n k = 2^n \text { für alle } n = 1,2,.. \text { gilt.} \end{eqnarray*}$

$\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^1~\binom n k = \frac {1!} {0! (1 - 0)!} + \frac {1!}{1!(1-1)!} = 2^1 \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=0}^{n+1}~\binom n k = \sum_{k=0}^n~\binom n k + \binom {n+1} {k} = 2^{n}+ \binom {n+1} {k} = 2^{n}+ \frac {(n+1)!}{k!((n+1)-k)!} \end{eqnarray*}$

aber wie komme ich jetzt weiter ich brauche ja $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$

19.11.2008, 18:21

Reksilat

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Welche Aufgabe soll den nun gelöst werden? verwirrt

Zitat:

Was meinst du damit? soll ich ein Fahler beim Abschreiben gemacht habe? Wenn du das meinst, nein ich habe das genau so auf meine Zettel stehen.

Woher soll ich wissen woher der Fehler kommt? Ein Vorzeichenfehler ist trotzdem drin! Setze soch einfach n=0, dann steht auf der linken Seite $\begin{eqnarray*} x_0 \end{eqnarray*}$ und auf der rechten:
$\begin{eqnarray*} \frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-x_{1}+x_{1}-\lambda_{1}x_{0})=-x_0 \end{eqnarray*}$
Mit $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ genau das gleiche und ich nehme an, dass sich das so fortführt, habe die Aufgabe nur noch nicht komplett gerechnet.

Zitat:

Also eine einfachere Aufgabe zum Verständniss der Vollständigen Induktion

Was soll das?
a) Du verstehst vollständige Induktion, dann bringen Dich andere Aufgaben nicht weiter.
b) Du verstehst sie nicht, dann ist aber auch dieses Problem ungeeignet sie zu verstehen und Du solltest eher mal in den Workshop schauen: Klick!
In diesem Beitrag wird sogar Dein Beispiel erläutert (Setze dabei a=b=1)

19.11.2008, 19:26

pr0xy

Auf diesen Beitrag antworten »

Also die Vollständige Induktion verstehe ich schon nur zum ende komme ich dann irgend wie immer nicht.

Ich verstehe nicht so ganz was mir diese Gleichung bringt.

$\begin{eqnarray*} x_{0} = \frac{1}{\lambda_{1}-\lambda_{2}}((\lambda_{2}x_{0}-x_{1})\lambda^{0}_{1}+(x_{1}-\lambda_{1}x_{0})\lambda^{0}_{2}) \end{eqnarray*}$
$\begin{eqnarray*} x_{0} = \frac{1}{\lambda_{1}-\lambda_{2}}((\lambda_{2}x_{0}-x_{1})+(x_{1}-\lambda_{1}x_{0})) \end{eqnarray*}$
$\begin{eqnarray*} x_{0} = \frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-x_{1}+x_{1}-\lambda_{1}x_{0}) \end{eqnarray*}$
$\begin{eqnarray*} x_{0} =\frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-\lambda_{1}x_{0}) \end{eqnarray*}$

darf ich das?

aber wie kommst du auf
$\begin{eqnarray*} \frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-x_{1}+x_{1}-\lambda_{1}x_{0})=-x_0 \end{eqnarray*}$

gruß pr0xy

19.11.2008, 19:39

Reksilat

Auf diesen Beitrag antworten »

Zitat:

aber wie kommst du auf
$\begin{eqnarray*} \frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-x_{1}+x_{1}-\lambda_{1}x_{0})=-x_0 \end{eqnarray*}$

Nicht wirklich oder?
Wenn Du $\begin{eqnarray*} \frac{1}{\lambda_{1}-\lambda_{2}}(\lambda_{2}x_{0}-\lambda_{1}x_{0})=-x_0 \end{eqnarray*}$ nicht zeigen kannst, dann habe ich grad' gar keine Lust Dir weiterzuhelfen. Schau Dir das in Ruhe an, Mach das gleiche für $\begin{eqnarray*} x_1 \end{eqnarray*}$ und dann melde Dich nochmal.

19.11.2008, 19:44

pr0xy

Auf diesen Beitrag antworten »

alles klar danke.. versuche das den ganzen tag schon zu verstehen.. gebe mir sehr viel mühe mit der darstellung und dann so was wie.. na wenn du es nicht verstehst.. selber schuld..

19.11.2008, 19:58

Auf diesen Beitrag antworten »

Du kannst jetzt den Trotz herauskehren, aber ich kann Reksilat nur beipflichten:

Irgendwann ist Schluss - wer auch noch so klitzekleine Schritte wie diese Vereinfachung weiter zerlegt haben will, dem muss man die Hochschulreife absprechen. Diese Vereinfachung ist Schulniveau, allenfalls 8./9.Klasse.

19.11.2008, 20:21

pr0xy

Auf diesen Beitrag antworten »

Alles klar.. sorry aber ich sehe es einfach gerade nicht.. ich mache dann morgen weiter..

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen