Vollständige Induktion/Einführung/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 .