Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Geschachtelte Summen

Geschachtelte Summen

Universität / Fachhochschule

Tags: Iterationsverfahren, Summenformel

GeheimAgent001254 aktiv_icon

12:25 Uhr, 16.03.2023

Hallo,

Gibt es einen allgemeinen Weg geschachtelte Summen zu berechnen?

Hab hier so einen Ausdruck und weiß nicht ob man da noch dran schrauben kann:

\sum_{i_{0} = 0}^{n} (\sum_{i_{1} = 0}^{i_{0}} (. . . (\sum_{i_{k} = 0}^{i_{k - 1}} D (i_{k} - 1, p - (k + 1))) . . .))

wobei

D (m, - 1) = 1

und

D (- 1, q) = 0

Viele Grüße

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

HAL9000 aktiv_icon

13:04 Uhr, 16.03.2023

Eine Vereinfachung ist sofort drin: Es wird über alle

(k + 1)

-Tupel

(i_{0}, i_{1}, \dots, i_{k})

summiert, für die

0 \leq i_{k} \leq i_{k - 1} \leq \dots \leq i_{0} \leq n

gilt. Da der Summand

D (i_{k} - 1, p - (k + 1))

nur vom letzten Index

i_{k}

abhängt, schauen wir mal, was für festes

i_{k}

mit

0 \leq i_{k} \leq n

passiert:

Dafür gibt es genau

(\begin{array}{c} n + k - i_{k} \\ k \end{array})

Tupel

(i_{0}, i_{1}, \dots, i_{k - 1})

mit eben jenem geforderten

i_{k} \leq i_{k - 1} \leq \dots \leq i_{0} \leq n

, somit vereinfacht sich deine Summe zu

\sum_{i = 0}^{n} (\begin{array}{c} n + k - i \\ k \end{array}) \cdot D (i - 1, p - (k + 1))

Die weitere Auswertung hängt davon ab, wie groß

p

ist - gegebenenfalls ist deine Funktion

D

auch nicht ausreichend genug definiert (z.B. dann, wenn

p \geq k + 1

ist).

GeheimAgent001254 aktiv_icon

15:59 Uhr, 16.03.2023

Hm, sorry ich habe es wohl falsch formalisiert

p

ist glaube ich

k

. Also so komme ich dazu:

D (n, p) = \sum_{i = 0}^{n} D (i, p - 1)

Wenn ich bei beliebigen n,p anfange, komme ich immer irgendwann zu p = -1 oder n = -1 und das sind quasi die Startbedingungen für die entweder 1 oder 0 definiert ist.

Ich kriege tatsächlich summierte N choose k raus...
D(10,0) = 11 (=10+1 = ncr(10,1) + ncr(10,0))
D(10,1) = 55 (=45+10 = ncr(10,2) + ncr(10,1))
D(10,2) = 165 (=120+45 = ncr(10,3) + ncr(10,2))

Das wäre ja mit ncr(n,p) + ncr(n,p+1) = ncr(n+1,p+1) und damit D(n,p)

Aber kann man das herleiten ohne, dass man erst diese Muster finden muss?
Hm, ich glaube man kann das induktiv herleiten aus der Rekursion und der Binomialkoeffizientenregel, sieht jetzt doch ganz ähnlich aus. Aber da war ich in der falschen Richtung unterwegs, weil ich das nicht gesehen hab.

HAL9000 aktiv_icon

16:18 Uhr, 16.03.2023

Ist ja schön, dass man die rekursive Definition von

D

jetzt auch mal erfährt ... sowas gehört an den Anfang!

Immer wieder ärgerlich dieses Vorenthalten WESENTLICHER Informationen, das kann einem wirklich alles verleiden. :(

--------------------------------

Tatsächlich kommt bei Rekursion

D (n, p) = \sum_{i = 0}^{n} D (i, p - 1)

für alle

n, p \in ℕ_{0}

die explizite Darstellung

D (n, p) = (\begin{array}{c} n + p + 1 \\ p + 1 \end{array})

heraus.

Deine oben berechneten Werte sind falsch, es ist

D (10, 1) = 66

und

D (10, 2) = 286

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1568690

1568686

	Status: nicht eingeloggt	Noch nicht registriert?