Induktionsbeweis bei einer Ungleichung

Question

Aufgabe:

In einem Buch (courses.arch.ntua.gr/fsr/113705/Hopkroft-Book.pdf ) las ich, dass gelte:
k + k²+...+kⁿ <= (k+1)ⁿ⁺¹.
Dies wollte ich über vollständige Induktion nachweisen. Ich habe dazu 2 Ansätze ausprobiert und bin zwei Mal beim Übergang von n nach n+1 gescheitert. Nun hoffe ich, dass mir jemand einen Rat geben kann.
Vielen Dank!

Problem/Ansatz:

Ansatz#1:

k + k²+...+kⁿ = ∑kⁱ, i=1 ... n, somit zu beweisen: ∑kⁱ, i=1 ... n <= (k+1)ⁿ⁺¹.

Sei n=1. Linke Seite: k¹ = k
              Rechte Seite: (k+1)²  = k²+2k+1
OK für n=1

Angenommen die Behauptung gelte für ein n, dann ist noch zu beweisen, dass sie auch für n+1 gilt. Also: k + k²+...+kⁿ+kⁿ⁺¹ <= (k+1)ⁿ⁺²

Nun gilt für die linke Seite nach Induktionsannahme, dass k + k²+...+kⁿ  <= (k+1)ⁿ⁺¹ ist.
"Und dann verließen sie ihn".

Ansatz#2:

k + k²+...+kⁿ als "Fast-"Partialsumme für die geometrische Reihe zu betrachten, diese läuft aber bei i=0 los. Also: 1+ k + k²+...+kⁿ <= (k+1)ⁿ⁺¹+1 (diese "1" ist die, die ich auch auf der linken Seite addiert habe, um der Definition der Partialsumme der geometrischen Reihe zu genügen).
Die Partialsumme einer geometrischen Reihe ist definiert als (kⁿ⁺¹-1) : (k-1). Demnach ist zu zeigen:

(kⁿ⁺¹-1) : (k-1) <= (k+1)ⁿ⁺¹+1

Sei n=1. Linke Seite: (k²-1) : (k-1) = k+1
              Rechte Seite: (k+1)²= k²+2k+1 +1 = k²+2k+2

OK für n=1.

Angenommen die Behauptung gelte für ein n, dann ist noch zu beweisen, dass sie auch für n+1 gilt.

Also: (kⁿ⁺²-1) : (k-1) <= (k+1)ⁿ⁺²+1
Und einmal mehr weiß ich nicht weiter.

Comments

diese Antwort wurde zurückgezogen!

---

Herzlichen Dank für die schnelle Antwort. Ich habe mir den Beweis angesehen und konnte ihm folgen, ausgehend von der Annahme, dass dies zu zeigen ist (so steht's auch in der Antwort):

"Zu Zeigen:  kⁿ ≤ (k+1)ⁿ⁺¹"
Nicht klar ist mir, warum es genügt zu zeigen, dass der n-te Summand (also kⁿ) kleiner oder gleich (k+1)ⁿ⁺¹ ist, denn dies könnte ja zwar zutreffen (bzw. dies trifft ja zu, wie man im folgenden Beweis erkennt), aber wieso ist es ausgeschlossen, dass die vorherigen Summanden, also k⁽¹⁾, k², k³, ...,k^n-1 aufaddiert und zu kⁿ hinzuaddiert nicht doch größer als (k+1)ⁿ⁺¹ sind?

Da stehe ich noch im Wald.

---

Achso, das habe ich falsch interpretiert. Dann wird es etwas komplexer.

---

OK, hast Du einen Hinweis, bitte?

---

k+k^2+...+k^{n+1}<=  (k+1)^{n+1} + k^{n+1}

Zu zeigen wäre nun

(k+1)^{n+1} + k^{n+1}  <=(k+1)^{n+2}

---

Ja, genau (Einarbeiten der Induktionsannahme), zu zeigen wäre: "(k+1)ⁿ⁺¹ + kⁿ⁺¹  <= (k+1)ⁿ⁺²" 

Nun müsste ich also abschätzen, ob (k+1)ⁿ⁺¹ + kⁿ⁺¹ <= (k+1)ⁿ⁺¹ * (k+1) ist. Intuitiv: ja, dem ist so, aber formal?

---

Oh Entschuldigung, eben sehe ich noch den weiteren Kommentar; den hatte ich bisher nicht beachtet und muss ihn erst einmal lesen.

Answer 1

(k+1)^{n+1}=1+(n+1)*k + (n+1 über 2) k^2 +...+ k^{n+1}>= 1+(k+k^2+....+k^n)+k^{n+1}

Nun ist jeder Summand größer wie der korrespondierende Summand auf der linken Seite der Ungleichung, da (n+1 über i) steht s größer gleich 1 ist. Hinzu kommt noch 1+k^{n+1} ( zumindest wenn k positiv ist, aber dazu hast du keine Angaben gemacht.)

Comments

Dankeschön. Basiert auf der Berechnung des Binimialkoeffizienten bzw. des binomischen Satzes. Das muss ich mir intensiv ansehen und verdauen.
VG

---

Ja, nun habe ich es verstanden. Der Beweis bedarf noch nicht einmal der vollständigen Induktion.
In der Tat (das hätte ich dazu schreiben müssen), kann davon ausgegangen werden, dass k > 0 ist (bezogen auf Ansatz#2 (geometrische Reihe), müsste sogar gefordert werden, dass k > 1 gilt).
Also nochmals: Vielen Dank für Deine Hilfe!