| Autor |
Beitrag |
    
Xell
| | Veröffentlicht am Samstag, den 04. August, 2001 - 16:36: | 
|
Hi Leute,
Um für Sn i=1 ik eine explizite Formel zu finden,
kann man sich für k=1 z.B. des Tricks von Gauß bedienen, um dann
Sn i=1 i = 1/2 * n * (n+1) zu ermitteln.
Für Sn i=1 i² wird das ganze Verfahren schon etwas mühsamer;
man erhält dann ein Polynom dritten Grades, nämlich
Sn i=1 i² = 1/6 * n * (n+1) * (2n+1)
Nun gibt es ein Verfahren, mit dem man explizite Formeln für beliebige
k entwickeln kann.
Angenommen, Sn i=1 ik = Sn+1 i=0 aj*xj.
Dann bestimme man A(1) = 1^k, A(2) = 1^k + 2^k, ..., A(k+2) = Sk+2 i=1 ik.
Somit erhält man k+2 Gleichungen, mit denen man das Polynom n+1-ten
Grades durch Auflösen eines linearen Gleichungssytems
bestimmen kann.
Das Problem ist jetzt nur, zu beweisen, dass die Summe immer durch
ein Polynom n+1-ten Grades dargestellt werden kann.
Wer Ideen hat, der melde sich hier bitte.
lg, Xell |
superknowa
| | Veröffentlicht am Samstag, den 04. August, 2001 - 17:32: |
|
Hi Xell
meinst Du im Mittelteil
"Angenommen, Sn i=1 ik = Sk+1 j=0 aj*nj "? |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 04. August, 2001 - 17:55: |
|
Das geht auch mit Induktion.
Anfang: k=1 ist ok.
Behauptung: k -> k+1
Nun kann man Sn i=1 ik+1 = Sn i=1 ik * Sn i=1 i1 - Rest schreiben.
Im Rest ist die ik die höchste Potenz.
Gruß
Matroid |
superknowa
| | Veröffentlicht am Samstag, den 04. August, 2001 - 17:59: |
|
Also erstmal muss die Matrix
| 10 | 11 | ... | 1k+1 | | 20 | 21 | ... | 2k+1 | | 30 | 31 | ... | 3k+1 | | ... | ... | ... | ... | | (k+2)0 | (k+2)1 | ... | (k+2)k+1 |
invertierbar sein, damit eine Lösung des Gleichungssystems eindeutig bestimmt ist. |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 04. August, 2001 - 19:09: |
|
Ich muß mich verbessern. Die Idee ist:
Sn i=1 ik+1 = ?
Es ist
nk+1 - (n-1)k+1
= binom(k+1,1)*nk - binom(k+1,2)*nk-1 +/- ...
und weiter
(n-1)k+1 - (n-2)k+1
= binom(k+1,1)*(n-1)k - binom(k+1,2)*(n-1)k-1 +/- ...
(n-2)k+1 - (n-3)k+1
= binom(k+1,1)*(n-2)k - binom(k+1,2)*(n-2)k-1 +/- ...
...
2k+1 - 1k+1
= binom(k+1,1)*2k - binom(k+1,2)*2k-1 +/-
1k+1 - 0k+1
= binom(k+1,1)*1k - binom(k+1,2)*0k-1 +/-
Die Addition aller linken Seiten ergibt nk+1.
Die Addition aller rechten Seiten eine komplizierte Summe, in der aber der höchste Exponent k ist.
Etwa so (für j=1,...,n)
jk+1 = Sn r=0 Sk+1 m=1 binom(k+1,m)*(-1)m+1 * (j-r)k-m+1
Also ist Sn i=1 ik+1 = Sn i=1 Sn r=0 Sk+1 m=1 binom(k+1,m)*(-1)m+1 * (j-r)k-m+1
Nun kann man die drei Summenzeichen vertauschen und wird dann hoffentlich was sehen.
Weil darin der höchste Exponent k ist, kann man die Induktionsvoraussetzung ("die Behauptung gelte für alle Exponenten < k+1") vielfach anwenden.
Für k=3 sieht das so aus:
n3 - (n-1)3 = 3n² - 3n + 1
(n-1)3 - (n-2)3 = 3(n-1)² - 3(n-1) + 1
(n-2)3 - (n-3)3 = 3(n-2)² - 3(n-2) + 1
...
23 - 13 = 3*2² - 3*2 + 1
13 - 03 = 3*1² - 3*1 + 1
----------------------------------
Summe der linken Seiten ist n3.
Summe der rechten Seiten ist formal eine Doppelsumme, in der der höchste Exponent k-1 ist. |
zipper
| | Veröffentlicht am Samstag, den 04. August, 2001 - 19:27: |
|
In der Summe
1+1+...+1
ist 0 die höchste Potenz von n; zählt man aber n
der 1'er zusammen, dann erhält man n=n1, also eine höhere Potenz.
Das sollte nachdenklich machen.
Gruß
zipper |
superknowa
| | Veröffentlicht am Samstag, den 04. August, 2001 - 20:44: |
|
Die Matrix von oben ist invertierbar mit der Determinante
D= 0! * 1! * 2! * ... * (k+1)!
ohne Beweis, nur mit der Begründung, dass die j.-ten Differenzen von Potenzen mit der Hochzahl j stets die Konstante j! liefert.
Im ersten Schritt zieht man die erste von der zweiten Zeile, die zweite von der dritten, usw. bis die vorletzte von der letzten ab; dann stehen in der 1. Spalte lauter 0-en, bis auf links oben (Diagonalelement (a1;1) ; da steht die 1=0!.
Im zweiten Schritt zieht man die zweite von der dritten, die dritte von der vierten usw. bis die vorletzte von der letzten ab; dann stehen in der zweiten Spalte lauter Nullen unter dem Diagonalelement a2;2 mit dem Wert 1=1!.
Im dritten Schritt zieht man die dritte von der vierten usw. bis die vorletzte von der letzten ab. Dann stehen unter dem Diagonalelement a3;3=2=2! lauter Nullen.
Nach dem vierten Schritt stehen unter dem Diagonalelement a4;4=6=3! lauter Nullen.
Im (k+1).-ten Schritt hat man eine Diagonalmatrix mit lauter Fakultäten in der Diagonalen, die links oben mit a1;1=0! beginnen und rechts unten mit ak+2;k+2=(k+1)! enden.
Die Matrix ist also umkehrbar und ein Polynom existiert, das die (k+2) Bedingungen erfüllt.
Warum aber erfüllt das Polynom für alle n die geforderte Beziehung (und nicht nur für die ersten (k+2))? |
Xell
| | Veröffentlicht am Samstag, den 04. August, 2001 - 21:21: |
|
Hi nochmal,
Ich erfreue mich hier der regen Beteiligung eurerseits, werde
allerdings erst morgen dazu kommen, mir das Ganze durchzulesen.
Was Matrizen und Determinanten angeht, weiß ich noch nicht so gut
Bescheid, werde mich dann aber bemühen, die richtigen Fragen zu
stellen, damit ich eure Beweisversuche auch verstehen kann.
Soweit ich das sehen konnte beim Überfliegen steht ein endgültiger
Beweis noch nicht !?
Morgen werd' ich nochmal reinschauen und was schreiben. Macht's
gut und danke für euer Interesse.
lg
P.S.: Im Anschluss wär es noch interessant, Varianten zu dem
vorgeschlagenen Verfahren zur Auffindung der expliziten Formeln
zu suchen, da dieses doch schnell aufwendig werden dürfte
für große k... |
Niels
| | Veröffentlicht am Sonntag, den 05. August, 2001 - 14:56: |
|
Hallo alle zusammen,
Ich möchte an dieser Stelle schonmal Die Rechnung mit dem Polynomansatz für k=3 und k=4 führen.
Also der Ansatz für k=3:
bn=Sn i=1i3
bn=bn-1+n3
Ansatz: bn ist ein Polynom k+1 ter Ordnung
bn=An4+Bn³+Cn²+Dn+E
Analog:
bn-1=A(n-1)4+B(n-1)³+C(n-1)²+D(n-1)+E
=>
An4+Bn³+Cn²+Dn+E=A(n-1)4+B(n-1)³+C(n-1)²+D(n-1)+E+n³
Und das wird nun eine verdammte Rechnerei die aber bewältigbar ist...
An4+Bn³+Cn²+Dn+E=An4-4An³+6An²-4An+A+Bn³-3Bn²+3Bn-B+Cn²-2Cn+C+Dn-D+E+n³
0=(1-4A)n³+(6A-3B)n²+(3B-4A-2C)n+(A-B+C-D)
E hebt sich weg und spielt keine Rolle mehr. E=0
Gleichungssystem:
1-4A=0
6A-3B=0
3B-4A-2C=0
A+C-B-D=0
Löst man dieses so erhält man:
A=1/4
B=1/2
C=1/4
D=0
Unser Polynom sieht also mit den eben errechneten Koeffizienten wiefolgt aus:
bn=(1/4)*n4+(1/2)n³+(1/4)n²
bn=n4+2n³+n²/4
bn=n²*(n²+2n+1)/4
bn=n²*(n+1)²/4
bn=(n*(n+1)/2)²
bn=Sn i=1i3=(n*(n+1)/2)²
Und Das ist die berüchtigte Summenformel der 3. Potenzen/Kuben der ersten n natürlichen Zahlen!!!
=================================================
Wer möchte kann ja diese Formel durch Induktion Beweisen.
Der Ansatz für k=4 funktioniert Analog und folgt später.
Viele Grüße
Niels |
Xell
| | Veröffentlicht am Sonntag, den 05. August, 2001 - 17:05: |
|
Hi Niels,
Zu beweisen gilt es ja gerade, dass Sn i=1 i^k tatsächlich
durch ein Polynom k+1-ten Grades darstellbar ist. Dass das Verfahren
unter dieser Voraussetzung funktioniert, habe ich ja schon im
ersten posting begründet (angenommen, das lineare Gleichungssystem
ist stets auflösbar für alle k aus IN).
Sinnvoller wäre es hier m.E. eher, ein Programm zu schreiben,
das bei angegebenem k die Koeffizienten a_{k+1}, a_k, ..., a_1, a_0
berechnet. Damit hätte man dan jeweils das Polynom bestimmt.
Allerdings macht mir, wie bereits erwähnt, die sicherlich schnell
ansteigende Rechenzeit bei steigendem k zu schaffen
(Bezieht sich auf das von mir angegebene Verfahren).
lg |
Carmichael (Carmichael)
| | Veröffentlicht am Sonntag, den 05. August, 2001 - 18:41: |
|
HI Leute!
Wir gehen aus von der geomtrischen Folge:
1 + Y + Y^2 + ... + Y^x = (1-Y^(x+1))/(1-Y);
es sei F(Y) := (1-Y^(x+1))/(1-Y);
diese differenzieren wir mal nach Y:
dann steht da:
1 + 2*Y + 3*Y^2 + ... + x*Y^(x-1) = F'(Y);
differenziert man k-mal so steht da:
k! + (k+1)!/1!*Y + .... + (k+x)!/x!*Y^(x-k) = F(k)(Y);
wir setzten Y -> 1 (wird schon Sätze geben, die sowas zulassen :-)) ein, dann kommt raus:
lim Y->1 k! + (k+1)!/1! + .... + (k+x)!/x! = F(k)(Y);
die linke seite lässt sich anders schreiben:
(ab jetzt: Y->1)
Sx i=0 (i+k)!/i! = F(k)(Y->1);
Sx i=0 (i+k)(i+k-1)*..*(i+1) = F(k)(Y->1);
P(i) := (i+k)(i+k-1)*..*(i+1) ist ein Polynom mit der Variablen i vom Grade k.
es lässt sich also so darstellen:
P(i) = a_k*i^k + a_(k-1)*i^(k-1) + ... + a_0;
=>
Sx i=0 a_k*i^k + Sx i=0 a_(k-1)*i^(k-1) + ... + Sx i=0 a_0 = F(k)(Y->1);
die a_0,a_1,..,a_k sind natürlich unabhängig von x (sie hängen ja nur von k ab); wir ziehen sie daher aus der summe raus und erhalten:
a_k*Sx i=0 i^k = F(k)(Y->1) - a_(k-1)*Sx i=0 i^(k-1) - ... - a_0*Sx i=0 1 ;
jetzt gilt des nur noch zu zeigen dass F(k)(Y->1), also die k-te Ableitung von F(Y) nach Y, ein Polynom mit der Variablen k höchenstens vom Grade k+1 ist und wir sind fertig (mit Hilfe leichter Induktion nach k).
Wegen dem Y->1 braucht man L'Hopital.
Beispiel:
[(Y^k-1)/(Y-1)]' = [(k-1)*Y^k - k*Y^(k-1) + 1]/(Y-1)^2;
jetzt Y -> 1 und wir haben "0/0"
schließlich ergibt sich dann:
lim Y->1 [(Y^k-1)/(Y-1)]' = n*(n-1)/2; und das war ja zu erwarten..
MfG |
Xell
| | Veröffentlicht am Freitag, den 14. September, 2001 - 15:30: |
|
Hi Carmichael,
Ein etwas später Nachtrag, ich hoffe aber trotzdem, dass
du ihn noch liest.
Ich sehe zwar, dass der Beweis funktioniert, aber wie bist du
darauf gekommen ? Ich meine die Idee, von der geometrischen
Reihe auszugehen ist nicht gerade die naheliegendste...
Grüße, Xell |
Carmichael (Carmichael)
| | Veröffentlicht am Freitag, den 14. September, 2001 - 16:47: |
|
HI,
hm so genau weiß ich das nicht mehr.
Ich wusste aber schon, dass man die geom. Folge ableiten kann.
Naja, man probiert halt etwas rum, erinnert sich an alte Sachen, fängt an diese irgendwie anzuwenden und kommt halt dann irgendwann drauf. |
|
