Rekursive Folge (Abbildung)

19.11.2013, 17:51

Hamude

Auf diesen Beitrag antworten »

Rekursive Folge (Abbildung)

Hallo,
ich habe in der Suche nichts gefunden deswegen probiere ich es mal hier, also folgende Aufgabe.

Sei f: N-->N rekursiv definiert durch f(n+2) = 2f(n+1) - f(n). Finde geschlossene Ausdrücke für f(n) falls:

a) f(1) = 1, f(2) = 2
b) f(1) = 1, f(2) = 3

Meine Frage ist, was genau ist mit "Finde geschlossene Ausdrücke für f(n)" gemeint? Was genau wird von mir hier verlangt?

MfG

19.11.2013, 17:58

Elvis

Auf diesen Beitrag antworten »

Berechne jeweils die ersten 10 Folgenglieder, und es fällt dir wie Schuppen von den Augen.

19.11.2013, 18:18

Hamude

Auf diesen Beitrag antworten »

Ja das habe ich schon gemacht:

a) f(3)=3 , f(4)=4, f(5)=5, f(6)=6, usw...

b) f(3)=5, f(4)=7, f(5)=9, f(6)=11, usw...

Mein Problem ist, was mit der Aufgabenstellung gemeint ist. Was sind denn hier "geschlossene Ausdrücke für f(n)"?

19.11.2013, 18:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hamude
Was sind denn hier "geschlossene Ausdrücke für f(n)"?

Vielleicht ein Beispiel:

Für die rekursiv definierte Folge $\begin{eqnarray*} f(0)=0 \end{eqnarray*}$ und $\begin{eqnarray*} f(n) = f(n-1) + n \end{eqnarray*}$ würde man die explizite Folgendarstellung $\begin{eqnarray*} f(n) = \frac{n(n+1)}{2} \end{eqnarray*}$ als geschlossenen Ausdruck bezeichnen.

19.11.2013, 19:03

Hamude

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Hamude
Was sind denn hier "geschlossene Ausdrücke für f(n)"?

Vielleicht ein Beispiel:

Für die rekursiv definierte Folge $\begin{eqnarray*} f(0)=0 \end{eqnarray*}$ und $\begin{eqnarray*} f(n) = f(n-1) + n \end{eqnarray*}$ würde man die explizite Folgendarstellung $\begin{eqnarray*} f(n) = \frac{n(n+1)}{2} \end{eqnarray*}$ als geschlossenen Ausdruck bezeichnen.

Wie hat man bzw. du dann auf diesen Ausdruck geschlussfolgert?
Ich habe versucht das nachzuvollziehen aber ich sehe einfach nicht wie man da umgeformt hat.

Edit:

Durch mehr oder weniger raten bin ich auf folgende geschlossene Ausdrücke gekommen:

a) f(n) = n
b) f(n) = 2*n - 1

19.11.2013, 19:05

HAL 9000

Auf diesen Beitrag antworten »

Ich wollte demonstrieren, was ein geschlossener Ausdruck ist - nicht, wie man in dieser anderen Aufgabe auf ihn kommt.

P.S.: Das ist hier einfach der kleine Gauß, denn die Rekursion macht ja nichts weiter, als die Zahlen bis n aufzusummieren.

Anzeige

19.11.2013, 19:18

Hamude

Auf diesen Beitrag antworten »

Ich soll noch die Gültigkeit durch volllst. Ind. beweisen. Ich dachte ich kriege das hin aber ich hänge an einer stelle.

$\begin{eqnarray*} f\left(n+2\right) = 2f\left(n+1\right) -f\left(n\right) \end{eqnarray*}$

Vollständige Ind. nach n:

I.V.: für n=0

$\begin{eqnarray*} f\left(2\right) = 2f\left(1\right) -f\left(0\right) \end{eqnarray*}$ (Wie kann ich das hier noch vereinfachen um es zu zeigen?)

I.S.: es gilt für n, dann gilt es auch für n+1

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

Beweis:

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

$\begin{eqnarray*} f\left(n+3\right) = 2(2f\left(n+1\right) -f\left(n\right)) -f\left(n+1\right) \end{eqnarray*}$ (einfach das (f+2) durch die Gleichung oben ersetzt)
$\begin{eqnarray*} f\left(n+3\right) = 4f\left(n+1\right) - 2f\left(n\right) -f\left(n+1\right) \end{eqnarray*}$
$\begin{eqnarray*} f\left(n+3\right) = 3f\left(n+1\right) - 2f\left(n\right) \end{eqnarray*}$

Ab hier komm ich dann nicht mehr weiter, würde mich freuen wenn mir jemand hier einen Tipp geben könnte.

