Erzeugende Funktion bestimmen

28.04.2011, 11:17

Philipp Imhof

Erzeugende Funktion bestimmen

Hallo!

Aus reinem Vergnügen wollte ich heute mal die erzeugende Funktion der Folge $\begin{eqnarray*} x=(n)_{n\in\mathbb N_0}=0,1,2,3,\ldots \end{eqnarray*}$ bestimmen.

Ich kann sie zusammensetzen aus der Folge der Partialsummen der 1-Folge und davon die 1-Folge abziehen, insgesamt also
$\begin{eqnarray*} \frac{1}{(1-z)^2} - \frac{1}{1-z} = \frac{z}{(1-z)^2} \end{eqnarray*}$

Aber ich wollte es auch über die lineare Rekursion versuchen: Die Folge ist rekursiv definiert als
$\begin{eqnarray*} x_0:=0, x_n:=x_{n-1}+1 \end{eqnarray*}$ .

Zuerst die homogene Lösung, via charakteristisches Polynom. Die allgemeine homogene Lösung ist offenbar $\begin{eqnarray*} x_n=\alpha \end{eqnarray*}$ , denn die einzige Nullstelle des charakteristischen Polynoms ist 1.

Die Störfunktion ist eine Konstante, also setze ich für die partikuläre Lösung ebenfalls mit einer Konstanten an: $\begin{eqnarray*} v:=K \end{eqnarray*}$ und dies setze ich in die Rekursionsgleichung ein:
$\begin{eqnarray*} v_n - v_{n-1} = K - K = 1 \end{eqnarray*}$

Wo liegt hier mein Fehler, dass ich auf einen Widerspruch komme?

Danke & Gruss

28.04.2011, 11:54

Mystic

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen

Zitat:

Original von Philipp Imhof
Wo liegt hier mein Fehler, dass ich auf einen Widerspruch komme?

Naja, wenn 1 eine m-fache Nullstelle des charakteristischen Polynoms ist, dann lautet der Ansatz für die partikuläre Lösung natürlich

$\begin{eqnarray*} x_n=An^m \quad (n \in \mathbb N) \end{eqnarray*}$

Noch nie davon gehört? verwirrt

Gehört eigentlich schon zum Standardwissen...

28.04.2011, 12:25

Philipp Imhof

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen
In unserem Skript steht:

Zitat:

Je nach Gestalt der Inhomogenität $\begin{eqnarray*} (d_n)_{n\geq k} \end{eqnarray*}$ existieren verschiedene Techniken. [...] Für $\begin{eqnarray*} d_n=n^k, k\in\mathbb N \end{eqnarray*}$ sei $\begin{eqnarray*} v:=\alpha_k+\alpha_{k-1}n+\cdots+\alpha_0n^k \end{eqnarray*}$

Hier ist die Inhomogenität $\begin{eqnarray*} 1 = n^0 \end{eqnarray*}$ also bleibt mir nach obiger Formel nur $\begin{eqnarray*} v=\alpha_0 \end{eqnarray*}$

Beim Beispiel in unserem Skript (da ist die Störfunktion ein Polynom zweiten Grades) wird analog angesetzt und dann einfach das Ansatz-Polynom in die Rekursion eingesetzt.

Insofern: Nein, von dem, was du (leicht vorwurfsvoll?) schreibst, habe ich noch nichts gehört. Ich sehe jetzt auch nicht, inwiefern ich das aus dem Skript herauslesen könnte.

28.04.2011, 13:40

Mystic

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen

Zitat:

Original von Philipp Imhof
Insofern: Nein, von dem, was du (leicht vorwurfsvoll?) schreibst, habe ich noch nichts gehört. Ich sehe jetzt auch nicht, inwiefern ich das aus dem Skript herauslesen könnte.

Naja, wenn du lieber dem Skript glaubst als mir, dann kann ich wenig dagegen machen... unglücklich

Du könntest aber immerhin versuchen, ob du mit meinem Ansatz dann eine vernünftige partikuläre Lösung rausbekommst... Das wäre zuminindestens einen Versuch wert...

28.04.2011, 14:01

Philipp Imhof

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen
Schon wieder so vorwurfsvoll? Habe ich dir etwas getan?

Es geht nicht darum, dass ich dir nicht glaube, sondern dass ich es nicht wissen kann, wenn ich es irgendwo anders gesehen, gelesen oder gehört habe.

Da ich die Lösung auf zwei andere Arten bestimmen kann, gilt mein Interesse deshalb v.a. der Frage, *warum* dein Ansatz so ist, wie er ist, und wie ich darauf hätte kommen sollen.

28.04.2011, 15:01

Mystic

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen

Zitat:

Original von Philipp Imhof
Schon wieder so vorwurfsvoll? Habe ich dir etwas getan?

Es geht nicht darum, dass ich dir nicht glaube, sondern dass ich es nicht wissen kann, wenn ich es irgendwo anders gesehen, gelesen oder gehört habe.

Ok, Tatsache ist doch, dass es bez. des Ansatzes für die partikuläre Lösung

1. es mit mit dem , welche du aus deinem Skript herausliest nicht funktioniert
2. es mit meinem Vorschlag aber funktioniert

Wenn du dann doch damit kommst, dass im Skrpt aber dieses und jenes steht, dann reagiere ich zugegebenermaßen ein bißchen gereizt...

Also noch einmal (und du wirst ja wohl im Internet eine Quelle ausfindig machen können, wo das endlich einmal richtig steht): Wenn für eine lineare Rekursion die Störfunktion ein Polynom vom Grad k und 1 eine m-fache Nullstelle des charakteristischen Polynoms ist, dann solltest du die partikuläre Lösung ansetzen in der Form

$\begin{eqnarray*} n^m (a_kn^k+\ldots+a_1n+a_0) \end{eqnarray*}$

Für den Fall, dass 1 keine Nullstelle des charakteristischen Polynoms ist, entspricht das also genau dem, was im Skriptum steht... Ist aber 1 eine m-fache Nullstelle mit m>0, so sind dann die Potenzen

$\begin{eqnarray*} 1,n,n^2,\ldots,n^{m-1} \end{eqnarray*}$

automatisch Lösungen der homogenen Differenzengleichung und daher muss der Ansatz "weiter oben" (aber gewissermaßen nur verschoben) beginnen, da die untersten Terme dann "nichts beitragen"... Einfach mal an einem Beispiel nachrechnen, da sieht man das alles am besten!

28.04.2011, 15:25

Philipp Imhof

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion bestimmen

Zitat:

Wenn du dann doch damit kommst, dass im Skrpt aber dieses und jenes steht, dann reagiere ich zugegebenermaßen ein bißchen gereizt...

Das war, wie gesagt, in keiner Weise meine Absicht.

Zitat:

Für den Fall, dass 1 keine Nullstelle des charakteristischen Polynoms ist, entspricht das also genau dem, was im Skriptum steht... Ist aber 1 eine m-fache Nullstelle mit m>0, so sind dann die Potenzen

$\begin{eqnarray*} 1,n,n^2,\ldots,n^{m-1} \end{eqnarray*}$

automatisch Lösungen der homogenen Differenzengleichung und daher muss der Ansatz "weiter oben" (aber gewissermaßen nur verschoben) beginnen, da die untersten Terme dann "nichts beitragen"...

Vielen Dank! Das war das fehlende Puzzle-Teil für mein Verständnis, woher dieses n^m kommt und warum.

Neue Frage »

Antworten »

Erzeugende Funktion bestimmen

Verwandte Themen