Die Mathe-Redaktion - 18.02.2020 23:12 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 515 Gäste und 15 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Erzeugende Funktionen » Summengrenzen bei erzeugenden Funktionen
Druckversion
Druckversion
Autor
Universität/Hochschule J Summengrenzen bei erzeugenden Funktionen
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-05


Hi!

Ich bin neu hier, also wenn ich irgendwie gegen die Forumsetiquette verstoße, bitte sagen :)


Ich möchte folgende Rekursionsgleichung mittels der erzeugenden Funktionen lösen:
\[
a_n = 2a_{n-1} + n\quad n\geq 1,\:a_0 = 0
\] Ich hab mich also hingesetzt, und den Algorithmus aus der Vorlesung angewandt. Zuerst habe ich mir mein $A(n)$ definiert:
\[
A(n) = \sum_{n\geq 1} a_nx^n
\] Nun habe ich beide Seiten der Rekursionsgleichung mit $x^n$ multipliziert und aufsummiert:
\[
\sum_{n\geq 1}a_nx^n = 2\sum_{n\geq 1}a_{n-1}x^n + \sum_{n\geq 1}nx^n
\] Ich habe mir die Summenglieder von $\sum_{n\geq 1}a_{n-1}x^n$ angeschaut, und bin zu dem Schluss gekommen, dass gilt:
\[
\sum_{n\geq 1}a_{n-1}x^n = x \sum_{n\geq 1}a_{n}x^n = x A(x)
\] Somit komme ich zu der Darstellung:
\[
A(x) = 2xA(x) + \sum_{n\geq 1}nx^n
\]

Jetzt kommen wir zu meinem Problem. Ich habe nun in meine Tabelle geschaut, und dort steht geschrieben (man achte dass die Summe bei $0$ anfängt):
\[
  \sum_{n\geq 0}nx^n = \frac{x}{(1-x)^2}
\] Wenn ich jetzt $\sum_{n\geq 1}nx^n$ ersetzen will, wie muss ich hier vorgehen? Ist es schlimm, dass der erste Summand fehlt? Kann ich die Summe irgendwie anpassen?

Noch wichtiger für die Klausur ist aber auch: Was ist wenn die Summe erst bei $n=4$ anfängt? Oder bei $n=k$, also wie geht man im allgemeinen Fall vor?

Liebe Grüße!



  Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-05


Hi kathi_,

willkommen auf dem MP!  smile

Überlege kurz, was der Term $nx^n$ für $n = 0$ ist, dann sollte sich deine Frage beantworten.

(Ähnliches ist übrigens bei deiner Umformung $\sum_{n \geq 1} a_{n-1} x^n = x \sum_{n \geq 1} a_n x^n$ passiert. Hier ist $a_0$ auch "verschwunden".)

Falls die Summe später anfängt, so kannst du die ersten Glieder per Hand ausrechnen. Manchmal kann man dabei geschickt umformen.


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-05


Hi Kezer,

danke für die schnelle Antwort :)

Ich glaube in diesem Fall ist das einfach, weil der Summand für $n=0$ einfach $0$ ist, korrekt?

Wie gehe ich jedoch vor wenn dieser einfache Fall nicht eintritt? Es könnte ja z.B. vorkommen, dass die Summe erst ab $n=2$ anfängt, wenn ich bspw. zwei Startwerte habe.

Liebe Grüße!

EDIT: Ah hast deine Nachricht editiert :) Kann ich die Glieder dann einfach wieder abziehen?



  Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-05


Richtig und richtig.  smile


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-01-05


Vielen Dank!

Ist es okay wenn ich noch meinen restlichen Rechenweg poste? :) Ich glaube ich habe soeben endlich verstanden wie das Verfahren funktioniert :)


-----

Ich habe also lustig weitergerechnet, wobei wir hiermit anfangen:
\[
A(n) = 2xA(n) + \frac{x}{(1-x)^2}
\] Nach Umformen habe ich raus:
\[
A(n) = \frac{x}{(1-x)^2(1-2x)}
\] Dann habe ich eine Partialbruchzerlegung gemacht:
\[
A(n) = \frac{x}{(1-x)^2(1-2x)} = \frac{-1}{(1-x)^2} + \frac{-1}{1-x} + \frac{2}{1-2x}
\] Dann bastle ich mir Summen aus den einzelnen Termen. Fangen wir mit dem ersten an:
\[
   \frac{-1}{(1-x)^2} = -1 \cdot \frac{1}{(1-x)^2} = -1 \cdot \sum (n+1)x^n \quad\Rightarrow\quad \text{Koeffizient:}\: -(n+1)
\] Der zweite Term:
\[
   \frac{-1}{1-x} = -1 \cdot \frac{1}{1-x} = -1 \cdot \sum 1\cdot x^n \quad\Rightarrow\quad \text{Koeffizient:}\: -1
\] Und schließlich der dritte und letzte Term:
\[
   \frac{2}{1-2x} = 2 \cdot \frac{1}{1-2x} = 2 \cdot \sum (2x)^n = 2 \cdot \sum 2^n x^n \quad\Rightarrow\quad \text{Koeffizient:}\: 2^{n+1}
\]
Insgesamt ergibt sich also:
\[
a_n = 2^{n+1} -n - 2
\]
Passt das so? :)

