Rechnen mit Summen

Neue Frage »

7 Tage Regenwetter Auf diesen Beitrag antworten »
Rechnen mit Summen
Meine Frage:
Hallo!

Ich wollte nur sichergehen, dass ich folgendes auch verstanden und deshalb richtig habe:

1) Das hier steht außer Zweifel:

2) Folgt daraus, dass ?

3) Und folgt weiter, dass ?

Meine Ideen:
Ich bin vor allem daran interessiert ob Punkt 3 stimmt, kann das vielleicht jemand bestätigen/widerlegen? Vielen Dank!
gonnabphd Auf diesen Beitrag antworten »

Zitat:
3) Und folgt weiter, dass ?


Nein. z.B.
Iorek Auf diesen Beitrag antworten »
RE: Rechnen mit Summen
Zitat:
Original von 7 Tage Regenwetter
Meine Frage:
Hallo!

Ich wollte nur sichergehen, dass ich folgendes auch verstanden und deshalb richtig habe:

1) Das hier steht außer Zweifel:


Da zweifel ich aber mal sehr stark dran unglücklich

Zitat:
Original von 7 Tage Regenwetter
2) Folgt daraus, dass ?



Nein, wie man auch leicht nachrechnet.

Zitat:
Original von 7 Tage Regenwetter
3) Und folgt weiter, dass ?


Da Punkt 2 nicht stimmt, kann Punkt 3 auch nicht stimmen. Gegenbeispiel für eine berichtigte Aussage 3) hast du allerdings auch schon bekommen.
Julian@mb Auf diesen Beitrag antworten »
RE: Rechnen mit Summen
/Edit: Dummes Zeug.
7 Tage Regenwetter Auf diesen Beitrag antworten »

Danke für die Hilfestellung, Punkt 1 ist ja tatsächlich Quatsch Finger2 es muss ja lauten

Also hmm...

Aber wie kann man dann etwas der Form berechnen?

Und vor allem, wie geht man dann mit einem Laufindex um?
gonnabphd Auf diesen Beitrag antworten »

 
 
7 Tage Regenwetter Auf diesen Beitrag antworten »

Ohje, danke Freude ganz schön doof von mir...
7 Tage Regenwetter Auf diesen Beitrag antworten »

Hm, doof oder nicht, ich blick immer noch nicht durch unglücklich

Also konkret versuche ich folgendes nachzuvollziehen:

Die Umformung von



auf



Der erste Schritt geht ja noch: multiplikation mit



aber dann... Wenn dann wäre doch (Und wenn nein: warum denn nicht?)

Wenn ich das also einsetze komme ich auf:



Naja und ab da weiss ich überhaupt nicht mehr weiter ... verwirrt

Ich nehme mal an die Summenumformung ist falsch, aber was genau?
Airblader Auf diesen Beitrag antworten »

Sowas wie



ist doch Quatsch. Wie kommst du darauf?
Eine Summe über beliebige Folgenglieder lässt sich im Allgemeinen nicht einfach angeben, wenn die Folge vom Laufindex abhängt.

Da hilft ein wenig Nachdenken: Mit dieser Gleichheit behauptest du, dass es völlig egal ist, was v_i für alle i <= n macht ... es kommt nur auf i=n+1 und i=n+2 an. Klingt das wirklich sinnvoll bei einer Summe?

Edit: Und die Umformung, die du da zeigen willst, ist im Allgemeinen schlicht falsch, wenn du nichts Näheres über die Folge der v_i weißt.

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Danke für die Antwort.

ausgeschrieben ist ja

ich hatte angenommen, dass sich die Sache ähnlich verhält wie bei



Dem ist ja aber offenbar nicht so. Ich verstehe aber immer noch nicht warum nicht, ehrlich gesagt...
Airblader Auf diesen Beitrag antworten »

Eigentlich solltest du das aber nicht mehr annehmen, denn dir wurde gesagt, dass es falsch ist und ein Gegenbeispiel genannt.

Die bessere Frage ist: Warum sollte es so sein? Wenn etwas für einen speziellen Fall gilt, dann nur selten auch für einen allgemeinen Fall. Augenzwinkern

Nochmal: Wenn diese Behauptung stimmen würde, dann wären in einer Summe aus n Summanden deiner Meinung nach also nur die letzten zwei relevant.

Also gilt z.B.

1 + 2 + 3 + 4 + 5 + 6 = 100 + 100 + 100 + 100 + 5 + 6 ?

Immerhin sind doch die letzten zwei Summanden gleich. Siehst du jetzt, wie falsch das ist? Augenzwinkern

Die Summe lässt sich für allgemeine schlicht und ergreifend nicht besser (expliziter) darstellen. Solltest du eine konkrete Folge v_i vorgegeben haben, die du uns verschweigst, sieht das natürlich anders aus.

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Ok, damit kann ich schon eher was anfangen, es IST falsch.

Ich wüsste nicht, dass irgendeine Folge gegeben wäre, wie erklärst du dir denn die Umformung, wo ist die Summe hinverschwunden?

Sozusagen ein Riesen EDIT: ich habe gerade gesehen, dass da nicht steht sondern !

Ich nehme an das ändert die Verhältnisse?
Airblader Auf diesen Beitrag antworten »

Ja, aber nur bedingt.
Vergleichen wir doch einfach mal zum Ergebnis, so sehen wir, dass - sofern die gegebene Umformung stimmt - folgendes gelten müsste:



Und wie das für allgemeine gelten soll müsste mir mal einer erklären. Das ist Quatsch!

Du kannst die linke Summe einen Tick vereinfachen: .

Außerdem entspricht der Summand ganz rechts laut Gaußscher Summenformel:



Also steht dann dort



Und wenn man die letzte Summe rüberbringt:



Und spätestens hier sollte man dann nun wirklich sehen, dass das einfach nicht stimmen kann. Links steht eine Summe über eine Folge und rechts taucht nur ein einziges Folgenglied auf. Auf der rechten Seite fehlt also eine ganze Menge an Informationen.
Wie soll sowas im Allgemeinen denn gleich werden?

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Hm, angenommen es wäre für ? Wäre das dann ein gesuchtes ?
Airblader Auf diesen Beitrag antworten »

Diese Aussage / Frage ergibt nicht besonders viel Sinn.

Du brauchst insgesamt (n+1) Folgenglieder.

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Hm, was soll ich denn jetzt machen? Du sagst, diese Umformung kann nicht stimmen, und doch steht sie so in meinem Buch.
Airblader Auf diesen Beitrag antworten »

Und doch ist jede positive Folge mit dem einen Endwert ein Gegenbeispiel, da die rechte Seite dann Null wird, die linke Seite aber offensichtlich nicht.

Nochmal: Ist da wirklich nichts über die Folge gegeben? Schreib doch mal ganz wortwörtlich den kompletten Wortlaut ab.

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Komplett alles kann ich nicht abschreiben, das ist zuviel, ich hoffe ich erwische den wichtigen Teil (es geht übrigens um den Quicksort-Algorithmus, im speziellen um die durchschnittliche Anzahl von Vergleichen). Ok, also:

"Für n > 1 ist die Anzahl der Vergleiche, die man benötigt, um das Pivotelement in die richtige Position zu bringen gleich n+1. Dazu kommt noch die zum sortieren der beiden Teillisten erforderliche Anzahl von Vergleichen, welche im Durchschnitt beträgt. Damit erhält man insgesamt



Da ist, folgt weiter



"

und jetzt kommt nur mehr der Teil den du schon kennst...
Airblader Auf diesen Beitrag antworten »

Okay.

Du kennst nun die Terme für und . Jetzt bilde einfach mal die Differenz



durch simples Einsetzen (das habe ich nun getan) und nun zusammenfassen.
Oben "übersehen" hatte ich, dass das hier sozusagen eine Rekursion ist.

air
7 Tage Regenwetter Auf diesen Beitrag antworten »

Damit hast du mir sehr geholfen, vielen Dank!

Übrig bleibt nur noch eine winzige Kleinigkeit:

warum ist ?

Wenn ich die erste Summe ausschreibe bekomme ich ja



bei der zweiten



Ach, ich komm gerade drauf dass es stimmt, es geht ja um 2 mal die Summe!

Also vielen Dank noch mal smile
Neue Frage »
Antworten »



Verwandte Themen

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