Induktionsanfang

Wissenschaft Mathematik
1

Wozu dient er? Kann man den Induktionsanfang einfach weglassen?
In dem man z.B. einfach sagt, ok, … der Induktionsanfang schaut einfach mal, ob es für das kleinstmögliche N gilt.

Meine Antwort lautet: nein.

Warum?

Wenn man sich mal wieder das Schaukel-Lemam anschaut:
http://www.matheplanet.com/default3.html?call=articl…

dann dürfte man nicht einfach (n+k*)* zu (n*+k)* ohne Induktionsanfang umformen.

Warum?

Weil man ja gar nicht wissen würde ob n+k*=n*+k ist, für k=0. Somit wäre es sinnlos zu schauen ob es denn dann auch für k+1=1 gilt.

Der Induktionsanfang k=0 stellt also die Hauptgrundlage für den Beweis k+1 und somit auch die Hauptgrundlage für den Beweis, dass es für alle k gilt.

Das ist doch richtig gedacht so oder? :wink:

Bevor nicht bewiesen wurde das k=0 wahr ist, ist es unsinnig zu fragen, ob k+1 wahr ist.

2

Hallo,

Wozu dient er? Kann man den Induktionsanfang einfach
weglassen?

nein, man kann ihn nicht weglassen (kann man schon, aber dann kann man auch per vollständiger Induktion keine Aussagen mehr für unendlich viele Objekte zeigen).

In dem man z.B. einfach sagt, ok, … der Induktionsanfang
schaut einfach mal, ob es für das kleinstmögliche N gilt.

Den Satz habe ich nicht verstanden.

Wenn man sich mal wieder das Schaukel-Lemam anschaut:
dann dürfte man nicht einfach (n+k*)* zu (n*+k)* ohne
Induktionsanfang umformen.

Doch, darf man natürlich. Dieser Schritt benutzt nur die Induktions_voraussetzung_, also die Annahme, dass die für alle k zu beweisende Aussage für ein herausgegriffenes k gilt. Den Induktionsschritt („Angenommen, Aussage gilt für ein k. Dann gilt sie auch für k+1.“) beweist man unabhängig vom Induktionsanfang, nur ohne ihn hat er nicht viel Wert.

Der Induktionsanfang k=0 stellt also die Hauptgrundlage für
den Beweis k+1 und somit auch die Hauptgrundlage für den
Beweis, dass es für alle k gilt.

Ich glaube, du meinst im Endeffekt das richtige. Dass er eine der Hauptgrundlagen für den Beweis für alle k ist, würde ich unterschreiben; dass er Hauptgrundlage für den Beweis „k+1“ ist, nicht, zumindest nicht direkt. Wenn man den Induktionsanfang und den Induktionsschritt beisammen hat, ergibt sich der „Beweis“ für k+1 automatisch durch eine lange Kette von Anwendungen des Induktionsschrittes, ausgehend von oder verankert am Induktionsanfang.

Bevor nicht bewiesen wurde das k=0 wahr ist, ist es unsinnig
zu fragen, ob k+1 wahr ist.

Jein, die Reihenfolge spielt keine Rolle. Man kann auch erst fragen, ob k+1 wahr ist (unter der Annahme, dass k wahr ist), und sich dann um den Anfang kümmern (der ja auch nicht immer 0 sein muss).

Viele Grüße,

Andreas

3

Ah. Da lag also der Haken!

Die Induktionsvorraussetzung behauptet also nur das n+k*=n*+k gilt.
Unter der Annahme dass diese gilt, kommt man von n+(k*)*=n*+k*

Nur damit ist ja noch nichts bewiesen. Damit ist nur bewiesen, dass, wenn die Induktionsvorraussetzung wahr ist, n+(k*)*=n*+k* gilt.

Und jetzt kommt der Induktionsanfang ins Spiel, welcher zeigt, dass es für das kleinst mögliche k wahr ist (beim schaukel-lemma eben die 0), weil von dem kleinstmöglichen ja auf alle anderen ks zwingend geschlossen wird.

Denn wenn man die 0 nun in n+(k*)* einsetzt bekommt man:

n+(0*)*=n*+0* (der übersichthalber die zwischenumformungen nicht mit geschrieben)

Jetzt hat man gezeigt, dass die Aussage nicht nur für 0* wahr ist, sondern sie ist auch für 1* wahr.

Wie zeigt man aber nun, dass sie auch für 2* wahr ist?

Vor mir spielt sich dieses Bild ab:

n+(((0*)*)*) = (n+(0*)*))*

oben wurde bewiesen, dass: n+(0*)*=n*+0* ist, also:

(n+(0*)*))* = (n*+0*)*
(n*+0*)* = n*+(0*)*

Also: n+(((0*)*)*) = n*+(0*)*

Das kann man nun ad infinitum so weiter machen.

Ist genau das mit der Induktion gemeint? Das sich dieses Szenario im Hirn abspielt?

4

Hallo,

Die Induktionsvorraussetzung behauptet also nur das n+k*=n*+k
gilt.

genau, für irgendein bestimmtes k.

Nur damit ist ja noch nichts bewiesen. Damit ist nur bewiesen,
dass, wenn die Induktionsvorraussetzung wahr ist,
n+(k*)*=n*+k* gilt.

Ja! Dieses „wenn“ ist den meisten, die die vollständige Induktion lernen, am schwierigsten klarzumachen.

Das kann man nun ad infinitum so weiter machen.

Genau, man hat einmal allgemein den Übergang von k zum Nachfolger von k gezeigt. Sobald man bei einer bestimmten Zahl x startet, „rennt“ diese Schlußfolgerungskette los und erfasst den Nachfolger von x und dessen Nachfolger und dessen Nachfolger und dessen Nachfolger …

Ist genau das mit der Induktion gemeint? Das sich dieses
Szenario im Hirn abspielt?

Bei mir spielt sich das auch so ab; ich denke, zum Begriff „Induktion“ braucht es dann noch die Erkenntnis, dass durch diesen Prozess (fast) alle natürlichen Zahlen erfasst werden.

Andreas

1 „Gefällt mir“
5

hi,

Wozu dient er? Kann man den Induktionsanfang einfach
weglassen?

beweis, dass alle zahlen größer als 100 ist.

a) kein induktionsanfang
b) wir gehen davon aus, dass n > 100
dann ist natürlich n+1 > n > 100

also sind alle zahlen größer als 100.

m.

6

Beweis, dass das nicht stimmt:

0 ist die erste natürliche Zahl (Axiom).

0

7

Genau:

Man wiederholt den Induktionsschritt zwar nicht unendlich mal, aber das braucht man ja auch nicht.

Wenn man die dahinterstehende Logik oder Gesetzmäßigkeit des Induktionsschrittes begriffen hat, sieht man, dass dieser Schritt alle N beweisen würde, würde man ihn unendlich oft wiederholen.

Aber das kann man sich sparen.

Das ergibt sich eben aus der Logik des Induktionsschrittes.

8

Hallo,

Die Induktionsvorraussetzung behauptet also nur das n+k*=n*+k
gilt.
Unter der Annahme dass diese gilt, kommt man von n+(k*)*=n*+k*

Nur damit ist ja noch nichts bewiesen. Damit ist nur bewiesen,
dass, wenn die Induktionsvorraussetzung wahr ist,
n+(k*)*=n*+k* gilt.

so ist es. Du kannst übrigens auch problemlos n + (k*)* = n* + k* + 789 zeigen („789“ kann auch jede beliebige andere Zahl sein), wenn Du als Induktionsvoraussetzung annimmst, dass n + k* = n* + k + 789 wahr ist. Der Induktions_schluss_ funktioniert auch dann einwandfrei. Allerdings kannst Du n + k* = n* + k + 789 für kein einziges k direkt zeigen, d. h. Du kannst den Induktions_anfang_ nicht zustande bringen, und deshalb ist der Beweis von n + k* = n* + k + 789 durch vollständige Induktion unmöglich. Induktionsanfang und -schluss gelingt nur für n + k* = n* + k.

Ist genau das mit der Induktion gemeint?

Si, señor.

Gruß
Martin

1 „Gefällt mir“
9

n+(((0*)*)*) = n*+((0)*)*

Kann man ja simpler machen, aber irgendwie habe ich das gar nicht gesehen:

n+(1*)* = (n+1*)*
(n+1*)* = (n*+1)*
(n*+1)* = n*+1*

Jetzt kann man ja dann so weitermachen:

n+(2*)* = n*+2*
n+(3*)* = n*+3*
[…]

Eine verkompliziertheit von mir selber weggemacht juhu.

Schön.

10

Noch ein kleines Bild dazu
Hallo Eliminato,

wie ich sehe, hast du das Prinzip der vollständigen Induktion inzwischen verstanden. Dennoch hier noch ein meiner Meinung nach schöner bildhafter Vergleich, der meiner Erfahrung nach vielen Anfängern hilft, das Prinzip der v. I. gut im Kopf zu behalten.

Stell dir eine Reihe von Dominosteinen vor, von denen jeder eine natürliche Zahl repräsentiert. Sie sind der Reihe nach aufgestellt, mit gleichem Abstand. Wenn ein Dominostein fällt, heißt das, die Behauptung gilt für die entsprechende Zahl
Der Induktionsschluss überprüft nun, ob die Dominosteine nahe genug zusammen stehen. Also, ob unter der Voraussetzung (Induktionsannahme), dass der k-te Stein fällt, dann auch der k+1-te Stein fällt.
Der Induktionsanfang überprüft, ob der erste der Dominosteine fällt. Wie du einfach siehst, nützt dir der Induktionsschritt, der zeigt, dass die Dominosteine noch so nah beieinander stehen nichts, wenn du nicht weißt, ob der erste Stein überhaupt fällt.

Anmerkung: du kannst die v. I. auch benutzen, um eine Aussage nicht für alle natürlichen Zahlen, sondern auch für alle ganzen Zahlen ab einer bestimmten Zahl, also z.B. alle ganzen Zahlen größer gleich 345 oder auch größer gleich -546 zeigen. Du muss dann nur den Induktionsanfang bei der entsprechenden Zahl ansetzen. Genauso funktioniert die v. I. natürlich auch rückwärts, für alle ganzen Zahlen kleiner gleich einer bestimmten Zahl. Man muss dann nur von k auf k-1 schließen.

Liebe Grüße
Nadine

11

Ohne Induktionsanfang kann, wie ich mir das ja selber auch
schon gedacht habe, man jeden Unsinn beweisen.

eben.
drum.
m.