Erzeugende Funktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:24 Do 21.02.2019 | | Autor: | magics |
| Aufgabe | Gegeben sei die Rekurrenz [mm] $a_{n+1} [/mm] = [mm] 2a_n+1$ [/mm] mit [mm] $n\ge [/mm] 0, [mm] a_0=0$
[/mm]
Wir wollen nun die zugehörige erzeugende Funktion der Form $A(x) = [mm] \summe_{n\ge 0}^{}a_nx^n$berechnen. [/mm] Dazu werden beide Seiten der Gleichung mit [mm] $x^n$ [/mm] multipliziert und Summiert über [mm] $n\ge0$. [/mm] |
Hallo,
ich stelle nun einen Lösungsweg vor, wobei zum einen ein Umformungsschritt mit Hilfe der geometrischen Reihe nicht klar ist und zum anderen das Konzept einer erzeugenden Funktion überhaupt.
Lösung:
Zuerst die linke Seite der Gleichung. Unter Berücksichtigung, dass [mm] $a_0 [/mm] = 0$, ergibt sich:
[mm] \summe_{n\ge 0}^{}a_{n+1}x^n=a_1x^0+a_2x^1+a_3x^2+...= \bruch{a_1x^1+a_2x^2+a_3x^3+...}{x}=\bruch{a_0 + a_1x^1+a_2x^2+a_3x^3+...}{x}= \bruch{\summe_{n\ge 0}^{}a_nx^n}{x}=\bruch{A(x)}{x}
[/mm]
Nun zur rechten Seite der Gleichung:
[mm] $\summe_{n\ge 0}^{}(2a_n+1)x^n= \summe_{n\ge 0}^{}2a_nx^n+x^n=2\summe_{n\ge 0}^{}a_nx^n+\summe_{n\ge 0}^{}x^n=\red{2A(x)+\summe_{n\ge 0}^{}x^n=2A(x)+\bruch{1}{1-x}}$
[/mm]
Der letzte Umformungsschritt beruht auf [mm] $\summe_{n\ge 0}^{}x^n=\bruch{1}{1-x}$ [/mm] für $|x|<1$ (geometrische Reihe).
Nun setzen wir die beiden Seiten der Gleichung wieder zusammen und erhalten: [mm] $\bruch{A(x)}{x} [/mm] = [mm] 2A(x)+\bruch{1}{1-x}$. [/mm] Wir lösen nach $A(x)$ auf und erhalten $A(x) = [mm] \bruch{x}{(1-x)(1-2x)}$
[/mm]
1) Der rot markierte letzte Umformungsschritt für die rechte Seite der Ausgangsgleichung lautet [mm] $2A(x)+\summe_{n\ge 0}^{}x^n=2A(x)+\bruch{1}{1-x}$. [/mm] Wobei scheinbar angenommen werden kann, dass $|x|<1$
Wieso darf das angenommen werden?
Wir multiplizieren beide Seiten mit [mm] $x^n$ [/mm] und summieren anschließend auf. Das macht $x$ ja noch lange nicht zur Summe jeweils zwei benachbarter Elemente aus einer Folge. Sehr verwirrend.
2) Wir haben nun eine hübsche "erzeugende Funktion". In wie weit steht diese noch im Zusammenhang mit der Rekurrenz am Anfang? Die Rekurrenz divergiert, während die erzeugende Funktion gegen 0 läuft und zumahl noch eine eine Definitionslücke hat. Denn bei $A(1)$ dividiert man plötzlich durch $0$, was mir überhaupt nicht gefällt.
Im großen und ganzen schreibt jede Literatur, die es zu dem Thema gibt von erzeugenden Funktionen als eine Potenzreihendarstellung einer unendlichen Folge von reellen Zahlen. Ist das nun ein reiner Formalismus oder steckt mehr dahinter? Kann ich behaupten, ich habe das Prinzip einer erzeugenden Funktion verstanden, wenn ich sage, "Die wird dazu benutzt, um aus eine Rekurrenz einen geschlossenen Ausdruck zu basteln"?.
Beste Grüße
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:41 Do 21.02.2019 | | Autor: | fred97 |
> Gegeben sei die Rekurrenz [mm]a_{n+1} = 2a_n+1[/mm] mit [mm]n\ge 0, a_0=0[/mm]
>
> Wir wollen nun die zugehörige erzeugende Funktion der Form
> [mm]A(x) = \summe_{n\ge 0}^{}a_nx^n[/mm]berechnen. Dazu werden beide
> Seiten der Gleichung mit [mm]x^n[/mm] multipliziert und Summiert
> über [mm]n\ge0[/mm].
>
> Hallo,
>
> ich stelle nun einen Lösungsweg vor, wobei zum einen ein
> Umformungsschritt mit Hilfe der geometrischen Reihe nicht
> klar ist und zum anderen das Konzept einer erzeugenden
> Funktion überhaupt.
>
>
> Lösung:
> Zuerst die linke Seite der Gleichung. Unter
> Berücksichtigung, dass [mm]a_0 = 0[/mm], ergibt sich:
> [mm]\summe_{n\ge 0}^{}a_{n+1}x^n=a_1x^0+a_2x^1+a_3x^2+...= \bruch{a_1x^1+a_2x^2+a_3x^3+...}{x}=\bruch{a_0 + a_1x^1+a_2x^2+a_3x^3+...}{x}= \bruch{\summe_{n\ge 0}^{}a_nx^n}{x}=\bruch{A(x)}{x}[/mm]
>
> Nun zur rechten Seite der Gleichung:
> [mm]\summe_{n\ge 0}^{}(2a_n+1)x^n= \summe_{n\ge 0}^{}2a_nx^n+x^n=2\summe_{n\ge 0}^{}a_nx^n+\summe_{n\ge 0}^{}x^n=\red{2A(x)+\summe_{n\ge 0}^{}x^n=2A(x)+\bruch{1}{1-x}}[/mm]
>
> Der letzte Umformungsschritt beruht auf [mm]\summe_{n\ge 0}^{}x^n=\bruch{1}{1-x}[/mm]
> für [mm]|x|<1[/mm] (geometrische Reihe).
>
> Nun setzen wir die beiden Seiten der Gleichung wieder
> zusammen und erhalten: [mm]\bruch{A(x)}{x} = 2A(x)+\bruch{1}{1-x}[/mm].
> Wir lösen nach [mm]A(x)[/mm] auf und erhalten [mm]A(x) = \bruch{x}{(1-x)(1-2x)}[/mm]
>
>
> 1) Der rot markierte letzte Umformungsschritt für die
> rechte Seite der Ausgangsgleichung lautet
> [mm]2A(x)+\summe_{n\ge 0}^{}x^n=2A(x)+\bruch{1}{1-x}[/mm]. Wobei
> scheinbar angenommen werden kann, dass [mm]|x|<1[/mm]
>
> Wieso darf das angenommen werden?
Das darf nicht nur angenommen werde, sondern muss angenommen werden, nur für $|x|<1$ ist die geometrische Reihe [mm] \summe_{n\ge 0}^{}x^n [/mm] konvergent und = [mm] \frac{1}{1-x}.
[/mm]
>
> Wir multiplizieren beide Seiten mit [mm]x^n[/mm] und summieren
> anschließend auf. Das macht [mm]x[/mm] ja noch lange nicht zur
> Summe jeweils zwei benachbarter Elemente aus einer Folge.
> Sehr verwirrend.
Wieso verwirrend ? Du hast $ [mm] a_{n+1} [/mm] = [mm] 2a_n+1 [/mm] $. Muktiplikation mit [mm] x^n [/mm] ergibt
$ [mm] a_{n+1}x^n [/mm] = [mm] 2a_nx^n+x^n [/mm] $
Summation liefert:
$ [mm] \sum_{n=0}^{\infty}a_{n+1}x^n [/mm] = 2 [mm] \sum_{n=0}^{\infty}a_nx^n+ \sum_{n=0}^{\infty}x^n [/mm] $
Die linke Seite dieser Gleichung ist gerade (siehe obige Rechnung) [mm] =\frac{A(x)}{x} [/mm] und die rechte Seite = 2A(x)+ [mm] \frac{1}{1-x}
[/mm]
(für |x|<1).
>
> 2) Wir haben nun eine hübsche "erzeugende Funktion". In
> wie weit steht diese noch im Zusammenhang mit der Rekurrenz
> am Anfang? Die Rekurrenz divergiert,
Ja, die Folge [mm] (a_n) [/mm] ist divergent, na und ?
> während die
> erzeugende Funktion gegen 0 läuft
Was läuft gegen 0 ? Wir haben [mm]A(x) = \bruch{x}{(1-x)(1-2x)}[/mm].
Ich sehe nur: [mm] \lim_{x \to 0}A(x)=0.
[/mm]
> und zumahl noch eine
> eine Definitionslücke hat. Denn bei [mm]A(1)[/mm] dividiert man
> plötzlich durch [mm]0[/mm], was mir überhaupt nicht gefällt.
Man mag es bedauern, ändern kann man es nicht: die Funktion A ist in x=1 und in x=1/2 nicht definiert.
>
> Im großen und ganzen schreibt jede Literatur, die es zu
> dem Thema gibt von erzeugenden Funktionen als eine
> Potenzreihendarstellung einer unendlichen Folge von reellen
> Zahlen. Ist das nun ein reiner Formalismus oder steckt mehr
> dahinter? Kann ich behaupten, ich habe das Prinzip einer
> erzeugenden Funktion verstanden, wenn ich sage, "Die wird
> dazu benutzt, um aus eine Rekurrenz einen geschlossenen
> Ausdruck zu basteln"?.
Ich versuche, Dir allgemein zu erklären, worum es geht: gegeben ist eine Folge [mm] (a_n)_{n \ge 0}.
[/mm]
Unter der erzeugenden Funktion dieser Folge versteht man die (formale) Potenzreihe [mm] A(x)=\sum_{n=0}^{\infty}a_nx^n.
[/mm]
Das wars schon mit der Def. ! Wenn gewünscht, so kann man sich noch nach einem geschlossenen Ausdruck von A(x) umsehen.
Beispiele:
1) Sei [mm] (a_n) [/mm] die Folge in Deiner Anfrage. Obige Rechnungen zeigen:
$ A(x) = [mm] \bruch{x}{(1-x)(1-2x)} [/mm] $
Für $|x|<1/2$ ist [mm] A(x)=\sum_{n=0}^{\infty}a_nx^n
[/mm]
Frage an Dich: warum $|x|<1/2 $?
2) Sei [mm] (a_n)=(1,1,1,....). [/mm] Dann ist [mm] A(x)=\sum_{n=0}^{\infty}x^n [/mm] und für $|x|<1$ ist $A(x)= [mm] \frac{1}{1-x}$.
[/mm]
3) Sei [mm] (a_n)=(n). [/mm] Dann ist [mm] A(x)=\sum_{n=1}^{\infty}nx^n.
[/mm]
Die Folge [mm] (a_n) [/mm] ist divergent, aber die Potenzreihe [mm] \sum_{n=1}^{\infty}nx^n [/mm] konvergiert für |x|<1 (warum ?)
>
> Beste Grüße
> Thomas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:31 Do 21.02.2019 | | Autor: | magics |
Hallo Fred,
> >Wobei scheinbar angenommen werden kann, dass [mm]|x|<1[/mm]
> >
> > Wieso darf das angenommen werden?
>
> Das darf nicht nur angenommen werde, sondern muss
> angenommen werden, nur für [mm]|x|<1[/mm] ist die geometrische
> Reihe [mm]\summe_{n\ge 0}^{}x^n[/mm] konvergent und =
> [mm]\frac{1}{1-x}.[/mm]
Eine geometrische Reihe kann, muss aber nicht konvergieren, wieso muss man es in diesem Fall annehmen?
> Ich versuche, Dir allgemein zu erklären, worum es geht:
> gegeben ist eine Folge [mm](a_n)_{n \ge 0}.[/mm]
>
> Unter der erzeugenden Funktion dieser Folge versteht man
> die (formale) Potenzreihe [mm]A(x)=\sum_{n=0}^{\infty}a_nx^n.[/mm]
Ich akzeptiere, dass es eine Definition ist gibt und auch wie man diese verwenden kann, um die Ausgangsgleichung umzuformen.
> Das wars schon mit der Def. ! Wenn gewünscht, so kann man
> sich noch nach einem geschlossenen Ausdruck von A(x)
> umsehen.
Ok, genau da liegt für mich der Hase im Pfeffer. Es gibt einen Zusammenhang zwischen dem geschlossenen Ausdruck und der Ausgangsfunktion, der über das Multiplizieren mit [mm] $x^n$ [/mm] und aufsummieren gebildet wird. Dieser Zusammenhang ist mir nicht klar.
Ein Beispiel meinerseits: Will man z.B. ein Binom ausmultiplizieren, kann man sich ein Pascalsches Dreieck aufmalen und mit dessen Hilfe das Binom aufschreiben. Man stellt die beiden Seiten der Gleichung, z.B. [mm] $(a+b)^3=a^3+3a^2b+3ab^2+b^3$ [/mm] in einem Zusammenhang über das Pascalsche Dreieck. Wenn man hinterfragt, wieso das Pascalsche Dreieck funktioniert, kann man es ja ganz klar über den Binomialkoeffizienten herleiten und wird am Ende auch verstehen, warum das funktioniert.
Bei der erzeugenden Funktion, weiß ich zwar rezeptartig: "Multipliziere mit [mm] $x^n$ [/mm] und summiere auf, aber woher nimmt man die Gewissheit, dass man eine erzeugende Funktion genau so bilden muss und nicht anders? Mich macht das ehrlich gesagt ziemlich fertig.
>
> Beispiele:
>
> 1) Sei [mm](a_n)[/mm] die Folge in Deiner Anfrage. Obige Rechnungen
> zeigen:
>
> [mm]A(x) = \bruch{x}{(1-x)(1-2x)}[/mm]
>
> Für [mm]|x|<1/2[/mm] ist [mm]A(x)=\sum_{n=0}^{\infty}a_nx^n[/mm]
>
> Frage an Dich: warum [mm]|x|<1/2 [/mm]?
Ich nehme an, es hat irgendwas damit zu tun, dass $A(x)$ für [mm] $x=\bruch{1}{2}$ [/mm] und $x=1$ nicht definiert ist. Warum sagt man nicht zum Beispiel für alle $x [mm] \not= \bruch{1}{2}$ [/mm] und $x [mm] \not=1$ [/mm] gälte $A(x)$?
> 3) Sei [mm](a_n)=(n).[/mm] Dann ist [mm]A(x)=\sum_{n=1}^{\infty}nx^n.[/mm]
>
> Die Folge [mm](a_n)[/mm] ist divergent, aber die Potenzreihe
> [mm]\sum_{n=1}^{\infty}nx^n[/mm] konvergiert für |x|<1 (warum ?)
Für $|x|<1$ wird das Polynom [mm] $x^n$ [/mm] mit jedem Summanden kleiner und daher konvergiert es auch. Aber wie gesagt, wieso muss man es so wählen, dass es konvergiert?
Grüße
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:00 Fr 22.02.2019 | | Autor: | leduart |
Hallo
Du hast irgendwie nicht verstanden, dass "erzeugende Funktion" einfach eine Definition ist. offensichtlich suggeriert dir der Name dass da etwas "erzeugt" wird. Was sicher nicht erzeugt wird, ist die zugehörige Folge. Die Definition ist rein formal, also erstmal unabhängig von Konvergenz oder nicht.
Für bestimmte x in deinem Fall x<1 st dann die formal definierte Potenzreihe auch wirklich eine Funktion von x.
Was du also "verstehen" willst kannst du nicht, es sei denn, dass bestimmte Summen bzw Funktionen mit bestimmten Folgen zusammenhängen, dazu siehe die Beispiele in Wiki.
Gruß ledum
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:47 So 24.02.2019 | | Autor: | magics |
Ok, ich muss mir das einfach nochmal ganz in Ruhe begreiflich machen. Danke euch beiden!
|
|
|
| |
|
Zum Begriff "Erzeugende Funktion":
Nehmen wir mal den umgekehrten Weg: Du hast eine beliebige Funktion f(x), die du um [mm] x_0 [/mm] = 0 in eine Taylorreihe entwickelst. Nehmen wir mal f(x) = [mm] e^x. [/mm] Dann bekommst du eine unendliche Reihe (wenn sie endlich ist, füllst du die weiteren Folgeglieder mit Nullen auf) der Form
[mm] \summe_{i=0}^{\infty}a_i x^i [/mm] (wobei du die [mm] a_i [/mm] mit Hilfe der Ableitungen bestimmen kannst), in unserem Fall also [mm] a_i [/mm] = [mm] \bruch{1}{i!}).
[/mm]
Die [mm] a_i [/mm] bilden somit eine Folge, die von der Funktion f(x) durch die Taylorreihe erzeugt wird. Daher heißt sie die erzeugende Funktion.
Ebenso erzeugt f(x) = [mm] \bruch{1}{1-x} [/mm] die Folge [mm] a_i [/mm] = 1 und f(x) = [mm] \bruch{1}{1+x} [/mm] die Folge [mm] (-1)^i.
[/mm]
Deine Aufgabe bestand darin, aus der Taylorreihe die Funktion zu ermittel, die diese Reihe erzeugt hat.
Natürlich haben die Taylorreihen verschieden große Konvergenzradien, aber die [mm] a_i [/mm] sind eindeutig definiert.
|
|
|
|
