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

Piepo aktiv_icon

19:51 Uhr, 03.10.2021

Moin,

das hier war eine Frage in einer meiner Klausuren:

Für n ∈ N sei

g_{n}

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

g_{1}

= 1,

g_{2}

= 2,

g_{3}

= 4. Finden Sie eine Rekursionsgleichung für die Folge (

g_{n})_{n \in N}

.

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."

DrBoogie aktiv_icon

20:56 Uhr, 03.10.2021

Den Fall

a_{1} + . . . + a_{k} = n

kann man in die Fälle

a_{1} = n

a_{1} = n - 1

a_{1} = n - 2

,...,

a_{n} = 1

unterteilen, was zu

g_{n} = 1 + g_{1} + g_{2} + . . . + g_{n - 2} + g_{n - 1}

führt.

Piepo aktiv_icon

21:07 Uhr, 03.10.2021

Ich verstehe nicht ganz, was mit dem Fall

a_{1} + . . . + a_{k} = 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...

HAL9000

21:15 Uhr, 03.10.2021

@DrBoogie

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

Es ist für

n \geq 4

daher einfach

g_{n} = g_{n - 1} + g_{n - 2} + g_{n - 3}

, was die drei Fälle abdeckt, dass die Summandenfolge mit 1,2 oder 3 beginnt.

DrBoogie aktiv_icon

21:17 Uhr, 03.10.2021

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

a_{1}, . . ., a_{k}

die Summe 4 haben.

a_{1}

darf also nur die Werte

1

bis

3

annehmen.
Wenn

a_{1} = 1

, dann haben

a_{2} + . . . + a_{k} = 3

und es gibt genau

g_{3} = 4

solche Folgen

a_{2}, . . ., a_{k}

, wie wir schon wissen. Also es gibt

g_{3} = 4

Folgen

a_{1}, . . ., a_{k}

mit

a_{1} = 1

und

a_{1} + . . . + a_{k} = 4

.
Wenn

a_{1} = 2

, dann haben

a_{2} + . . . + a_{k} = 2

und es gibt genau

g_{2} = 2

solche Folgen

a_{2}, . . ., a_{k}

, wie wir schon wissen. Also es gibt

g_{2} = 2

Folgen

a_{1}, . . ., a_{k}

mit

a_{1} = 2

und

a_{1} + . . . + a_{k} = 4

.
Genauso gibt's nur

g_{1} = 1

Folgen mit

a_{1} = 3

.
Also es gilt

g_{4} = g_{3} + g_{2} + g_{1}

Allgemein hätten wir

g_{n} = g_{n - 1} + g_{n - 2} + g_{n - 3}

Piepo aktiv_icon

21:19 Uhr, 03.10.2021

Vielen Dank für die ausführliche Antwort!

Hat mir sehr weiter geholfen

HAL9000

10:23 Uhr, 04.10.2021

Beim Problem OHNE Summandenlimit kommt übrigens die sehr einfache explizite Anzahl

g_{n} = 2^{n - 1}

heraus.

Mit Limit

a_{k} \in {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

g_{n} \approx C \cdot λ^{n}

, wobei

λ

die betragsgrößte Lösung der charakteristischen Gleichung

x^{3} - x^{2} - x - 1 = 0

ist, da kommt

λ \approx 1.8393

sowie zugehörig

C \approx 0.61842

raus.

Piepo aktiv_icon

22:25 Uhr, 06.10.2021

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?

HAL9000

22:44 Uhr, 06.10.2021

Es bedarf keiner Vollständigen Induktion, um die Rekursionsgleichung

g_{n} = g_{n - 1} + g_{n - 2} + g_{n - 3}

für

n \geq 4

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.

1542174

1542048

	Status: nicht eingeloggt	Noch nicht registriert?