Menge verstehen, für Rekusion

Aufrufe: 830     Aktiv: 12.08.2020 um 23:22

0

Moin Leute,

ich tue mich schwer diese Aufgabe zu lösen. Ich denke nicht, dass es "schwer" sein wird die Rekursion an sich explizit zu berechnen, mir fällt es schwierig diese Menge zu verstehen. Ich kann damit nichts anfangen. Wie soll das aussehen?

LG Theo

 

EDIT: lasst euch nicht von dem Rest ablenken. Die Erzeugende Funktion A(x)  steht ganz unten mit der Rechnung, Altklausur 2019.2

Diese Frage melden
gefragt

Student, Punkte: 66

 
Kommentar schreiben
2 Antworten
1

Also fangen wir erstmal an \(a_0,a_1,a_2\) zu bestimmen.

\(a_0\) ist die Anzahl an Folgen von 2en und 3en deren Summe 2 ergibt. Da gibt es nur eine Folge nämlich "2".

\(a_1\) ist die Anzahl an Folgen von 2en und 3en deren Summe 3 ergibt. Da gibt es nur eine Folge nämlich "3".

\(a_2\) ist die Anzahl an Folgen von 2en und 3en deren Summe 4 ergibt. Da gibt es nur eine Folge nämlich "22".

Im Allgemeinen ist \(a_{n}\) die Anzahl an Folgen der Summe \(n+2\) ergibt. Für \(n>2\) kann man sich nun Folgendes überlegen. Eine Folge deren Summe \(n+2\) ergibt erhält man, indem man eine Folge mit Summe \(n\) nimmt und eine \(2\) dranhängt oder eine Folge mit Summe \(n-1\) und eine \(3\) anhängt. Die Anzahl der Folgen mit Summe \(n+2\) enspricht also gerade der Anzahl an Folgen mit Summe \(n\) plus der Anzahl der Folgen mit Summe \(n-1\). 

Somit ist also für \(a_n=a_{n-2}+a_{n-3}\) für \(n>2\).

Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 3.1K

 

danke euch beiden!!! ihr habt mir schon mehrmals geholfen, ich bin euch sehr dankbar :)   ─   labis.theodoros 11.08.2020 um 21:56

Kommentar schreiben

1

Nach einer Menge ist hier gar nicht gefragt. Fang mal an mit a_0, a_1, a_2, a_3. Die gefragte Summe ist sowas wie die Quersumme. Dann schauen wir weiter.

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 39.52K

 

Ja da fängt mein Problem an. (Ich wusste nicht wie ich es sonst nennen sollte). Wie soll ich denn a_0 bestimmen?
"aller Folgen von zweien und dreien". und womit fang ich nun an? und wie viele? also mir fällt es schwer zu verstehen was da von mir gefordert ist. soll ich einfach en folge aus zufälligne 2en und 3en aufschreiben? und dann eine summe drüber bilden? das macht für mich keinen sinn
  ─   labis.theodoros 11.08.2020 um 20:56

moment, da muss cih kurz drüber nachdenken.   ─   labis.theodoros 11.08.2020 um 21:27

so jetzt bin cih wieder da. sei a_1 die Anzahl der Folge vonm Zweien und Dreien, dass n+2. dh für a_0 kommt nur 2 in frage da 0+2 = 2

a_1 = 3, a_2 = 2+2= 4 ?? meine intuition sagt nein, da ich gerade die bedingung " folge zweier und dreier" irgendwie nicht mit einbeziehe. du sagst, die gefragte summe ist sowas wie die Quersumme, hm. dh die zweien und dreien sind immer abwechselnd? zB für a_0 = 2, a_1 = 2+3, a_2 = 2+3+2, a_3 =2+3+2+3?
  ─   labis.theodoros 11.08.2020 um 21:54

