Vollständige Induktion für alle n∈ℕ0 gilt Σi=2n (1/i ≥ 1 + n/2)

Question

Aufgabe:

Zu zeigen ist, dass für alle $$n\in \mathbb{N}_{0}$$ gilt: $$\sum \limits_{i=1}^{2^{n}}\frac{1}{i}\geq 1 + \frac{n}{2}$$

Problem/Ansatz:

Das ganze hört sich stark nach vollständiger Induktion an, deswegen hier mein Ansatz:

$$[IA] n=0: \sum \limits_{i=1}^{2^{0}}\frac{1}{i}=1\geq 1 + \frac{0}{2}=1$$

Als Induktionsvoraussetzung nehme man an, dass die Behauptung iben für ein n aus den natürlichen Zahlen (inkl. 0) erfüllt ist.

$$[IS] n\rightarrow n+1$$

$$\sum \limits_{i=1}^{2^{n+1}}\frac{1}{i} = \sum \limits_{i=1}^{2^{n}}\frac{1}{i} + \sum \limits_{i=2^{n}+1}^{2^{n+1}}\frac{1}{i}\text{ (mit Induktionsvoraussetzung)}\geq1 + \frac{n}{2}+\sum \limits_{i=2^{n}+1}^{2^{n+1}}\frac{1}{i} (*)$$

Wie kann ich die Gleichung (*) nun so zielführend umformen, dass am Ende steht:

$$\geq1+\frac{n}{2} + \frac{1}{2} = \frac{n+1}{2}$$

Über hilfreiche Gedankenanstöße würde ich mich sehr freuen!

Answer 1

Du brauchst also noch

$$\sum \limits_{i=2^{n}+1}^{2^{n+1}}\frac{1}{i} ≥ \frac{1}{2}$$

In der Summe stehen 2ⁿ Summanden und die sind alle größer

oder gleich 1 /  2^(n+1) , also ist deren Summe größer oder gleich

2ⁿ * ( 1 / 2^(n+1) ) = 1/2 .

In deiner letzten Gleichung fehlt noch " 1 + " .

Comments

Vielen Dank, leicht verständlich erklärt. Die Methodik, eine Summe durch eine derartige Betrachtung abzuschätzen - das war mir noch nicht bekannt, werde ich mir merken :D

---

Könntest du vielleicht ebenfalls erläutern, wie du darauf gekommen bist, dass die Summe 2ⁿ  Summanden enthält? Wenn ich das mit Beispielzahlen ausprobiere funktioniert es, aber wie würde ein formaler Beweis aussehen?

Mit einem Link statt einer Erklärung wäre ich ebenfalls zufrieden.

---

Mein Anliegen hat sich erledigt, ich habe es verstanden.