Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion mit Grenze (2^n)-1

Vollständige Induktion mit Grenze (2^n)-1

Universität / Fachhochschule

Tags: Vollständig Induktion

CatDoge aktiv_icon

10:20 Uhr, 17.03.2016

(Lösung vorhanden (s.Bild))

Hi,

ich habe Probleme mit der vollständigen Induktion, wo die Grenze ungleich

n

ist. Also bspw.

2 \cdot n + 1,

oder wie im angehängten Bsp.

2^{n} - 1

Den ersten Schritt kann ich mehr oder weniger nachvollziehen. Man möchte die die Induktionsvoraussetzung durch

\frac{n}{2}

ersetzen. Warum fange ich aber bei der zweiten Summe bei

k = 2^{n}

an ?

Auch den Schritt von der letzten Summe (s.Bild) zu dem Bruch verstehe ich nicht.

Das Problem ist auch, dass es wenige Beispiele/Aufgaben gibt, wo die Grenze ungleich

n

ist. Auch in den meisten Youtube Videos ist die Grenze immer

n

.

Wenn ihr mir helfen könntet, wäre ich sehr dankbar.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

DerDepp aktiv_icon

10:49 Uhr, 17.03.2016

Hossa :-)

Um die Induktionsvoraussetzung nutzen zu können, zerlegst du die Summe mit

2^{n + 1} - 1

Summanden in zwei Teilsummen. Die erste Teilsumme geht von

k = 1

bis

k = 2^{n} - 1

. Die zweite Teilsumme schließt sich daran an und geht von

k = 2^{n}

bus

k = 2^{n + 1} - 1

\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}

Deswegen startet die zweite Summe bei

k = 2^{n}

. Nach Induktionsvoraussetzung ist die erste Teilsumme nun

\geq n / 2

, also:

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

.

Für die verbliebene Teilsumme lauten die Summanden:

\frac{1}{2^{n}} + \frac{1}{2^{n} + 1} + \frac{1}{2^{n} + 2} + \dots + \frac{1}{2^{n + 1} - 1}

. Jeder dieser Summanden ist größer als

\frac{1}{2^{n + 1}}

, denn es gilt:

2^{n} < 2^{n + 1}, 2^{n} + 1 < 2^{n + 1}, \dots, 2^{n + 1} - 1 < 2^{n + 1}

. Daher gilt:

\sum_{k = 2^{n}}^{2^{n + 1} - 1} \frac{1}{k} > \sum_{k = 2^{n}}^{2^{n + 1} - 1} \frac{1}{2^{n + 1}} = \underset{(2^{n + 1} - 1) - (2^{n}) + 1 Summanden}{\underset{⎵}{\frac{1}{2^{n + 1}} + \frac{1}{2^{n + 1}} + \dots + \frac{1}{2^{n + 1}}}} = 2^{n} \cdot \frac{1}{2^{n + 1}}

Die Summe ausgeschrieben ergibt

(2^{n + 1} - 1) - (2^{n}) + 1

Summanden. [Obere Grenze minus untere Grenze plus 1.] Das sind dann

2^{n + 1} - 2^{n} = 2 \cdot 2^{n} - 2^{n} = 2^{n}

Summanden insgesamt. Schließlich kann folgt daraus:

\sum_{k = 1}^{2^{n + 1} - 1} \frac{1}{k} > \frac{n}{2} + 2^{n} \cdot \frac{1}{2^{n + 1}} = \frac{n + 1}{2}

.

Im Induktionsschritt gilt sogar echtes Größer, nicht nur Größer-Gleich ;-)

CatDoge aktiv_icon

14:16 Uhr, 17.03.2016

Hab das leider an sich nicht wirklich verstanden, aber ich werde jm. fragen, ob er mir das so erklären kann, wie du es beschrieben hast.

Vielen Dank!

1296566

1296522

	Status: nicht eingeloggt	Noch nicht registriert?