jap, hab es danach auch gesehen. meine intuition war also nicht so verkehrt. ja tatsächlich wollte ich es auch selbst rausfinden. dennoch bin ich für jeden dankbar, der mir auf seine art und weise hilft, das schätze ich wert. ich mache ja weiter. werde jetzt versuchen die erzeugende Funktion zu ersstellen um auf das Polynom A(x) zu kommen. mal schauen, eigentlich ist der Algorithmus drin.

dennoch danke ich dir für die bemühungen!
  ─   labis.theodoros 11.08.2020 um 22:29

ich editiere mal die Frage, dann kann ich ein Bild meiner Rechnun hochladen, das geht schneller.   ─   labis.theodoros 11.08.2020 um 22:43

A(x)= P(x) / Q(x)

P(x) = 3x^2+3x+2 und Q(x) = -x^3-x+1
  ─   labis.theodoros 11.08.2020 um 22:49

Jap. Dazu haben wir keine Lösungen bekommen. Durch die Klausur bin ich letztes Jahr durchgefallen. Erzeugende Funktion ist ja "nur" ein Algorithmus. ich bevorzuge lieber die Variante aus 2019.1 aber das kann man sich nicht immer aussuchen. Weil eine Partialbruchzerlegung mit 3 Variablen, dauert mir zu lange der Koeffizientenvergleich. Außerdem verrechne ich mich da immer.

Ich hab nur ganz kleines bisschen gespickt, ob ich bei der ersten Summe, nach dem ich sie geteilt habe, welche a_i abziehen muss. Aber das hab ich jetzt verstanden.
  ─   labis.theodoros 11.08.2020 um 22:55

bei 2019.1 hab ich nicht geraten. ich hab ja die ersten 3 bestimmt. ich hab das Kreuzprodukt nach Vorgabe gebildet, ist das falsch gewesen? muss ich das anders machen? ich bin davon ausgegangen, dass das so richtig wäre. O.O, jetzt bin ich verwirrt.
EDIT: bei mir auf dem schmierblatt habe ich sogar a_4 und a_5 bestimmt, nur um zu sehen ob das hinhaut :D

und bei 2019.2 wäre das keine Lösung mit vollen Punkten? weil was genau fehlt da? müsste ich genauer argumentieren wie ich auf die Rekursion komme?
  ─   labis.theodoros 11.08.2020 um 23:03

ok, verstehe. ja das sollte ich eigntlich auch erwarten. da hast du recht. dann wie folgt:

2019.1: tatsächlich habe ich, wie gesagt, bis a_5 bestimmt. Das hat natürlich etwas gedauert, aber so hatte ich dann die Werte a_1 = 1, a_2 = 3, a_3 = 5, a_4 = 8. Dann war mir eigentlich klar, dass es die Fibonacci ist. Aber einfach sagen "denke das ist so" ist nicht wissenschaftlich. Aber Ansatz 1: reichen nicht mehrere Glieder aus, um die Vermutung zu einer richtigen Aussage zu machen? Anscheinend nicht, dh. es gibt eine Methode, anhand der ermittelten Punkte die Rekursion eindeutig zu bestimmen. Aber lt. VL ist eine Rekursion ja eindeutig durch die Glieder bestimmt. (darüber mache ich mir gleich noch Gedanken)

2019.2: da hast du absolut recht. jetzt beim zweiten mal nachdenken und dem versuch zu begründen, warum die rekursion so aussieht, fällt mir die argumentation schwer. auch darüber mache ich mir kurz noch mal gedanken.
  ─   labis.theodoros 11.08.2020 um 23:17

Ich bin idr kein Freund von Raten, da es mir in den meisten Fällen nicht hilft, nicht zu wissen wie es richtig geht. Daher suche ich eigentlich immer nach eine Rezept, wie ich mir die Sachen zurechtdenken muss. Daher habe ich gerade mal im Skript noch mal nachgeschaut. Eine Rekursionsgleichung k-ter Ordnung ist definiert als: x_n = c_1*x_{n-1}+c_2*x_{n-2}+...+c_k*x_{n-k}+b_k, mit b_k = 0 wenn die rekursion homogen ist, sonst inhomogen. Hilft mir das? Meine Idee, einsetzen und mal schauen was passiert. Durch ausprobieren lernt man :D

