Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Induktionsschnitt

Induktionsschnitt

Universität / Fachhochschule

Sonstiges

Tags: Induktionsschnitt, Zahlentheorie

Gauss94 aktiv_icon

02:30 Uhr, 11.09.2022

Seid gegrüßt,

ich beschäftige mich mit Gauß und der Zahlentheorie. Beim einstudieren des „Anfängerstoffs“ ist ständig von einem Induktionsschritt die Rede. Soweit ich verstanden habe handelt es sich um eine Beweisführung,

d . h

. ob eine Aussage wahr oder falsch ist.

Problem:
Ich habe die einzelnen Schritte nicht ganz verstanden. Ist der Induktionsschritt etwas Allgemeines oder Spezifisches, also sieht er für jede Aussage anders aus?

Falls er allgemein ist, wie sehen die einzelnen Schritte mathematisch aus?

Falls er spezifisch ist, muss es doch dennoch eine allgemeine Form geben, auf die sie zurückgeht?

Auf Wikipedia werde ich nicht schlauer, dort ist er zu kompliziert erklärt. Kann mir jemand den Induktionsschritt - wenn möglich - einfacher erklären?

Ich bedanke mich im Voraus!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

08:05 Uhr, 11.09.2022

Sicher kann man versuchen, das Beweisprinzip der Vollständigen Induktion in einem Beitrag zu erläutern, aber dazu eignen sich eigentlich Lehrbücher besser. Einen ersten Einblick kann sicher auch der Wiki-Artikel

de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion

bieten. Früher mal war das auch Gymnasialstoff - weiß nicht, ob sich das geändert hat.

Revilo aktiv_icon

01:57 Uhr, 12.09.2022

Hallo Gauss94,
du möchtest also per Induktion die Gültigkeit einer mathem. Aussage beweisen, richtig?
Mit dieser Frage habe ich früher auch große Probleme gehabt.

Vielleicht kann ich dir mit folgender bildlichen Anschauung etwas weiterhelfen.
Bitte stelle dir mal eine unendlich lange Reihe von Dominosteinen vor, alle schön hintereinander aufgestellt. Als Aussage soll gelten: Alle Steine fallen um!
Das gilt es also als allgemeingültig zu beweisen.

Damit die ganze Dominostein-Reihe tatsächlich komplett umfällt, müssen zwei Bedingungen erfüllt sein:

1) -

der erste Stein muß umfallen (die math. Aussage/Formel) muß also für

n = 1

gelten.
Das ist der Induktionsanfang. Wenn schon der erste Stein nicht umfällt, können die nachfolgenden es erst recht nicht. Also der erste Stein muß zumindest angestoßen werden und deshalb umfallen.

2) -

jeder umfallende Stein muß die Eigenschaft des Umfallens auf seinen Nachfolger übertragen,
an diesen weitergeben, ihn also ebenfalls anstoßen.
Das ist der Induktionsschritt, also quasi die "Vererbung" (Weitergabe der Eigenschaft)
an den nächsten Stein, sprich die nächste "Generation".

Hat man den Start (die Formel also für

n = 1

bewiesen (Induktionsanfang)), muß man zeigen, daß die Vererbung gilt, also jeder nachfolgende Stein ebenfalls angestoßen wird. (Induktionsschritt)
Erst, wenn dieser Nachweis erbracht wurde, ist gesichert, daß die ganze Reihe Dominosteine umfällt, egal wie lang sie auch sein mag. Erst dann ist die Formel also allgemein bewiesen.

Beispiel: Mathem. Ausage: Die Summe

S

der natürlichen Zahlen von 1 bis

n

ist

(\frac{n}{2}) \cdot (n + 1)

.
Diese Aussage gilt es zu beweisen.

Induktionsanfang: ich setze

n = 1

Die Summe von 1 ist

1!

n = 1

in die Formel eingesetzt ergibt

\frac{1}{2} \cdot (1 + 1) = 1

1 = 1 w . A

. Der Induktionsanfang ist damit bewiesen, die Formel gilt also
garantiert für

n = 1

. Der erste Stein ist also sicher umgefallen.

Jetzt gilt es, die Vererbung zu beweisen:
Induktionsschritt:
Da die Formel für

