matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikErzeugende Funktion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Diskrete Mathematik" - Erzeugende Funktion
Erzeugende Funktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erzeugende Funktion: Rechen- und Verständnisfrage
Status: (Frage) beantwortet Status 
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

        
Bezug
Erzeugende Funktion: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Erzeugende Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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



Bezug
                        
Bezug
Erzeugende Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Erzeugende Funktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:47 So 24.02.2019
Autor: magics

Ok, ich muss mir das einfach nochmal ganz in Ruhe begreiflich machen. Danke euch beiden!

Bezug
                        
Bezug
Erzeugende Funktion: Benennung
Status: (Antwort) fertig Status 
Datum: 14:11 So 24.02.2019
Autor: HJKweseleit

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.



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]