Vollständige Induktion/Einführung/Aufgaben/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man mit ihnen zählen kann, d.h. dass man in ihnen ausgehend von durch den Übergang von zum Nachfolger jede natürliche Zahl erreicht. Dies begründet die folgende Eigenschaft: Wenn eine Teilmenge ist, die einerseits die enthält und die andererseits mit jedem auch den Nachfolger enthält (also ), so ist bereits . Mit dem Startglied folgt ja dann zunächst , sodann , sodann u.s.w, und da dieser Zählprozess jede natürliche Zahl erreicht, gehört jede natürliche Zahl zu . Diese Beobachtung ist die Grundlage der vollständigen Induktion.

Mathematische Aussagen, die von natürlichen Zahlen abhängen, können mit dem Beweisprinzip der vollständigen Induktion bewiesen werden. Die folgende Aussage begründet dieses Prinzip.



Satz  

Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte

  1. ist wahr.
  2. Für alle gilt: wenn gilt, so ist auch wahr.

Dann gilt für alle .

Beweis  

Es sei

Wir wollen zeigen, dass ist, denn genau dies bedeutet, dass die Aussage für alle gilt. Nach der ersten Bedingung ist

Nach der zweiten Voraussetzung gilt für , dass aus stets folgt. Damit erfüllt beide Voraussetzungen im Induktionsprinzip für Mengen, so dass gilt.


Der Nachweis von (der Gültigkeit von) heißt dabei der Induktionsanfang und der Schluss von auf heißt der Induktionsschluss. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage erst für für ein gewisses (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage und den Induktionsschluss führt man für durch.

Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, reelle, komplexe) Zahlen bedeutet

Dabei hängen im Allgemeinen die in einer formelhaften Weise von ab. Entsprechend ist das Produktzeichen definiert, nämlich durch

Insbesondere sind für die Potenzen durch

definiert. Dabei gelten die Konventionen und (die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll). Als Rechenregeln für das Potenzieren gelten


Aufgabe

Beweise durch Induktion die folgende Formel für .


Lösung

Beim Induktionsanfang ist , daher besteht die Summe links nur aus einem Summanden, nämlich der , und daher ist die Summe . Die rechte Seite ist , so dass die Formel für stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein gilt, und müssen zeigen, dass sie auch für gilt. Dabei ist beliebig. Es ist

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für , also ist die Formel bewiesen.


Aufgabe

Zeige durch vollständige Induktion, dass für jedes die Zahl

ein Vielfaches von ist.


Lösung

Induktionsanfang. Für ist

ein Vielfaches von . Induktionsschritt. Sei nun die Aussage für bewiesen und betrachten wir den Ausdruck für . Dieser ist

wobei im letzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass ein Vielfaches von ist). Daher ist diese Zahl ein Vielfaches von .

Aufgabe

Die Städte seien untereinander durch Straßen verbunden und zwischen zwei Städten gibt es immer genau eine Straße. Wegen Bauarbeiten sind zur Zeit alle Straßen nur in eine Richtung befahrbar. Zeige, dass es trotzdem mindestens eine Stadt gibt, von der aus alle anderen Städte erreichbar sind.


Aufgabe *

Die offizielle Berechtigung für eine Klausurteilnahme werde durch mindestens Punkte im Übungsbetrieb erworben. Professor Knopfloch sagt, dass es aber auf einen Punkt mehr oder weniger nicht ankomme. Zeige durch eine geeignete Induktion, dass man mit jeder Punkteanzahl zur Klausur zugelassen wird.


Aufgabe

Eine -Schokolade ist ein rechteckiges Raster, das durch Längsrillen und Querrillen in () mundgerechte kleinere Rechtecke eingeteilt ist. Ein Teilungsschritt an einer Schokolade ist das vollständige Durchtrennen einer Schokolade längs einer Längs- oder Querrille. Eine vollständige Aufteilung einer Schokolade ist eine Folge von Teilungsschritten (an der Ausgangsschokolade oder an einer zuvor erhaltenen Zwischenschokolade), deren Endprodukt aus den einzelnen Mundgerechtecken besteht. Zeige durch Induktion, dass jede vollständige Aufteilung einer -Schokolade aus genau Teilungsschritten besteht.


Aufgabe

Es sei eine Menge und es seien , , endliche Teilmengen. Für eine Teilmenge sei

Beweise die Anzahlformel


Aufgabe *

Zeige mittels vollständiger Induktion für die Formel


Aufgabe *

Beweise durch Induktion, dass die Summe von aufeinanderfolgenden ungeraden Zahlen (beginnend bei ) stets eine Quadratzahl ist.


Aufgabe

In der folgenden Argumentation wird durch Induktion bewiesen, dass alle Pferde die gleiche Farbe haben. „Es sei die Aussage, dass je Pferde stets untereinander die gleiche Farbe haben. Induktionsanfang: Wenn nur ein Pferd da ist, so hat dieses eine bestimmte Farbe und die Aussage ist richtig. Für den Induktionsschritt sei vorausgesetzt, dass je Pferde stets untereinander die gleiche Farbe haben. Es seien jetzt Pferde gegeben. Wenn man eines herausnimmt, so weiß man nach der Induktionsvoraussetzung, dass die verbleibenden Pferde untereinander die gleiche Farbe haben. Nimmt man ein anderes Pferd heraus, so haben die jetzt verbleibenden Pferde wiederum untereinander die gleiche Farbe. Also haben all diese Pferde überhaupt die gleiche Farbe“. Analysiere diese Argumentation.