n = 1

(wie oben bewiesen) funktionierte, könnte sie ja auch
für

n = 2,3,4,5 . .

. funktionieren, aber das ist noch nicht sicher bewiesen.

Wie in der Biologie:
Eine genetische Eigenschaft kann nur von den Eltern auf die Kinder vererbt werden.

Wir gehen also davon aus, daß diese "genetische" Eigenschaft bis zu einer x-beliebigen
Elterngeneration

k

uneingeschränkt bestanden hat. Sonst wäre sie ja nicht mehr vererbbar.

Für die Eltern-Generation

k

muß also laut Formel bisher gegolten haben:

S (k) = \frac{k}{2} \cdot (k + 1)

.

Wenn die Vererbung weiterhin funktionieren soll, muß für die nachfolgende Generation bildlich
für den nächsten Dominostein

(k + 1)

also

[1 + 2 + 3 + . .

+ k] + k + 1 = \frac{k + 1}{2}) \cdot ((k + 1) + 1)

gelten.

Der Term

[1 + 2 + 3 + . .

+ k]

kann also quasi als "elterliche Mitgift" betrachtet werden.
Für diese "Mitgift" gilt bekanntlich

\frac{k}{2} \cdot (k + 1)

.

Diese "Mitfift" nutzen wir jetzt, um sie einzusetzen:

\frac{k}{2} \cdot (k + 1) + k + 1

soll also dasselbe ergeben, wie

\frac{k + 1}{2} \cdot ((k + 1) + 1

laut Formel für

(k + 1))

.
Dies gilt es schlußendlich, zu zeigen!

Wenn uns das gelingt, ist, weil

k

als "Elterngeneration" ja beliebig gewählt wurde, die Vererbung
als Ganzes und damit die Allgemeingültigkeit der Formel wasserdicht bewiesen.

Also rechnen wir mal nach, ob folgendes stimmt:

\frac{k}{2} \cdot (k + 1) + k + 1 = \frac{k + 1}{2} \cdot ((k + 1) + 1)

= \frac{k + 1}{2} \cdot (k + 2)

wichtig: die rechte Seite dieser Gleichung bleibt ab jetzt unverändert, unangetastet !
(eine eventuelle Übereinstimmung muß sich also ausschließlich aus der linken Seite
herleiten lassen).

Gehen wir es also an:

\frac{k}{2} \cdot (k + 1) + k + 1 =

[

nach Ausklammern von

(k + 1)] = (k + 1) \cdot (\frac{k}{2} + 1)

wenn man jetzt sieht, daß man die 1 ganz rechts auch als

\frac{2}{2}

schreiben kann, ergibt sich:

(k + 1) \cdot (\frac{k}{2} + \frac{2}{2})

bzw.

(k + 1) \cdot (\frac{k + 2}{2}

weil gleicher Nenner)) bzw. schließlich

\frac{k + 1}{2} \cdot (k + 2)

.

Ein Vergleich beider Seiten zeigt deren Übereinstimmung.
Die "genetischen" Eigenschaften der Elterngeneration

(k)

gelten also auch für die nachfolgende Generation

(k + 1),

egal, welches

k

ich zuvor wählte.

Damit ist die Vererbung allgemein nachgewiesen und der Induktionsschritt hat sein Ziel erreicht.

O . g

. Formel gilt also generell, selbst wenn ich für

k = 1

Milliarde gewählt hätte.

Fazit:
Der Witz am Induktionsschritt ist nichts weiter, als das nutzen der "elterlichen Mitgift".
Den mathematischen Blick für Vereinfachungen wie

1 = \frac{2}{2}

gewinnt man aber nur durch Übung.
Eine einzige bildliche Vorstellung ist manchmal hilfreicher, als

1000

Seiten Fachliteratur.

Ich hoffe, daß ich dir damit etwas helfen konnte.

Mit nettem Gruß Revilo

Gauss94 aktiv_icon

08:47 Uhr, 12.09.2022

Größten Dank für die ausführliche Antwort!

Ich werde anhand deiner Antwort demnächst etwas ausprobieren und eventuell hier reinstellen.

1560302

1560281

	Status: nicht eingeloggt	Noch nicht registriert?