www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de