gleiche Summen

30.10.2011, 23:53

Paradiesvogel

Auf diesen Beitrag antworten »

gleiche Summen

Meine Frage:
Hallo Leute!

Wie die Überschrift sagt, sitze ich hier an einer Gleichung aus Summen und komme einfach nicht weiter. Die Gleichung heißt:

$\begin{eqnarray*} \sum \limits_{k=0}^{n} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n-k}\right) = \sum \limits_{k=0}^{n} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+1) \right) \end{eqnarray*}$

p ist hierbei eine Primzahl.

Meine Ideen:
Ich habe schon alles mögliche versucht. Die einzelnen Summanden stimmen nicht überein. Durch einfaches Umformen der Gleichung komme ich also zu keinem Ergebnis. Ich habe auch versucht, mit Beispielen die einzelnen Summanden irgendwie in einen sinnvollen Zusammenhang zu bringen, aber das nützt alles nichts.

Ich weiß nun nicht mehr weiter und wäre sehr dankbar, wenn mir jemand helfen könnte. Vielen Dank!

Paradiesvogel

31.10.2011, 13:58

klarsoweit

Auf diesen Beitrag antworten »

RE: gleiche Summen
Hast du es schon mal mit vollständiger Induktion versucht?

Übrigens ist es wurscht, ob p eine Primzahl ist oder nicht. Augenzwinkern

Augenzwinkern

31.10.2011, 14:48

Paradiesvogel

Auf diesen Beitrag antworten »

Ja!
Ja, ich habe auch vollständige Induktion versucht. Das Problem ist, dass ich auch dafür die beiden Formeln ineinander umformen muss und das nicht hinbekomme.

31.10.2011, 14:52

klarsoweit

Auf diesen Beitrag antworten »

RE: Ja!
Dann schreib mal, wie weit du gekommen bist.

31.10.2011, 23:39

Paradiesvogel

Auf diesen Beitrag antworten »

...
Naja, wenn man eine Induktion machen will, dann ja nach n. Induktionsanfang ist ja klar und geht auch ohne Probleme auf. Dann folgt der Induktionsschritt wie immer und bei der Induktionsbehauptung ersetze ich n durch n+1.
Danach stehe ich aber vor dem gleichen Problem, wie vorher auch und kann es nicht umformen...

01.11.2011, 09:08

klarsoweit

Auf diesen Beitrag antworten »

Re: ...
Solange du nicht deine Rechnung hinschreibst, kann ich dir beim besten Willen nicht helfen. geschockt

geschockt

Anzeige

01.11.2011, 10:43

Paradiesvogel

Auf diesen Beitrag antworten »

Induktion
OK, bitte entschuldige. Ich dachte, es wäre eindeutig, was ich meine. Nun kommt hier noch einmal die Induktion in allen Einzelheiten:
$\begin{eqnarray*} \sum \limits_{k=0}^{n} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n-k} \right) = \sum \limits_{k=0}^{n} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+1) \right) \end{eqnarray*}$

Das ist die Funktion. Der Induktionsanfang müsste demnach so aussehen: (n=0)
$\begin{eqnarray*} \sum \limits_{k=0}^{0} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n-k} \right) = \sum \limits_{k=0}^{0} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+1) \right) \end{eqnarray*}$
$\begin{eqnarray*} \left( \frac{2}{2} \cdot p^{0} \right) = \left( \frac{p-1}{p-1} \cdot 1 \right) \end{eqnarray*}$
$\begin{eqnarray*} 1 = 1 \end{eqnarray*}$ w.A.

Die Induktionsvoraussetzung sagt dann, dass die oben genannte Gleichung für ein festes n gilt.

Die Induktionsbehauptung heißt dann:
$\begin{eqnarray*} \sum \limits_{k=0}^{n+1} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} \right) = \sum \limits_{k=0}^{n+1} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+2) \right) \end{eqnarray*}$

Der Induktionsbeweis beginnt dann mit
$\begin{eqnarray*} \sum \limits_{k=0}^{n} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n-k} \right) = \sum \limits_{k=0}^{n} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+1) \right) \end{eqnarray*}$
und daraus muss ich irgendwie
$\begin{eqnarray*} \sum \limits_{k=0}^{n+1} \left( \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} \right) = \sum \limits_{k=0}^{n+1} \left( \frac{p^{k+1}-1}{p-1} \cdot (n-k+2) \right) \end{eqnarray*}$
folgern, aber dazu muss ich es doch trotzdem irgendwie umformen, oder? Wie soll das gehen?

01.11.2011, 10:49

René Gruber

Auf diesen Beitrag antworten »

Du könntest versuchen, die linke Seite der Induktionsbehauptung soweit umzuformen, dass du in der Induktionsvoraussetzung auftauchende Strukturen nutzen kannst. Da ist es naheliegend, den letzten Summanden erstmal abzutrennen sowie aus der Restsumme einen Faktor $\begin{eqnarray*} p \end{eqnarray*}$ herauszulösen:

$\begin{eqnarray*} \sum \limits_{k=0}^{n+1} \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} &=& \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} ~+~ \frac{(n+2)(n+3)}{2}\\ &=& p \cdot \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} ~+~ \frac{(n+2)(n+3)}{2} \end{eqnarray*}$

01.11.2011, 11:56

Paradiesvogel

Auf diesen Beitrag antworten »

Du hast etwas vergessen!!
Wenn du den letzten Summanden aus der Summe herausziehst, musst du doch aber auch den Faktor p^(...) mit rausziehen. Der steht ja schließlich auch mit in der Summe drin, oder sehe ich das falsch?

Das ist zwar eine gute Idee, aber was nützt mir das für den Induktionsbeweis? Kann man das tatsächlich ineinander umformen?

01.11.2011, 12:02

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Paradiesvogel
Wenn du den letzten Summanden aus der Summe herausziehst, musst du doch aber auch den Faktor p^(...) mit rausziehen.

Mitrechnen würde dir so manche unnötige Frage ersparen: Im letzten Summanden ist $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ , also ist diese $\begin{eqnarray*} p \end{eqnarray*}$ -Potenz dort gleich

$\begin{eqnarray*} p^{n+1-k} = p^{n+1-(n+1)} = p^0 = 1 \end{eqnarray*}$ .

P.S.: Ich bin dann mal weg, ein Helfer ist genug (zumal dann, wenn es klarsoweit ist). Augenzwinkern

Augenzwinkern

01.11.2011, 12:04

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Paradiesvogel
Wenn du den letzten Summanden aus der Summe herausziehst, musst du doch aber auch den Faktor p^(...) mit rausziehen. Der steht ja schließlich auch mit in der Summe drin, oder sehe ich das falsch?

Wie sieht denn der Faktor aus?

Zitat:

Original von Paradiesvogel
Das ist zwar eine gute Idee, aber was nützt mir das für den Induktionsbeweis? Kann man das tatsächlich ineinander umformen?

Ja. Mache mit

$\begin{eqnarray*} p \cdot \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} ~+~ \frac{(n+2)(n+3)}{2} \end{eqnarray*}$

eine Indexverschiebung, so daß die Summe bei k=1 beginnt und mit k=n+1 endet.

01.11.2011, 18:25

Paradiesvogel

Auf diesen Beitrag antworten »

Indexverschiebung!
Oh, tut mir leid. Das habe ich gar nicht gesehen. Stimmt, dann kann man den Faktor natürlich weglassen. Ich versuche jetzt mal die, von dir vorgeschlagene, Indexverschiebung.