Liebe Grüße!



  Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-01-05


Hi,

ich habe nicht überprüft, ob die Partialbruchzerlegung stimmt, aber das sollte so richtig sein.

Wann immer du dir nicht sicher bist, ob das Ergebnis korrekt ist, hilft es kleine Werte einzusetzen. Wolfram-Alpha schafft es auch, direkt das Ergebnis auszugeben - hier gibt WA genau dein Resultat aus.  smile


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-01-05


Vielen Lieben Dank! Dieses Thema ist für mich aus irgendeinem Grund extrem schwer, aber ich habe es jetzt denke ich gut verstanden.

Könntest du mir das Kommando für WolframAlpha zeigen, wie man danach fragt? :)

Ich habe mir zwei Python-Funktionen geschrieben, einmal die geschlossene Funktion und einmal die Rekursionsgleichung, und dann die Ergebnisse für ein paar $n$ verglichen. Nicht sehr effektiv :P



  Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-01-05


Sowas wie "a_n = 2a_(n-1) + n explicit" reicht schon bei WA. Ich würde direkt kleine Werte im Kopf (oder auf dem Papier) überprüfen, aber ein Python-Programm tut es natürlich auch.


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-01-05


Vielen Lieben Dank für all die Antworten! Du hast mir sehr bei der Klausurvorbereitung geholfen :)

Einen schönen Abend dir noch!



  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 10.01.2011
Mitteilungen: 3200
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-01-05


Hallo.

Der Clou bei Erzeugenden ist es oft den Index zu Shiften und Rekurrenzen 1-1 in Algebra zu übersetzen.

Die Methode hier angewendet ergibt:

Wir habe die Rekurrenz

$\displaystyle a_{n+1}=2 \cdot a_n+(n+1)$ für $n \ge 0$ mit $a_0=0$

Es folgt sofort

$\displaystyle \dfrac {A(x)-a_0}{x}=2 \cdot A(x)+ \dfrac {1}{(1-x)^2}$

Jetzt kann man einfach nach $A(x)$ auflösen und weiterrechnen.

Man muss also bei dieser Aufgabe sich absolut nicht mit den Summen und Grenzen herumschlagen.

Siehe Klick mich

Gruss endy

PS: In Beitag Nr.4 muss mehrfach n durch x ersetzt werden.



-----------------
Dean Koontz : Zwielicht

Unzählige verschlungene Nachtpfade zweigen vom Zwielicht ab.
Etwas bewegt sich inmitten der Nacht,das nicht gut und nicht richtig ist.

The Book of Counted Sorrows.




  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-01-05


Hallo,

achso, du meinst also, dass man die Rekursionsformeln fast schon "normalisiert" (das Wort wird hier natürlich nicht verwendet), also in eine kanonische Form bringt, sodass die Summen auf der rechten Seite keine Indexprobleme mehr verursachen?

Also wenn ich bspw. die folgende Rekursion habe:
\[
  a_n = a_{n-1} + a_{n-2} + n
\]
Dann mache ich daraus:
\[
    a_{n+2} = a_{n+1} + a_{n} + (n+2)
\]
Korrekt?

Ich hab schon hergeleitet, dass gilt:
\[
   \sum a_{n+1}x^n = \frac{A(x) - a_0}{x}
\]
Gibt es dafür eine allgemeine Formel für $a_{n+k}$? :)

Könnte das hier stimmen:
\[
  \sum a_{n+k}x^n = \frac{A(x) - \sum_{r = 0}^{k-1}a_r}{x^k}
\]
Gruß



  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 10.01.2011
Mitteilungen: 3200
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-01-05


Ja und fast Ja.

Wenn du in dem verlinkten Buch aus Beitrag Nr.9 auch nur die ersten beiden Kapitel verstanden hast , sind Erzeugende kein Problem mehr für dich in einer Klausur.

Siehe Klick mich

mma kennt diese Formeln übrigens auch:
mathematica
(* In *)
 
GeneratingFunction[f[n + 1], n, x] // Simplify // ExpandNumerator
GeneratingFunction[f[n + 2], n, x] // Simplify // ExpandNumerator
GeneratingFunction[f[n + 3], n, x] // Simplify // ExpandNumerator
GeneratingFunction[f[n + k], n, x, 
 Assumptions -> k \[Element] Integers && k > 0]
GeneratingFunction[f[n - k], n, x, 
 Assumptions -> k \[Element] Integers && k > 0]
 

endy
 
Nachricht zur Änderung : mma Code eingefügt.



  Profil  Quote  Link auf diesen Beitrag Link
kathi__
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-01-05


Vielen Dank für die Hilfe und den Link!



  Profil  Quote  Link auf diesen Beitrag Link
kathi__ hat die Antworten auf ihre/seine Frage gesehen.
kathi__ hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]