Rekursionsfrei Darstellung einer Folge

03.07.2011, 17:43

chillerStudent

Auf diesen Beitrag antworten »

Rekursionsfrei Darstellung einer Folge

Hallo,

ich muss eine rekursionsfreie Darstellung der Folge $\begin{eqnarray*} (x_n)_n \end{eqnarray*}$ finden, mit $\begin{eqnarray*} x_0=1, x_1=1 \end{eqnarray*}$ und $\begin{eqnarray*} x_n=3x_{n-1}-2x_{n-2} \end{eqnarray*}$

In meinem Skript steht nur ein Beispiel mit einer Fibonacci-Folge.
Sinngemäß heißt es da:

Nimm an, dass p(x) über C verschiedene NS $\begin{eqnarray*} \lambda...\lambda_k \end{eqnarray*}$ mit jeweils der Vielfachheit = 1 hat. Dann gibt es $\begin{eqnarray*} \alpha...\alpha_n \end{eqnarray*}$ € C, sodass $\begin{eqnarray*} x_n=\alpha_1 \lambda_1^n+...+\alpha_k \lambda_k^n \end{eqnarray*}$ eine folge definiert, die Rekursions-gleichung und Anfangsbedingung erfüllt.

Wie finde ich nun mein p(x). Man sagt, mit dem charakteristischem Polynom?

Wie gehe ich da vor?

03.07.2011, 18:25

HAL 9000

Auf diesen Beitrag antworten »

Bei dieser Rekursion und diesen ganz speziellen Anfangswerten würde ich an deiner Stelle einfach mal $\begin{eqnarray*} x_2,x_3,x_4 \end{eqnarray*}$ ausrechnen und dann eine Vermutung aufstellen... Augenzwinkern

Augenzwinkern

03.07.2011, 18:34

chillerStudent

Auf diesen Beitrag antworten »

Die Vermutung lautet: $\begin{eqnarray*} x_2=x_3=x_4=...=x_n=1 \end{eqnarray*}$

Was nun?

03.07.2011, 18:35

HAL 9000

Auf diesen Beitrag antworten »

Wie "was nun" ? Z.B. Beweis per vollständiger Induktion, wie man diesen Einzeiler vornehm nennen könnte. Augenzwinkern

Augenzwinkern

03.07.2011, 18:41

chillerStudent

Auf diesen Beitrag antworten »

mhh... es ist verlangt, dass ich das mit dem ich oben genannten sinngemäßen Satz den Beweis zeige. Ich vertehe aber diesen Satz leider nicht so.

03.07.2011, 19:06

chillerStudent

Auf diesen Beitrag antworten »

hat die Funktion $\begin{eqnarray*} x_n=3x_{n-1}-2x_{n-2} \end{eqnarray*}$ folgende charakteristisches Polynom?

$\begin{eqnarray*} x^2-x-1 \end{eqnarray*}$

edit:
nein doch nicht, hab noch mal geguckt. Nun meine ich, dass das ch. Pol. x^2-3x+2 ist.
stimmt das?

Anzeige

03.07.2011, 19:24

Math1986

Auf diesen Beitrag antworten »

Ich würde diese Aussage direkt per vollständiger Induktion beweisen anstatt hier mit Kanonen auf Spatzen zu schießen Augenzwinkern

Augenzwinkern

03.07.2011, 19:34

chillerStudent

Auf diesen Beitrag antworten »

Ich würde das gerne so machen, wir ihr hier es vorschlagt, aber die aufgabenstellung lautet so. traurig

traurig

Habe nun eine Formel hinbekommen, weiß aber nicht genau ob sie stimmt.

$\begin{eqnarray*} F_n=1*\left(\frac{3}{2}+\frac{1}{2} \right)^n - 1*\left(\frac{3}{2}-\frac{1}{2}\right)^n \end{eqnarray*}$

03.07.2011, 19:53

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von chillerStudent
Ich würde das gerne so machen, wir ihr hier es vorschlagt, aber die aufgabenstellung lautet so. traurig

traurig

Und wie lautet sie genau? böse

böse

03.07.2011, 19:56

chillerStudent

Auf diesen Beitrag antworten »

Finden Sie mit Hilfe des Satzes in Kapitel IV.2. eine rekursionsfreie Darstellung der Folge...

Den Satz hab ich sinngemäß oben im ersten Beitrag hingeschrieben.

03.07.2011, 20:01

chillerStudent

Auf diesen Beitrag antworten »

das ch. Pol. hab ich laut wiki (http://de.wikipedia.org/wiki/Fibonacci-F...on_Moivre-Binet abgelesen.
$\begin{eqnarray*} x^2-3x+2 \end{eqnarray*}$

03.07.2011, 20:14

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von chillerStudent
Finden Sie mit Hilfe des Satzes in Kapitel IV.2. eine rekursionsfreie Darstellung der Folge...

Den Satz hab ich sinngemäß oben im ersten Beitrag hingeschrieben.

Ja, und wo steht dass du das nicht durch Induktion beweisen darfst?
Wie sieht besagter Satz aus?
Muss man dir wirklich jede Information aus der Nase ziehen?
Wenn du unbedingt über das char. Polynom argumentieren willst, bitte schön

03.07.2011, 20:34

chillerStudent

Auf diesen Beitrag antworten »

Zitat:

Sinngemäß heißt es da: Nimm an, dass p(x) über C verschiedene NS $\begin{eqnarray*} \lambda...\lambda_k \end{eqnarray*}$ mit jeweils der Vielfachheit = 1 hat. Dann gibt es $\begin{eqnarray*} \alpha...\alpha_n \end{eqnarray*}$ € C, sodass $\begin{eqnarray*} x_n=\alpha_1 \lambda_1^n+...+\alpha_k \lambda_k^n \end{eqnarray*}$ eine folge definiert, die Rekursions-gleichung und Anfangsbedingung erfüllt.

Ich glaube das heißt, wenn es ein chark. Polynom gibt dessen NS die Vielfachheit 1 ist, dann gibt es eine Folge $\begin{eqnarray*} x_n=\alpha_1 \lambda_1^n+...+\alpha_k \lambda_k^n \end{eqnarray*}$ , die die Anfangsbedinung und lin. Rek. Gleichung k-ter Ordnung erfüllt.

So bin ich jetzt rangegangen:

Wie schon gesagt, das chark. Poly. hab ich abgelesen: $\begin{eqnarray*} x^2-3x+2 \end{eqnarray*}$
Davon die NS sind 2 und 1. Laut definition setze ich dies in die Folge ein:

$\begin{eqnarray*} x_n=\alpha_1(2)^n+\alpha_2(1)^n \end{eqnarray*}$

$\begin{eqnarray*} F_0=0 >> \alpha_1+\alpha_2=0 >> \alpha_1=-\alpha_2 \end{eqnarray*}$

$\begin{eqnarray*} F_1=1 >> \alpha_1(2)^1+\alpha_2(1)^1=1 >> \alpha_2=-1 >> \alpha_1=1 \end{eqnarray*}$

$\begin{eqnarray*} F_n=1*(2)^n-1*(1)^n >> 1*[(2)^n-(1)^n] \end{eqnarray*}$

03.07.2011, 21:03

HAL 9000

Auf diesen Beitrag antworten »

Was soll das mit dem $\begin{eqnarray*} F_n \end{eqnarray*}$ ? So hieß die Folge vielleicht in deiner Beispielvorlage, hier geht es aber um $\begin{eqnarray*} x_n \end{eqnarray*}$ . Und da ist

Zitat:

Original von chillerStudent
$\begin{eqnarray*} F_0=0 >> \alpha_1+\alpha_2=0 >> \alpha_1=-\alpha_2 \end{eqnarray*}$

übersetzt eben nicht $\begin{eqnarray*} x_0=0 \end{eqnarray*}$ , sondern $\begin{eqnarray*} x_0=1 \end{eqnarray*}$ vorgegeben! Ist es nicht so?

03.07.2011, 21:12

chillerStudent

Auf diesen Beitrag antworten »

In der Beispielvorlage geht es auch um $\begin{eqnarray*} x_n \end{eqnarray*}$ und wegen fibonacci-folge wurde aus $\begin{eqnarray*} x_n \end{eqnarray*}$ >> $\begin{eqnarray*} F_n \end{eqnarray*}$

ups, ja stimmt. Es heißt $\begin{eqnarray*} x_n=1 \end{eqnarray*}$ . Sry hab das ganze einfach strikt nach dem Beispiel gemacht.

Wenn ich jetzt das hier $\begin{eqnarray*} F_0=1 >> \alpha_1=1-\alpha_2 \end{eqnarray*}$ in die Gleichung einsetzte komme ich auf $\begin{eqnarray*} \alpha_2=1 \end{eqnarray*}$

03.07.2011, 21:18

HAL 9000

Auf diesen Beitrag antworten »

Verrechnen ist die eine Sache, kommt vor. Aber es ist traurig, dass du nicht die einfachsten Kontrollmechanismen anwendest:

Du wusstest seit oben, dass die Folge konstant gleich 1 ist, und trotzdem bietest du kritiklos deine dann offensichtlich falsche Lösung

Zitat:

Original von chillerStudent
$\begin{eqnarray*} F_n=1*(2)^n-1*(1)^n >> 1*[(2)^n-(1)^n] \end{eqnarray*}$

übersetzt $\begin{eqnarray*} x_n=2^n-1 \end{eqnarray*}$ hier an? Mir ziemlich unverständlich. unglücklich

unglücklich

03.07.2011, 21:22

chillerStudent

Auf diesen Beitrag antworten »

Ok. Ich würde gerne ganz von anfang an beginnen und möchte/muss über das char. Poly. arbeiten.
Stimmt das Poly. : $\begin{eqnarray*} x^2-3x+2 \end{eqnarray*}$

03.07.2011, 21:24

HAL 9000

Auf diesen Beitrag antworten »

Ja, ja, das ist in Ordnung - obwohl ich nach deinen obigen Bezeichnungen eher mit $\begin{eqnarray*} \lambda \end{eqnarray*}$ als mit $\begin{eqnarray*} x \end{eqnarray*}$ arbeiten würde, also $\begin{eqnarray*} p(\lambda)=\lambda^2-3\lambda+2 \end{eqnarray*}$ .

Wenn es dir was bringt, dann schreib eben alles nochmal ordentlich auf.

03.07.2011, 21:31

chillerStudent

Auf diesen Beitrag antworten »

dann sind die NS davon $\begin{eqnarray*} \lambda_1=1, \lambda_2=2 \end{eqnarray*}$

Laut definition gibt es eine Folge $\begin{eqnarray*} x_n=\alpha_1 \lambda_1^n+...+\alpha_k \lambda_k^n \end{eqnarray*}$

Das heißt:

$\begin{eqnarray*} x_n=\alpha_1* 1^n+\alpha_2 *2^n \end{eqnarray*}$

stimmt das ?

03.07.2011, 21:34

HAL 9000

Auf diesen Beitrag antworten »

Ja, alles in Ordnung. (Es war nur der eine Fehler $\begin{eqnarray*} x_0 = 0 \end{eqnarray*}$ statt $\begin{eqnarray*} x_0 = 1 \end{eqnarray*}$ einzusetzen.)

03.07.2011, 21:42

chillerStudent

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x_0=\alpha_1+\alpha_2=1 >> \alpha_1=1-\alpha_2 \end{eqnarray*}$

$\begin{eqnarray*} x_1=\alpha_1+2\alpha_2=1 >> \alpha_2=0 \end{eqnarray*}$

komisch?

03.07.2011, 21:45

HAL 9000

Auf diesen Beitrag antworten »

Was ist daran komisch? Es ist das erwartete Resultat.

03.07.2011, 21:48

chillerStudent

Auf diesen Beitrag antworten »

wenn ich für $\begin{eqnarray*} \alpha_2=1-\alpha_1 \end{eqnarray*}$ einsetze dann ist $\begin{eqnarray*} \alpha_1=1 \end{eqnarray*}$

ist das richtig?

03.07.2011, 21:50

HAL 9000

Auf diesen Beitrag antworten »

Ja.

Ich möchte dich aber höflich drauf hinweisen, dass dies hier kein Chatroom ist. Du darfst auch mal zwei, drei Minischritte in einem Beitrag machen, statt nur einen.

03.07.2011, 21:55

chillerStudent

Auf diesen Beitrag antworten »

Ok.

Dann ist $\begin{eqnarray*} x_n=1*1^n \end{eqnarray*}$ .
Danke dir vielmals!!!!!!

03.07.2011, 22:00

HAL 9000

Auf diesen Beitrag antworten »

Was man üblicherweise auch einfach als $\begin{eqnarray*} x_n=1 \end{eqnarray*}$ schreibt, womit sich der Kreis endlich schließt. Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »