Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Verständnisprobleme bei Induktionsvoraussetzung

Verständnisprobleme bei Induktionsvoraussetzung

Universität / Fachhochschule

Sonstiges

Tags: Induktion, Induktionsvoraussetzung, Sonstig, Vollständig Induktion

LaPregunta aktiv_icon

10:45 Uhr, 19.10.2018

Guten Tag,
wir haben neulich in einer Vorlesung den Beweis durch Induktion (wird meine ich auch "vollständige Induktion" genannt) behandelt. Der Dozent hat die einzelnen Schritte meiner Meinung nach nicht gut genug erläutert.

Mein Problem ist, dass ich nicht verstehe weshalb die Induktionsvoraussetzung gelten muss, um die die Aussage eines zu beweisenden Satzes in den nachfolgenden Schritten zu beweisen.
Ist die Induktionsvoraussetzung nicht genau der Satz, welcher geprüft wird? Wieso wird hier auf einmal die Korrektheit dieses Satzes angenommen, um seine Korrektheit zu beweisen?

Außerdem frage ich mich, wieso der Induktionsanfang (prüfen mit

z . b

n = 1)

notwendig ist.

Wäre nett, wenn mir jemand die Sinnhaftigkeit der Induktionsvoraussetzung und ggf. auch des Induktionsanfangs, so verständlich und basic wie möglich, erklären könnte.

Ich hoffe, dass diese allgemeine Fragestellung so verständlich und in Ordnung ist.

Dankesehr und liebe Grüße!

Bummerang

14:55 Uhr, 19.10.2018

Hallo,

Offensichtlich waren die Erklärungen wohl doch nicht so gut, sonst würdest Du hier nicht fragen!

"Ist die Induktionsvoraussetzung nicht genau der Satz, welcher geprüft wird?"

Nein!

Der zu prüfende Satz ist meist der Art: Beweise, dass für alle

n \in ℕ, n > n_{0}

gilt, dass

. .

. !

Dabei ist

n_{0}

eine feste natürliche Zahl. Die Induktionsvoraussetzung aber lautet dann: Es existiert ein

n \in ℕ, n > n_{0},

für das gilt: dass

. .

.

Siehst Du den Unterschied? In der Behauptung steht, dass etwas für alle

n (n > n_{0})

gilt, in der Induktionsvoraussetzung steht aber nur, dass es ein solches

n > n_{0}

gibt! Und dass es so ein

n > n_{0}

gibt, zeigst Du im Induktionsanfang für

n = n_{0} + 1

. Jetzt sollte Dir auch klar geworden sein, wofür der Induktionsanfang gut ist: Er zeigt, dass die Induktionsvoraussetzung erfüllt ist!

Beispiel: Beweise, dass alle geraden natürlichen Zahlen

n, n > 0,

durch 2 teilbar sind.

Induktionsanfang: Die kleinste natürliche Zahl, die gerade ist, ist die 2. Die 2 ist durch 2 teilbar, da jede Zahl durch sich selbst teilbar ist. Teilbar sein heisst per Definition in der Grundschule: Es existiert ein

k_{n} \in ℕ

mit

2 \cdot k_{n} = n

.

Induktionsvoraussetzung: Es gibt eine natürliche Zahl

n, n > 0,

die durch 2 teilbar ist. Das ist wie bei der Induktionsvoraussetzung äquivalent dazu, dass ein

k_{n + 1} \in ℕ

existiert, so dass

2 \cdot k_{n + 1} = n + 2

.

Induktionsbehauptung: Dann ist auch die nächstgrößere gerade natürliche Zahl

n + 2

durch 2 teilbar!

Beweis der Induktionsbehauptung:

n + 2;

Anwendung der Induktionsvoraussetzung

= 2 \cdot k_{n} + 2;

Anwendung des Distributivgesetzes

= 2 \cdot (k_{n} + 1)

Mit

k_{n + 1} = k_{n} + 1 \in ℕ

ist die Teilbarkeit bewiesen!

DerDepp aktiv_icon

15:32 Uhr, 19.10.2018

Hossa :-)

Das macht man sich am besten an einem Beispiel klar. Stell dir vor, du möchtest beweisen, dass die Summe der natürlichen Zahlen von