zu 2019.1
dh. ich könnte dort theoretisch meine "berechneten" Glieder einsetzen und bekomme:
ich weiß zu dem punkt ja nicht, ob sie inhomogen ist? deswegen das fragezeichen statt b_k

a_1 = c_1 * x_0 + (?)
a_2 = c_1 * x_{2-1=1} + c_2 * x_{2-2=0}
a_3 = c_1 * x_{3-1=2} + c_2 * x_{3-2=1} + c_3 * x_{3-3=0}
usw.

ist das ein ansatz den man verfolgen kann? Oder ist das "zu aufwendig"?

EDIT: und ich verstehe nicht, wieso da mal was kursiv ist, wieso da jetzt das Multiplikationszeichen fehlt, aber hier steht es drin, und die LaTex Befehle klappen hier irgendwie auch nicht :D auch dazu lasse ich mich gerne belehren.
  ─   labis.theodoros 11.08.2020 um 23:40

Ausprobieren ist zwar ein Rezept für das Lernen, aber Ausprobieren ist kein gutes Rezept für eine Klausur :D
ich glaube mir ist gerade ein Zusammenhang klar geworden: Eine Rekursion ist genau eindeutig durch alle Glieder bestimmt. Deswegen werden dann die expliziten Ausdrücke gesucht, da diese in einem Polynomraum sind. Das Polynom ist dann sowieso ein Erzeuger, dh das Polynom baut den Raum auf, aber eine Rekursion für sich alleinstehend mit den paar Startwerten hat nicht die gleiche Aussage, richtig?

zurück zu der aufgabe. ich bleibe mal bei 2019.1. die Folge a_n = (2 3 5 8 13 21 34 55 ... ) ich habe mal paar Werte dazu genommen, vllt hilft mir das ein Bildungsgesetz zu erkennen. Die Zahl a_n, wie die sich verändert, hm. die Zahl a_n wird immer größer. sie wird aber nicht proportional oder sonstiges größer. die Zahl a_n ist hier +1 +2 +3 +5 +8 +13 größer, interressant, dh die zahl a_n wird gerade um die Folge selbst größer. ist das ein ansatz?

zu aufgabe 2019.2: gleiches versuche ich mal hier mit ein paar Werten mehr. Ich habe die zweien und Dreien immer so gewählt, dass die große Zahl minimal erreicht wird. a_n = ( 2 3 4 5 6 7 8 9 ... ), aber die Folge selbst wird ja aus 2en und 3en gebaut, also a_0 = 2, a_1 = 3, a_2 = (2 2), a_3 = (2 3), a_4 = (3 3), a_5 = (2 2 3), a_6 = (2 3 3)
, oder hätte ich es eher nach Primfaktorzerlegung wählen müssen? Das würde die a_6 ändern zu = (2 2 2 2).
  ─   labis.theodoros 12.08.2020 um 00:04

ich weiß noch nicht ob es klick gemacht hat, aber a_n wird ja gerade um die eigene Folge größer. dh wenn ich a_n bestimmen will, muss ich ihm ja nur die zwei vorhergehenden Werte geben, richtig?

zu 2019.2: absolut keine ahnung :D vllt muss ich einfach drüber schlafen. danke für die hilfe! ich hoffe dui kannst mir da noch weiter helfen? ich hau mich jetzt hin. danke und gute Nacht
  ─   labis.theodoros 12.08.2020 um 00:27

ich hab eine Methode gefunden, wie ich die Rekursion aus 2019.2 finden kann. ich hab mal wie du es mir gesagt hast, den rat angenommen und mal mehr glieder bestimmt. die sind folgende:

a_0 = Summe = 2: das wäre (2)
a_1 = Summe = 3: das wäre (3)
a_2 = Summe = 4: das wäre (22)
a_3 = Summe = 5: das wäre (23 32)
a_4 = Summe = 6: das wäre (33 222)
a_5 = Summe = 7: das wäre (322 232 233)
a_6 = Summe = 8: das wäre (332 233 323 2222)
a_7 = Summe = 9: das wäre (333 3222 2322 2232 2223)

daraus erkennt man den Wert des Glieds: ich schreibe jetzt nur mal die zahlenfolge auf für die a_i ist dann :: 1 1 1 2 2 3 4 5

dann hab ich mir überlegt. wie ich von einem auf das nächste Glied komme. von 0 auf 1 nix usw. interessant wurde es, als ich entdeckt habe, dass die a_3 = 2 ist. die 2 = 1+1. Aber da war noch nicht klar, welches der a_0/ a_1/ a_2 zu dieser Kombination führt. also habe ich mir die anderen Glieder angeschaut, bei a_5 war es dann deutlicher, 2+1, aber welche. habe weiter geschaut und bei a_8 oder a_9 dann gehsehen, dass es immer die 2 Glieder sind, ohne die a_n-1.

sieht das besser aus? oder ist das immer noch das selbe. ich finde die methode gut :)
  ─   labis.theodoros 12.08.2020 um 22:17

gelesen schon, aber wohl nicht verstanden. das ist ein großer Unterschied :(
es tut mir auch wirklich leid, aber ich sehe wohl incht wie ich das angehen soll. die argumentation von benesalvatore ist für mich halt auch nur "schwer" verständlich, aber irgendiwe ok
  ─   labis.theodoros 12.08.2020 um 22:30

- "Im Allgemeinen ist an die Anzahl an Folgen der Summe n+2 ergibt." das habe ich ja bei a_n als Summe stehen, das war klar


- "Für n>2 kann man sich nun Folgendes überlegen. Eine Folge deren Summe n+2 ergibt erhält man, indem man eine Folge mit Summe n nimmt und eine 2 dranhängt oder eine Folge mit Summe n−1 und eine 3 anhängt"
genau so habe ich tatsächlich die Folge weiter bestimmt und dann die unterschiedlichen a_n gefunden

"Die Anzahl der Folgen mit Summe n+2 enspricht also gerade der Anzahl an Folgen mit Summe n plus der Anzahl der Folgen mit Summe n−1." und genau das spiegelt doch mein Weg wieder, oder nicht?


Ja natürlich hab ich das noch mal versucht. Von nichts kommt nichts.

Ich habe ja zum Glück noch keinen Abschluss, da nehme ich es mir raus Sachen so aufzuschreiben, wie ich sie verstehe XD Natürlich verstehe ich, dass das in einer Klausur nicht unbedingt die max Punkte bringt. Mit der Notation will ich nur sagen, dass zB für a_0 die Summe durch die aufgabe n+2 = 2 ist. Dh. die Kombination aus den 2en und 3en kann nur "2" sein. für a_1 ist es ja n+2 = 1+2 = 3 und das geht nur mit einer 3 usw.

wie hätte ich das denn zB sauber schreiben können? Aber meinen tuen wir glaube ich das selbe (ich hoffe es, soll keine Anmaßung sein, lediglich Hoffnung :D )
  ─   labis.theodoros 12.08.2020 um 22:39

danke für deine Antwort. Ich denke nicht, dass es was mit cool sein zu tun hat, sondern eher mit Unwissen. Falsch schreiben/ argumentieren/ lösen etc. hat in der Mathematik nur mit Unwissen zu tun. Da bin ich keine Ausnahme. danke für deine Geduld und Hilfe. Heute muss cih schon etwas früher ins Bett.

schönen Abend noch.
  ─   labis.theodoros 12.08.2020 um 23:18

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.