Summe vereinfachen (Trick gesucht)

Neue Frage »

lori97 Auf diesen Beitrag antworten »
Summe vereinfachen (Trick gesucht)
Meine Frage:
Hallo,

die Laufzeit eines Algorithmus ergibt folgende Formel die ich vereinfachen möchte:



klar ist natürlich die letzte Summe ergibt j:



Ab hier bin ich aber leider ratlos.

Ich hoffe ihr könnt mir weiterhelfen.



Meine Ideen:
Ich denke man muss mit einem Trick die Abhängigkeit von i Lösen.
klarsoweit Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Ich würde so vorgehen:



Und hierfür lassen sich einschlägige Formeln anwenden. smile
HAL 9000 Auf diesen Beitrag antworten »

Und noch ein Tipp für die äußere Summe (die über ): Für Potenzfunktionen ist es bekanntermaßen schwierig, geeignete geschlossene Summenformeln für auch für größere Exponenten aufzustellen.

Bei Summand Binomialkoeffizient statt Potenz ist es hingegen einfach: .
lori97 Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Danke für die elegante Lösung smile

Nur um sicher zu gehen:



korrekt?

Zusammen mit der ersten Summe ergibt das dann:

lori97 Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Edit:

Wobei es wahrscheinlich klüger wäre die Brüche nicht zu verbinden...
Steffen Bühler Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Passt. Wie geht es weiter? Was ist ?

Viele Grüße
Steffen
 
 
lori97 Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Meine Lösung ist mir jetzt zu lang um alles auf Latex abzutippen.
Aber ich würde die Summe auf zwei aufteilen. Die erste Summe kann man Streichen und mit (n+1) multiplizieren.
Die Zweite Summe wieder auf i^2 und i aufteilen, 1/2 rausziehen und die Formeln anwenden.
Für: hoffe ich einfach das ich für die Laufzeitanalyse mit drüberbügeln darf

Dann noch alles zusammenfassen.
Steffen Bühler Auf diesen Beitrag antworten »
RE: Summe vereinfachen (Trick gesucht)
Ich würde die Summe sogar auf vier aufteilen:



Nun schau Dir mal die einzelnen Summen an. Und auch für die Summe der ersten n Quadratzahlen gibt es eine Formel.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
.

Für k=2 heißt das .
Leopold Auf diesen Beitrag antworten »

Man kann die Summanden auch verschieden gruppieren. Setzt man



als Elemente einer oberen Dreiecksmatrix, so ist die gegebene Summation die

Summation nach Zeilen



Ebenso möglich wäre die

Summation nach Spalten



oder die

Summation nach Diagonalen



Die Summation nach Spalten scheint am schnellsten zu gehen:

(siehe HAL 9000)

Bei Kenntnissen über Potenzsummen kann man aufgrund der gegebenen Struktur schließen, daß die Summe ein Polynom in höchstens vom Grad 3 ist:



Speziell für erhält man , so daß man den Ansatz



mit noch zu bestimmenden Koeffizienten machen darf.

Man setzt ein und erhält nach geringer Vereinfachung das lineare Gleichungssystem:

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »