Vollständige Induktion bei einer Ungleichung. Beh. Summe(1/k) ≤ n.[k von 1 bis 2^n-1]

Question

Ich komme mit der Aufgabe nicht klar, weiß nicht, was ich weiter machen muss.

Ich hoffe, ihr könnt mir helfen :)

---

aus Duplikat:

Sei n ∈ ℕ. Zeigen Sie:

2ⁿ-1

∑1/k ≤ n

k=1

Könnte mir jemand diese Aufgabe lösen und erklären bitte

Answer 1

Bei deinem Induktionsschritt ist noch was faul.

Erst mal heißt es am Anfang Summe bis 2 ⁿ⁺¹ - 1  Das stimmt, aber dann

=   ( und nicht ≤ )  , also

= Summe bis 2^n - 1  +  und jetzt kommt nicht nur ein, sondern

alle Summanden von 2^n bis 2 ⁿ⁺¹ - 1 , also so

= Summe bis 2^n - 1  + Summe von k=2^n bis  2 ⁿ⁺¹ - 1 über 1/k

Und dann kannst du die Induktionsvor. einsetzen und hast

≤  n  +  Summe von k=2^n bis  2 ⁿ⁺¹ - 1 über 1/k        #

Und letztere Summe besteht aus 2^n Summanden

(denn von 2^n bis 2 ⁿ⁺¹ - 1sind es genau 2^n Zahlen)

und jeder Summand ist ≤ 1 / (2 ⁿ )    also die Summe  ≤ 2^n * 1 / ( 2^n ) = 1

und damit geht es bei # weiter mit

≤  n  + 1    q.e.d.

Comments

kannst du vielleicht mal genauer sagen wir man rechnerisch drauf kommt das die 2^n Summanden 1 sind.

Ich verstehe, dass sie das sind aber weiß nicht wie ich das dann in meinem Induktionsbeweis aufschreiben kann.

Answer 2

IA: Für \(n=1\) offensichtlich wahr.

IS:

$$ \sum_{k=1}^{2^{n+1}-1} \frac{1}{k} = \sum_{k=1}^{2^{n}-1} \frac{1}{k} + \sum_{k=2^n}^{2^{n+1}-1} \frac{1}{k} \leq n + \sum_{k=2^n}^{2^{n+1}-1} \frac{1}{2^n} = n+1  $$

Gruß