Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Rekursionsgleichung für Folge

Rekursionsgleichung für Folge

Universität / Fachhochschule

Differenzengleichungen

Rekursives Zählen

Tags: Differenzengleichung, Rekursives Zählen

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Piepo

Piepo aktiv_icon

19:51 Uhr, 03.10.2021

Antworten
Moin,

das hier war eine Frage in einer meiner Klausuren:

Für n ∈ N sei gn die Anzahl der Folgen (beliebiger Länge) mit Einträgen
aus {1, 2, 3}, für die die Summe aller Einträge gleich n ist. Z.B. ist g1 = 1, g2 = 2,
g3 = 4. Finden Sie eine Rekursionsgleichung für die Folge (gn)nN.

Ich habe versucht ein paar Werte zu errechnen, sehe aber kein konkretes Muster. Gut möglich, dass ich mich auch verrechnet habe.

Ich freue mich über jede Hilfe.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Antwort
DrBoogie

DrBoogie aktiv_icon

20:56 Uhr, 03.10.2021

Antworten
Den Fall a1+...+ak=n kann man in die Fälle
a1=n, a1=n-1, a1=n-2,..., an=1 unterteilen, was zu
gn=1+g1+g2+...+gn-2+gn-1 führt.
Piepo

Piepo aktiv_icon

21:07 Uhr, 03.10.2021

Antworten
Ich verstehe nicht ganz, was mit dem Fall a1+...+ak=n und der Zerlegung gemeint ist. Deswegen auch die Schlussfolgerung nicht ganz. Gäbe es noch eine etwas ausführlichere Antwort bzw. eine für dumme? :-D)
Kann auch gut sein, dass ich gerade komplett auf dem Schlauch stehe...
Antwort
HAL9000

HAL9000 aktiv_icon

21:15 Uhr, 03.10.2021

Antworten
@DrBoogie

Du vergisst, dass die Summanden nur aus {1,2,3} stammen dürfen.

Es ist für n4 daher einfach gn=gn-1+gn-2+gn-3, was die drei Fälle abdeckt, dass die Summandenfolge mit 1,2 oder 3 beginnt.

Antwort
DrBoogie

DrBoogie aktiv_icon

21:17 Uhr, 03.10.2021

Antworten
Ah, ich habe leider Fehler drin.
Ich habe vergessen, dass nur die Zahlen 1 bis 3 in Frage kommen.
Dann geht es anders.

Z.B. betrachten n=4.
Die Frage ist, welche Folgen a1,...,ak die Summe 4 haben.
a1 darf also nur die Werte 1 bis 3 annehmen.
Wenn a1=1, dann haben a2+...+ak=3 und es gibt genau g3=4 solche Folgen a2,...,ak, wie wir schon wissen. Also es gibt g3=4 Folgen a1,...,ak mit a1=1 und a1+...+ak=4.
Wenn a1=2, dann haben a2+...+ak=2 und es gibt genau g2=2 solche Folgen a2,...,ak, wie wir schon wissen. Also es gibt g2=2 Folgen a1,...,ak mit a1=2 und a1+...+ak=4.
Genauso gibt's nur g1=1 Folgen mit a1=3.
Also es gilt g4=g3+g2+g1

Allgemein hätten wir gn=gn-1+gn-2+gn-3.
Frage beantwortet
Piepo

Piepo aktiv_icon

21:19 Uhr, 03.10.2021

Antworten
Vielen Dank für die ausführliche Antwort!

Hat mir sehr weiter geholfen
Antwort
HAL9000

HAL9000 aktiv_icon

10:23 Uhr, 04.10.2021

Antworten
Beim Problem OHNE Summandenlimit kommt übrigens die sehr einfache explizite Anzahl gn=2n-1 heraus.

Mit Limit ak{1,2,3} ist es etwas komplizierter, auch wenn die o.g. Lineare Differenzengleichung ebenfalls explizit lösbar ist: Für große n ergibt sich gnCλn, wobei λ die betragsgrößte Lösung der charakteristischen Gleichung x3-x2-x-1=0 ist, da kommt λ1.8393 sowie zugehörig C0.61842 raus.

Piepo

Piepo aktiv_icon

22:25 Uhr, 06.10.2021

Antworten
Wie genau würde man das jetzt mit vollständiger Induktion beweisen? Bzw. braucht es überhaupt noch einen Beweis, da es ja eigentlich aus der Definition hervorgeht?
Antwort
HAL9000

HAL9000 aktiv_icon

22:44 Uhr, 06.10.2021

Antworten
Es bedarf keiner Vollständigen Induktion, um die Rekursionsgleichung gn=gn-1+gn-2+gn-3 für n4 nachzuweisen, die ergibt sich DIREKT aus dem Sachverhalt:

Die drei Summanden in dieser Rekursiongleichung zählen die Folgen, die mit 1, 2 oder 3 beginnen - mehr Fälle gibt es nicht.

Das hatte ich übrigens schon im Beitrag 4.10.2021, 10:23 so erzählt, aber das hast du wohl nicht für voll genommen: Auch kurze Begründungen können Beweiskraft haben...
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.