Anwendung der vollständigen Induktion auf Wettbewerbsaufgaben

Gliederung

1. Einleitung

2. Definition der vollstandigen Induktion als Beweisverfahren in der Mathematik

3. Aufgaben und Losungen zur vollstandigen Induktion
3.1 Leichte Aufgabe zum Einstieg
3.2 Bundeswettbewerb Mathematik 2002, Runde 2, Aufgabe 1
3.3 Bundeswettbewerb Mathematik 1981, Runde 1, Aufgabe 3
3.4 Bundeswettbewerb Mathematik 2000, Runde 2, Aufgabe 1
3.5 Bundeswettbewerb Mathematik 2006, Runde 2, Aufgabe 1

4. Schlusswort

1. Einleitung

Meine Facharbeit beschaftigt sich mit der vollstandigen Induktion als Beweisverfahren in der Mathematik, jedoch liegt der Schwerpunkt nicht in der Definition, sondern in den Anwendungsbeispielen. Hierfur wahlte ich funf Aufgaben aus, die unter anderem aus dem Bundeswettbewerb Mathematik aus den Jahren 1981, 2000, 2002 und 2006 stammen, und ordnete diese nach ihrem Schwierigkeitsgrad. Oft konnen solche Wettbewerbsaufgaben nicht nur auf eine Weise gelost werden, aber die vollstandige Induktion ist oft ein nutzliches Beweisverfahren, wenn beispielweise eine Aussage uber die naturlichen Zahlen bewiesen werden soll.

Die Entscheidung fur dieses Thema fiel, weil ich in meiner Schulzeit schon einige Male an Mathematikwettbewerben teilgenommen habe. Ich finde es sehr interessant, mich mit diesen Aufgaben zu beschaftigen, da sie meist ganz anders aufgebaut sind und anders zu losen sind als die Aufgaben, die aus der Schule bekannt sind.

2. Definition der vollstandigen Induktion als Beweisverfahren in der Mathematik

In der Mathematik gibt es drei grundlegende Beweisverfahren: den direkten Beweis, den indirekten Beweis und den Beweis durch vollstandige Induktion. Im Folgenden mochte ich naher auf das Verfahren der vollstandigen Induktion eingehen.

Die vollstandige Induktion beruht auf dem 5. Peano-Axiom (nach Guiseppe Peano, 1858-1932) fur die Menge der naturlichen Zahlen N, dem Induktionsaxiom. Dieses lautet folgendermaßen:

Enthalt eine Menge X die Zahl 0 und mit jeder naturlichen Zahl n auch stets deren Nachfolger n', so enthalt X bereits alle naturlichen Zahlen.

Diese relativ theoretische und doch logische Definition findet in der Praxis oft ihre Anwendung, wenn eine Aussage A(n) fur alle naturlichen Zahlen n bewiesen werden soll.

Der Beweis wird immer nach dem gleichen Muster ausgefuhrt:

Schritt 1: Die Aussage wird fur irgendeine naturliche Zahl n0 bewiesen. (Induktionsanfang)

Schritt 2: Es wird angenommen, dass die Aussage fur alle naturlichen Zahlen von n0 bis n gilt (Induktionsvoraussetzung).

Schritt 3: AnschlieGend wird die Aussage A(n+1) durch Umformungen und logische Schlusse aus den Aussagen A(n) bis A(n0) fur die Zahl n+1 bewiesen (Induktionsschritt).

Diese Vorgehensweise mochte ich an einem einfachen Beispiel demonstrieren: Aufgabe: Man beweise folgende Aussage A(n) fur alle [Abbildung in dieser Leseprobe nicht enthalten]:

[Abbildung in dieser Leseprobe nicht enthalten] ist durch 9 teilbar.

Losung:

Induktionsanfang:

A(1): [Abbildung in dieser Leseprobe nicht enthalten]

Da 9 sicherlich durch 9 teilbar ist, ist die Aussage fur n = 1 bewiesen.

Induktionsvoraussetzung:

Man nimmt an, dass die Annahme A(n) fur ein bestimmtes n wahr ist, es gabe also eine naturliche Zahl n, fur die gilt:

[Abbildung in dieser Leseprobe nicht enthalten] ist durch 9 teilbar.

Induktionsschritt:

Jetzt muss nur gezeigt werden, dass die Aussage fur n+1 automatisch richtig ist, wenn sie fur n richtig ist. Wir beweisen also weder die Aussage A(n), noch A(n+1), sondern die Eigenschaft: wenn A(n) zutrifft, dann trifft automatisch auch A(n+1) zu.

Abbildung in dieser Leseprobe nicht enthalten

Nach der festgelegten Induktionsvoraussetzung ist 10n -1 durch 9 teilbar. Da 9-10n auch durch 9 teilbar ist, ist unsere Aussage A(n) somit fur alle n >1 bewiesen. Anschaulich kann die vollstandige Induktion mit Dominosteinen verglichen werden. Es ist zu zeigen, dass, wenn der Stein mit der Zahl n fallt, dann fallt auch der nachfolgende Stein mit der Zahl n+1. Diese Eigenschaft des Dominospiels entspricht dem Induktionsschritt.

Abbildung in dieser Leseprobe nicht enthalten

http://www.pohlig.de/Mathematik/VollstaendigeInduktion/vi.htm (Stand: 2.Juni 2010) http://www.emath.de/Referate/Vollstaendige-Induktion.pdf (Stand: 2.Juni 2010) http://de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion (Stand: 2.Juni 2010) http://www.mathepedia.de/Beispiele_Teilbarkeit.aspx (Stand 2.Juni 2010) http://www.referatschleuder.de/upload/270.pdf (Stand 2.Juni 2010)

3.1 Leichte Aufgabe zum Einstieg

Aufgabe: Zeige, dass es in einem ebenen, konvexen n-Eck [Abbildung in dieser Leseprobe nicht enthalten]— Diagonalen gibt.

Losung:

Induktionsanfang:

Zur Verdeutlichung der Aufgabenstellung ist unten ein ebenes, konvexes Viereck aufgezeichnet, das - wie allgemein bekannt- stets zwei Diagonalen hat.

Abbildung in dieser Leseprobe nicht enthalten

Nun wird uberpruft, ob man bei Berechnung der Diagonalenanzahl (bei n=4) mit der gegebenen Gleichung dasselbe Ergebnis erhalt.

Abbildung in dieser Leseprobe nicht enthalten

Die Formel ist somit fur n = 4 bewiesen.

Man nimmt an, dass ein ebenes, konvexes Vieleck mit n Ecken stets

Diagonalen hat.

Induktionsschritt:

Laut Induktionsvoraussetzung ist die Formel fur ein beliebig vorgegebenes n gultig. Um zu zeigen, dass sie fur jedes n gilt, muss sie fur (n+1) bewiesen werden. Laut der

Abbildung in dieser Leseprobe nicht enthalten

Aussage A(n+1) musste ein Vieleck mit n+1 Ecken Diagonalen haben.

http://www.joerg-rudolf.lehrer.belwue.de/gkmathe/analysis/vi.pdf (Stand: 16. Dezember 2010)

Fugt man in das im Induktionsanfang gezeichnete Viereck zwischen den Ecken A und B noch eine Ecke C ein, so kommen die 3 grunen Diagonalen hinzu. Das heiRt, das Funfeck hat 5 Diagonalen.

Allgemein kommen pro Ecke, die zu einem Vieleck hinzukommt, immer [(n+1)-3]+1 Diagonalen dazu. [(n+1)-3], weil man zwischen der neuen Ecke (C) und allen anderen Ecken Diagonalen zeichnen kann, auRer zu den beiden anliegenden Ecken (A und B) und zum Ausgangspunkt selbst. Zu dieser Gleichung muss man noch eine Diagonale addieren, da es zwischen den Punkten A und B nun auch eine Diagonale gibt.

Zu beweisen:

Abbildung in dieser Leseprobe nicht enthalten

Es ist also bewiesen, dass die Formel fur alle n-Ecke anwendbar ist.

[...]