19.11.2013, 19:31

HAL 9000

Auf diesen Beitrag antworten »

Was tust du denn da??? geschockt

geschockt

Die Iterationsgleichung $\begin{eqnarray*} f(n+2) = 2f(n+1) - f(n) \end{eqnarray*}$ ist nicht zu beweisen, deren Gültigkeit ist für alle $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ gegeben!!!

19.11.2013, 19:34

Hamude

Auf diesen Beitrag antworten »

Hey HAL,

Ich habe schon den Ausdruck gefunden, guck mal in meinem EDIT 2 Posts vorher^^.

Die vollständige Aufgabe lautet eig.:

"Sei f: N-->N rekursiv definiert durch f(n+2) = 2f(n+1) - f(n). Finde geschlossene Ausdrücke für f(n) falls:

a) f(1) = 1, f(2) = 2
b) f(1) = 1, f(2) = 3

Beweisen Sie die Gültigkeit mittels vollständiger Induktion"

Hab ich das etwa total falsch gemacht?

19.11.2013, 19:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hamude
Ich habe schon den Ausdruck gefunden, guck mal in meinem EDIT 2 Posts vorher^^.

Ja, sieht gut aus, aber warum tauchen diese Ausdrücke im Induktionsbeweis nicht auf? Diese Darstellung willst du doch beweisen, stattdessen machst du unsinniges Hin- und Hergeschaufel rein auf Basis der Iterationsgleichung. unglücklich

unglücklich

19.11.2013, 19:40

Hamude

Auf diesen Beitrag antworten »

Ah ich soll einmal per Induktion für a) und dann nochmal für b) machen?
Wenn ja, dann habe ich die Aufgabenstellung total falsch verstanden.

Edit: ich habe eben wieder rumprobiert, ich komme einfach nicht weiter unglücklich

unglücklich

19.11.2013, 19:51

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hamude
Ah ich soll einmal per Induktion für a) und dann nochmal für b) machen?

Ja, so in etwa. Mit ein wenig Cleverness könnte man natürlich auch gleich die allgemeinere Darstellung

$\begin{eqnarray*} f(n) = (b-a)n + 2a-b \end{eqnarray*}$

für frei wählbare Anfangswerte $\begin{eqnarray*} f(1)=a,f(2)=b \end{eqnarray*}$ in einem einzigen Beweis nachweisen - dann wären a),b) lediglich Spezialfälle. Augenzwinkern

Augenzwinkern

19.11.2013, 20:07

Hamude

Auf diesen Beitrag antworten »

Kannst du mir auch bitte direkt zeigen wie das geht, darauf wäre ich überhaupt nicht gekommen.
Wäre dir sehr dankbar.

19.11.2013, 20:10

HAL 9000

Auf diesen Beitrag antworten »

Nein, ich verabschiede mich für heute ins Länderspiel (d.h.: Einladung an andere Helfer).

19.11.2013, 21:19

Hamude

Auf diesen Beitrag antworten »

Ich bin am verzweifeln unglücklich

unglücklich

20.11.2013, 12:10

Elvis

Auf diesen Beitrag antworten »

Was gibt es da zu verzweifeln ? Der Induktionsanfang ist doch schon fertig : f(1)=1,f(2)=2.
Du musst nur noch den Induktionsschritt machen.

20.11.2013, 16:34

Hamude

Auf diesen Beitrag antworten »

Ich verstehe aber einfach nicht, was genau ich jetzt machen muss.

20.11.2013, 17:39

Elvis

Auf diesen Beitrag antworten »

Die erste Folge ist anscheinend f(n)=n. Das ist ein geschlossener Ausdruck für die rekursiv definierte Folge.
Induktionsanfang: Für n=1 und n=2 stimmt das, weil f(1)=1 und f(2)=2.
Induktionsschritt: f(n+2)=2f(n+1)-f(n) per definition.
Nach Induktionsvoraussetzung ist f(n)=n und f(n+1)=n+1 , also f(n+2)=2n+2-n=n+2 .
q.e.d.

20.11.2013, 17:51

Hamude

Auf diesen Beitrag antworten »

Ich glaub ich habs jetzt raus, danke.

20.11.2013, 17:57

Elvis

Auf diesen Beitrag antworten »

Was heißt "glaub" ? Für die erste Folge habe ich es bewiesen, das musst du nicht glauben, das weißt du jetzt. Für die zweite Folge musst du die entsprechende Behauptung formulieren und beweisen. Besser wäre es, wenn du den allgemeinen Beweis führst, den HAL 9000 vorgeschlagen hat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »