Vollständige Induktion Summe über 1/k bis 2^n-1 Ungleichung

Question

Aufgabe:

Hey Leute, ich soll per Induktion beweisen, dass für alle n ∈ ℕ gilt:

\( \sum \limits_{k=1}^{2^{n-1}}{1/k} \leq n \)

Problem/Ansatz:

Induktionsanfang bis Behauptung alles klar soweit, aber im Induktionsschritt versteh ich nicht ganz wie ich den beweisen soll.

Ich habe jetzt so umgestellt, dass da steht:

\( \sum \limits_{k=1}^{2^{n-1}}{1/k}\) + \( \sum \limits_{k=2^n-1 +1}^{2^{n}}{1/k}\)  ≤ n + \( \sum \limits_{k=2^n-1 +1}^{2^{n}}{1/k}\)

(Die 2^n-1+1 soll eigentlich 2 (hoch (n-1)) +1 sein)

Ich hab mir gedacht von da aus per Äquivalenzumformung den rechten Teil der Gleichung mit <= n+1 eine Seite auf 0 zu bringen. Weiß aber nicht genau wie. Wäre das überhaupt der richtige Weg gewesen? Bzw. kann mir jemand sagen was ich stattdessen machen könnte?

MfG

Answer 1

\(\sum \limits_{k=1}^{2^{n-1}}  \frac{1}{k}+ \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)  ≤ n + \( \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)

Das ist doch schon ganz OK.

Überlege dir, wieviel Summanden die Summe \( \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\) hat und welcher davon der grösste ist.

Anzahl mal Wert des grössten Summanden ist sicherlich

eine obere Schranke für diese Summe. Die ist also ≤1.

Comments

Also der erste Summand müsste ja der Größte sein, da 1/k. Aber woher weiß ich wie viele Summanden diese Summe hat wenn mit Variablen(n) gehandelt wird? Und warum ist Anzahl mal Wert der 2. Summe ≤1?

---

\( \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)

hat 2^(n-1) Summanden;  denn 2^(n-1) ist ja

genau die Hälfte von 2^n , also sind es von 2^(n1) + 1

bis 2^n genau 2^(n-1) Stück.

Die werden immer kleiner, der größte ist also 1/ (2^(n-1)+1)

Also ist die ganze Summe kleiner oder gleich

Anzahl * größer Werte eines Summanden

=  2^(n-1)  *   1/ (2^(n-1)+1)

Und wenn man den Nenner kleiner macht ,

wird ja der Bruch größer, also gilt

 <  2^(n-1)  *  1/ 2^(n-1)  = 1.

---

Also ich verstehe, dass 2^(n-1) die Hälfte von 2^n sind und ,dass die immer kleiner werden. Ich verstehe auch, dass die Summe kleiner ist als wenn man Anzahl * größter Werte eines Summanden der Summe nimmt (Da man ja den größten Wert multipliziert und in dieser Summe die Werte immer kleiner werden). Das der Bruch größer wird wenn der Nenner kleiner wird versteh ich auch. (1/2 ist größer als 1/4) 

Aber den letzten Teil versteh ich noch nicht ganz, warum = 1 ? Und wie genau wende ich das im Induktionsschritt an?

---

2^(n-1)  *  1/ 2^(n-1)  = 1.

Hier wird doch ein Term mit seinem

Kehrwert multipliziert. Das gibt immer 1.

Wenn du bist bei

\(\sum \limits_{k=1}^{2^{n-1}}  \frac{1}{k}+ \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)  ≤ n + \( \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)

brauchst du doch nur zu sagen: Die letzte Summe

besteht aus 2^(n-1) Summanden, die alle

kleiner als 1/2^(n-1) sind, also ist der Wert der

Summe kleiner 1 und damit folgt:

\(\sum \limits_{k=1}^{2^{n-1}}  \frac{1}{k}+ \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k}\)  ≤ n + \( \sum \limits_{k=2^{n-1} +1}^{2^{n}}\frac{1}{k} \)

< n+1.     q.e.d.

---

Achsoo, ich hab die Rechnung unten falsch gelesen haha. Danke auf jeden Fall jetzt hab ichs verstanden!