1

bis

n

stets

n \cdot (n + 1) / 2

ist. Dann lautet also die Behauptung:

A (n) = \sum_{k = 1}^{n} k = \frac{n (n + 1)}{2};

für

n \in ℕ

Den Beweis durch Induktion beginnst du mit der Verankerung. Dabei zeigst du, dass die Behauptung für ein bestimmtes

n_{0}

gilt. Hier bietet sich das kleinst mögliche

n_{0}

an, also

n_{0} = 1

. Wir prüfen das duch Nachrechnen:

Verankerung bei

n_{0} = 1

:

linke Seite:

A (1) = \sum_{k = 1}^{n_{0}} k = \sum_{k = 1}^{1} k = 1

rechte Seite:

A (1) = \frac{n_{0} \cdot (n_{0} + 1)}{2} = \frac{1 \cdot (1 + 1)}{2} = \frac{2}{2} = 1

Damit haben wir die Richtigkeit der Behauptung für

n_{0} = 1

bewiesen. Im nächsten Schritt wollen wir sie für n=2 beweisen und dabei ausnutzen, dass wir die Richtigkeit der Formel bereits für alle

n < 2

bewiesen haben. Danach wissen wir dann, dass die Behauptung auch für alle

n \leq 2

gilt. Im darauf folgenden Schritt bauen wir auf dieser Erkenntnis auf und zeigen, dass die Behauptung auch für n=3 gilt... Wir schließen also immer aus der Richtigkeit der Formel für

A (n)

auf die Korrektheit der Formel für

A (n + 1)

. Das macht man nun nicht für jedes

n

einzeln, sondern verallgemeinert den Induktionsschritt wie im Folgenden:

Induktionsschritt:

n_{0} \to n_{0} + 1

Wir wissen, dass

A (n)

richtig ist für alle

n \leq n_{0}

. Es gilt also:

A (n) = \sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}

für alle

n \leq n_{0}

.
Das nächsthöhere

n

ist

n = n_{0} + 1

. Die Summe dafür lautet:

A (n_{0} + 1) = \sum_{k = 1}^{n_{0} + 1} k = 1 + 2 + 3 + \dots + n_{0} + (n_{0} + 1) = \underset{= A (n_{0})}{\underset{⎵}{\sum_{k = 1}^{n_{0}} k}} + (n_{0} + 1)

Da wir die Formel für

A (n_{0})

bereits bewiesen haben, können wir die Summe durch die Formel ersetzen ("Die Induktionsvoraussetzung wird verwendet"):

A (n_{0} + 1) = \underset{= A (n_{0})}{\underset{⎵}{\frac{n_{0} \cdot (n_{0} + 1)}{2}}} + (n_{0} + 1) = \frac{n_{0} \cdot (n_{0} + 1)}{2} + \frac{2 (n_{0} + 1)}{2} = \frac{(n_{0} + 1) \cdot (n_{0} + 2)}{2}

Wenn du nun

n_{0} + 1

durch

n

ersetzt, steht da wieder exakt die Formel für

A (n)

A (\overset{= n}{\overset{⎴}{n_{0} + 1}}) = \frac{(\overset{= n}{\overset{⎴}{n_{0} + 1}}) \cdot (\overset{= n}{\overset{⎴}{n_{0} + 1}} + 1)}{2}

Im Induktionsschritt hast du also allgemein gezeigt, dass die Formel für

A (n_{0} + 1)

gilt, wenn sie für

A (n_{0})

gilt. In der Verankerung hast du gezeigt, dass sie für A(1) gilt. Nach dem ersten Induktionsschritt gilt sie dann für A(2). Nach dem nächsten Induktionsschritt gilt sie dann für A(3). Nach dem nächsten Induktionsschritt gilt sie dann für A(4)...

LaPregunta aktiv_icon

15:51 Uhr, 20.10.2018

Danke für Eure antworten! Habe bis jetzt nur mal schnell drübergeguckt, aber meine dass es mein Problem gelöst hat.

Werde mir die Beiträge morgen, wenn ich Zeit habe, genauer durchlesen und noch Rückmeldung geben.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1442780

1442565

	Status: nicht eingeloggt	Noch nicht registriert?