+5 Finden Sie eine Formel für die Summe der ersten n natürlichen Zahlen, die bei Division durch 3 den Rest 1 lassen, und beweisen Sie die Formel anschließend durch vollständige Induktion. Kann mir da jemand helfen? :)
+3976 Ich hab mal ein bisschen rumprobiert und bin zu folgendem Ergebnis gekommen:
Lässt n selbst beim Teilen durch 3 den Rest 1, so ist die gesuchte Summe einfach die Summe der ersten n Zahlen. (zB. 1 bis 7 -> 28; 1 bis 10 -> 55 etc.). Dafür gibt's die Gauß'sche Summenformel n(n+1)/2.
Für die anderen Werte von n ergibt sich durch Polynom-Interpolation die Formel 0,5n2+0,5n+1.
Ich bin mir eigentlich auch halbwegs sicher, dass sie stimmt, der Nachweis per Induktion ist aber natürlich noch zu führen.
Also, los geht's!
Der Induktionsanfang passt schonmal: Ist n=1, so ist 1 die erste Summe & 1=1*(1+1)/2.
Für den Induktionsschritt nehmen wir an, dass die Formel für n gilt, und folgern sie für n+1:
Fall 1: n=1 mod 3 (-> n+1=2 mod 3)
In diesem Fall ist die gesuchte Summe (nach Induktionsvoraussetzung) für n genau die Summe der ersten n natürlichen Zahlen, also n*(n+1)/2. Wollen wir von da aus den Rest bei Teilen durch 3 nicht verändern, so müssen wir eine Zahl hinzufügen, die selbst durch 3 teilbar ist. Die nächste, bisher ungenutzte, Zahl ist n+2. Es ist n*(n+1)/2+n+2 = 0,5n2+0,5n+n+2 = 0,5n2+1,5n+2.
Setzen wir in die erwartete Formel n+1 für n ein, so erhalten wir 0,5(n+1)2+0,5(n+1)+1 = 0,5n2+n+0,5+0,5n+0,5+1 = 0,5n2+1,5n+2 - genau das gleiche, passt also.
Fall 2: n=2 mod 3: (-> n+1=0 mod 3)
Ist n=2 mod 3, so ist die Summe so aufgebaut wie in Fall 1: Erst alle Zahlen bis n-1 (denn n-1=1 mod 3), dann noch n+1 dazu (weil n+1=0 mod 3).
Um wieder nichts am Rest beim Teilen durch 3 zu ändern, müssen wir die letzten Summanden so abändern, dass sie wieder durch 3 teilbar sind. Ist n=2 mod 3, so ist n+n+2=0 mod 3. Daher können wir die Summe aus einem Summanden mehr so aufbauen:
Erst die ersten n-1 Zahlen (hat Rest 1), dann noch n+n+2 dazu (hat Rest 0, ändert also nichts am Rest 1 der Gesamtsumme).
Der Wert der Summe ist dann die Gauß-Formel für n-1 plus n+n+2:
(n-1)*n/2+n+n+2 = 0,5n2-0,5n+2n+2 = 0,5n2+1,5n+2. Das ist, wie wir vorhin schon gesehen haben, genau der Wert der erwarteten Formel - passt also auch.
Fall 3: n=0 mod 3 (-> n+1=1 mod 3):
Ist n=0 mod 3, so setzt sich die Summe so zusammen wie oben diskutiert:
Erst die ersten n-2 Zahlen (hat Rest 1), dann noch n-1 und n+1 (haben zusammen Rest 0). Um einen Summanden mehr zu haben, können wir nun n selbst benutzen, denn n ist ja durch 3 teilbar. Dan sind's wieder genau die ersten n natürlichen Zahlen, für die genau die Gauß-Formel gilt. Damit sind wir fertig.
