Wie lautet der Induktionsbeweis? Summe_(k=1)^{2^n}(1/k) ≥ 1 + n/2

Question

I.

Wenn ich beim Induktionsanfang n = 1 setze dann muss ich ja die Summe aus bis 2 für die Gleichung ermitteln.

Ich setze ein um bekomme bei 1 = 1/1 ≥ 1+1/2 raus und dann nochmal n = 2 addiere komme ich auf:

1,5 ≥ 1,5 ,

ist das soweit korrekt? Bei n = 2 habe ich ja den rechten Teil der Gleichung komplett weggelassen aber sonst würde es nach meiner Rechnung nicht mehr stimmen. 

II.

Hier einfach die Gleichung einsetzen.

III.

Hier  bei  n und k(?) in der Gleichung jeweils +1 hinzufügen. 
Ich hab jetzt einige Annahmen gemacht und weiß nicht ob die stimmen

Und wie komme ich jetzt auf den Beweiß?  

Comments

Bemerkung: Da du das nun bewiesen hast, hast du bewiesen, dass die harmonische Reihe divergiert. 

Answer 1

      

Abkürzung: N := 2ⁿ , M = 2ⁿ⁺¹  [ wegen des Formeleditors bei Summen ]

zu zeigen:  A(n):   Für alle n∈ℕ (n≥1) gilt:  \(\sum\limits_{k=1}^{N} 1/k\) ≥ 1 + n/2

Basis A(1):    \(\sum\limits_{k=1}^{2} 1/k\)  = 1 + 1/2  ≥ 1 + 1/2  ist  wahr.

Induktionsschluss:  A(n)  ⇒ A(n+1)

\(\sum\limits_{k=1}^{M} 1/k\)  

= \(\sum\limits_{k=1}^{N} 1/k\)  + \(\sum\limits_{k=N+1}^{M} 1/k\)    [ ≥ 1/2  Edit: ??]

≥_IV  1 + n/2 + 1/2  = 1 + (n+1) / 2

Edit: Muss so sein, ist aber nicht so offensichtlich, wie ich zuerst dachte. 

@Gast hj2100 hat es aber in seinem letzten Kommentar sehr einleuchtend  begründet und damit die Hauptarbeit geleistet:

"Die rote Summe hat  mindestens den Wert 1/2, weil k ≤ M ist".

Wegen k ≤ M ist nämlich jeder einzelne Summand 1/k ≥ 1/M und da es davon M-N Stück gibt, ist die gesamte Summe größer oder gleich (M-N)/M = 1/2 . 

Ergänzung von mir zur Erinnerung (vgl. 1.Zeile): 

(M-N) / M = (2ⁿ⁺¹ - 2ⁿ) / 2ⁿ⁺¹ = 1 - 1/2 = 1/2

Gruß Wolfgang

Comments

wie beweist man das von dir rot geschriebene? Habe es versucht, aber nicht hinbekommen.

---

-------------------------------------------------

---

statt  einen Summanden  :  Wert
statt  N+1 = 2ⁿ +1 ≥ 2  :  k ≤ M

---

Rote Summe ≥ 1/2 ist nicht so offensichtlich, wie ich zuerst dachte. (hatte in tiefer Nacht den Kehrwert ignoriert).

Dieser Nachweis ist wohl die eigentliche Arbeit bei dem Beweis.

Denke darüber nach (und wäre  für jede Unterstüzung dankbar :-) !)

Habe die Antwort editiert und die falsche Begründung in meinem vorhergehenden Kommentar gelöscht.

@Gast hj2100: Wenn du recht hast, wäre der Beweis fertig.

Aber warum sollte die rote Summe  " den Wert  k ≤ 2ⁿ⁺¹  [k∈ℕ] " haben? 

Für n=2 hat sie den Wert ≈ 0.634

Für n=3 hat sie den Wert ≈ 0.662

Für n=4 hat sie den Wert ≈ 0.677

Für n=10 hat sie den Wert ≈ 0.693

Für n=20 hat sie den Wert ≈ 0.704

---

Aber warum sollte die rote Summe  " den Wert  k ≤ 2ⁿ⁺¹  [k∈ℕ] " haben?

Das habe ich doch nie behauptet.

Der ursprüngliche Kommentar lautete

Nach meinen Ersetzungen wird daraus

"Die rote Summe hat doch mindestens den Wert 1/2, weil k ≤ M ist".

Wegen k ≤ M ist nämlich jeder einzelne Summand 1/k ≥ 1/M und da es davon M-N Stück gibt, ist die gesamte Summe größer oder gleich (M-N)/M = 1/2 .

---

Unmittelbar einleuchtend, man muss nur darauf kommen. Danke für die Unterstützung!

(Hatte es schon verzweifelt mit einem weiteren Induktionsbeweis versucht)

Ich hoffe, du bist damit einverstanden, dass ich dich im EDIT der Antwort zitiert habe, damit das Ganze im Zusammenhang dargestellt ist.

---

Kann jemand den roten Schritt nochmal näher erläutern? Ich bin da noch nicht ganz hinter gestiegen...