$\begin{eqnarray*} p \cdot \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} + \frac{(n+2)(n+3)}{2} \end{eqnarray*}$
Wenn die Summe wieder bei n+1 enden soll, muss der letzte Summand wieder hineingezogen werden, also:
$\begin{eqnarray*} \sum \limits_{k=0}^{n+1} \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} \end{eqnarray*}$
Jetzt soll die Summe bei k=1 beginnen, also muss der 0-te Summand herausgezogen werden.
$\begin{eqnarray*} \sum \limits_{k=1}^{n+1} \frac{(k+1)(k+2)}{2} \cdot p^{n+1-k} + p^{n+1} \end{eqnarray*}$

Ich hoffe, dass das so stimmt.

01.11.2011, 19:44

René Gruber

Auf diesen Beitrag antworten »

Hmm, ich erkenne leider nicht, was klarsoweit mit seinem Vorschlag bezweckt. verwirrt

verwirrt

Ich jedenfalls hätte erstmal für $\begin{eqnarray*} \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} \end{eqnarray*}$ die rechte Seite der Induktionsvoraussetzung eingesetzt und erst anschließend so eine Indexverschiebung vorgenommen.

01.11.2011, 20:37

Paradiesvogel

Auf diesen Beitrag antworten »

Ahh!!
Ich glaube, ich weiß, was ihr meint. Ich habe die ganze Zeit gedacht, ich muss die beiden Aussagen ineinander umformen, aber wenn ich die Induktionsvoraussetzung da anwende, ist es ja praktisch das gleiche. Ich versuche es gleich mal, aber bist du wirklich sicher, dass das so funktioniert? Ich habe es schon mal versucht, die Summanden einzeln zu betrachten und die haben nicht übereingestimmt. Vielleicht klappt es dann so auch nicht, aber ich werde es versuchen. Vielen Dank für den Tipp!

01.11.2011, 20:45

Leopold

Auf diesen Beitrag antworten »

Wenn du den Induktionsbeweis hinter dir hast, kannst du dir einmal den folgenden Beweis betrachten. Es geht nämlich ganz ohne Induktion, wenn man die geometrische Reihe verwendet. Dann rechnet man von rechts nach links so:

$\begin{eqnarray*} \sum_{k=0}^n \frac{p^{k+1}-1}{p-1} \cdot (n-k+1) = \sum_{k=0}^n \sum_{j=0}^k p^j (n-k+1) = \sum_{j=0}^n \sum_{k=j}^n p^j (n-k+1) = \sum_{j=0}^n p^j \sum_{k=j}^n (n-k+1) \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{j=0}^n p^j \sum_{k=1}^{n-j+1} k = \sum_{j=0}^n \left( p^j \cdot \frac{1}{2} (n-j+1)(n-j+2) \right) = \sum_{j=0}^n \left( p^{n-j} \cdot \frac{1}{2} (j+1)(j+2) \right) \end{eqnarray*}$

1. Gleichheitszeichen: geometrische Reihe
2. Gleichheitszeichen: Summationen vertauschen (siehe unten)
3. Gleichheitszeichen: von $\begin{eqnarray*} k \end{eqnarray*}$ unabhängigen Faktor vor die innere Summe ziehen
4. Gleichheitszeichen: In der inneren Summe Reihenfolge der Summanden invertieren
5. Gleichheitszeichen: Formel für Dreieckszahlen (kleiner Gauß)
6. Gleichheitszeichen: Reihenfolge der Summanden invertieren

In einer Doppelsumme der Art $\begin{eqnarray*} \sum_{k=0}^n \sum_{j=0}^k a_{kj} \end{eqnarray*}$ kann man die Summanden in einem Dreieck anordnen:

$\begin{eqnarray*} \begin{matrix} a_{00} \\ a_{10} & a_{11} \\ a_{20} & a_{21} & a_{22} \\ \vdots & \vdots & \vdots \\ a_{n0} & a_{n1} & a_{n2} & \ldots & a_{nn} \end{matrix} \end{eqnarray*}$

In der obigen Form wird zeilenweise summiert. In der Form $\begin{eqnarray*} \sum_{j=0}^n \sum_{k=j}^n a_{kj} \end{eqnarray*}$ wird spaltenweise summiert.

01.11.2011, 20:46

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Paradiesvogel
aber bist du wirklich sicher, dass das so funktioniert?

Eine ziemliche Frechheit: Finde mal einen Thread hier im Board, wo mein Tipp nicht funktioniert (es gibt natürlich einige, wo mein Tipp ignoriert wird). Augenzwinkern

Augenzwinkern

Es klappt schon, allerdings ist noch etwas Zusatzarbeit nötig, wie man nach dem Einsetzen unschwer sieht.

01.11.2011, 22:24

Paradiesvogel

Auf diesen Beitrag antworten »

Wow!
Wow! Viel mehr kann man dazu nicht sagen. Seit Tagen versuche ich die Gleichung mit Induktion und irgendwelchen fiesen Tricks zu knacken und du machst das mal eben direkt. Der Beweis ist mir klar. Vielen Dank dafür.

Bei der Induktion komme ich leider trotz allem zu keinem sinnvollen Ergebnis. Wenn ich den Summanden wie oben rausziehe und dann dann die Summe ersetze sieht das zwar nicht schlecht aus, aber wenn ich dann noch einen Summanden zu der Summe hinzufüge und außerhalb wieder abziehe sieht man, dass sich da nichts auflöst. Ich kann noch ein wenig rumrechnen, aber zumindest das p vor der Summe wird nicht so einfach verschwinden.
Wenn ich den Versuch von der anderen Seite komme ich auch nicht viel weiter. Hast du es durchprobiert? Ist es bei dir aufgegangen?

@ René Gruber: Ich wollte dich auf keinen Fall beleidigen, aber ich habe keinen Zugang gefunden und da habe ich gefragt, ob du dir sicher bist. Verzeih' bitte.

02.11.2011, 07:11

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Paradiesvogel
Ich wollte dich auf keinen Fall beleidigen, aber ich habe keinen Zugang gefunden und da habe ich gefragt, ob du dir sicher bist. Verzeih' bitte.

Der Smilie am Ende sollte eigentlich andeuten, dass ich es so ernst nicht gemeint hatte. smile

smile

02.11.2011, 09:12

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Hmm, ich erkenne leider nicht, was klarsoweit mit seinem Vorschlag bezweckt. verwirrt

verwirrt

Ich jedenfalls hätte erstmal für $\begin{eqnarray*} \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} \end{eqnarray*}$ die rechte Seite der Induktionsvoraussetzung eingesetzt und erst anschließend so eine Indexverschiebung vorgenommen.

Sorry, das hatte ich auch gemeint. Hammer

Hammer

Also so läuft das:

$\begin{eqnarray*} p \cdot \sum \limits_{k=0}^{n} \frac{(k+1)(k+2)}{2} \cdot p^{n-k} + \frac{(n+2)(n+3)}{2} = p \cdot \sum \limits_{k=0}^{n} \frac{p^{k+1} - 1}{p-1} \cdot (n-k+1) + \frac{(n+2)(n+3)}{2} \end{eqnarray*}$

Jetzt die Indeverschiebung:

$\begin{eqnarray*} ... = p \cdot \sum \limits_{k=1}^{n+1} \frac{p^k - 1}{p-1} \cdot (n-k+2) + \frac{(n+2)(n+3)}{2} = \sum \limits_{k=0}^{n+1} \frac{p^{k+1} - 1 + 1 - p}{p-1} \cdot (n-k+2) + \frac{(n+2)(n+3)}{2} \end{eqnarray*}$

$\begin{eqnarray*} = \sum \limits_{k=0}^{n+1} \frac{p^{k+1} - 1}{p-1} \cdot (n-k+2) + \sum \limits_{k=0}^{n+1} \frac{1 - p}{p-1} \cdot (n-k+2) + \frac{(n+2)(n+3)}{2} \end{eqnarray*}$

Die 1. Summe entspricht dem, was man haben will. Wenn man nun noch $\begin{eqnarray*} \frac{1 - p}{p-1} \end{eqnarray*}$ zu -1 kürzt, kann man die 2. Summe mit bekannten Regeln umformen. Der Rest ist dann simpel.

02.11.2011, 10:44

Paradiesvogel

Auf diesen Beitrag antworten »

Ich hab's noch nicht ganz.
Vielen Dank für die Rechnung. Allerdings habe ich es an einigen Stellen noch nicht ganz verstanden. Wir nehmen also die Induktionsbehauptung und ziehen den letzten Summanden aus der Summe. Danach wird ein Faktor p nach vorne gezogen. Damit sieht es aus, wie die Induktionsvoraussetzung und wir können die ersetzen. Dann hast du eine Indexverschiebung gemacht, die ich nicht verstehe. In deiner Rechnung stehen da auch drei Punkte, aber ich bin mir nicht sicher, wie das funktioniert. Wenn ich jetzt einen neuen Index i nenne, der k+1 darstellt werden die Enden der Summe so, wie du es geschrieben hast, aber in dem letzten Faktor würde dann nicht (n-k+2), sondern nur (n-k) stehen. (Wenn man i dann wieder k nennen würde.) Wie hast du das gemacht? Ich komme einfach nicht hinter. Danke!

02.11.2011, 10:55

klarsoweit

Auf diesen Beitrag antworten »

In $\begin{eqnarray*} \sum \limits_{k=0}^{n} \frac{p^{k+1} - 1}{p-1} \cdot (n-k+1) \end{eqnarray*}$ ersetze ich i = k+1 bzw. k = i - 1. Dann ist i_u = k_u + 1 = 1 und i_o = k_o + 1 = n+1 . Alles einsetzen ergibt:

$\begin{eqnarray*} ... = \sum \limits_{i=1}^{n+1} \frac{p^i - 1}{p-1} \cdot (n - (i-1) + 1) \end{eqnarray*}$

Jetzt wieder i = k setzen und voilà. Augenzwinkern

Augenzwinkern

Die 3 Punkte ... beziehen sich nur auf den vorigen Ausdruck. Den wollte ich nicht wiederholen.

02.11.2011, 11:00

Leopold

Auf diesen Beitrag antworten »

Zwischenbemerkung:

Für die Summe kann man auch einen geschlossenen Ausdruck angeben, nämlich

$\begin{eqnarray*} \frac{2(p-1)p^{n+3} - (n+2)(n+3)p^3 + (n+3)(3n+4)p^2 - (n+1)(3n+8)p + (n+1)(n+2)}{2(p-1)^4} \end{eqnarray*}$

Die Herleitung erfolgte mit Hilfe eines CAS über die Funktion

$\begin{eqnarray*} g(x) = \frac{1}{2} \sum_{k=1}^{n+1} x^{-k} = \frac{x^{-n-1}-1}{2(1-x)} \end{eqnarray*}$

Die gesuchte Summe ist nämlich gerade $\begin{eqnarray*} p^{n+3} g''(p) \end{eqnarray*}$ .
Numerische Ergebnisse bestätigen die Richtigkeit der Formel.

EDIT
Und das Ergebnis kann man auch noch durch $\begin{eqnarray*} p-1 \end{eqnarray*}$ kürzen:

$\begin{eqnarray*} \frac{2p^{n+3} - (n+2)(n+3)p^2 + 2(n+1)(n+3)p - (n+1)(n+2)}{2(p-1)^3} \end{eqnarray*}$

02.11.2011, 18:12

Paradiesvogel

Auf diesen Beitrag antworten »

Ahh!!
Stimmt ja! Ich Depp wollte k+1 ersetzen, obwohl ein Minus davor stand... Argh... Ich Depp!! Jetzt hab' ich's aber endlich, denke ich. Zumindest geht es jetzt endlich auf. Vielen, vielen Dank für eure Hilfe. Alleine wäre ich hoffnungslos untergegangen. Vielen Dank an alle, die mir geholfen haben! Danke!!

Paradiesvogel

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »