Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Prinzip

Inhalt

1. Das Prinzip der vollständigen Induktion10. Eine Summe mit Binomialkoeffizienten
2. Der Rekursionssatz11. Eine Ungleichung mit der Fakultät
3. Die Summenformel von Gauß12. Eine Summe mit Fakultäten
4. Rechenregeln mit Summen13. Potenzsummen
5. Beweis der Summenformel von Gauß14. Teilbarkeitsaussagen
6. Eine Ungleichung zwischen Potenz und Quadrat15. Eine Formel für die Ableitung
7. Die geometrische Summe16. Auswahl einer Basis
8. Eine alternierende Summe17. Zerlegung durch Geraden
9. Binomialkoeffizienten, binomischer Lehrsatz18. Aufgaben

1. Das Prinzip der vollständigen Induktion

Es sei <math>\mathds{N}=\{0,1,2,3,\dotsc\}</math> die Menge der natürlichen Zahlen. Das Prinzip der vollständigen Induktion besagt: Es sei <math>P(n)</math> eine Eigenschaft von natürlichen Zahlen <math>n \in \mathds{N}</math>. Wir nehmen an:

(a) Es gilt <math>P(0)</math>.
(b) Wenn <math>n \in \mathds{N}</math> beliebig ist und <math>P(n)</math> gilt, dann gilt auch <math>P(n+1)</math>.

Dann lässt sich daraus folgern, dass <math>P(n)</math> für alle <math>n \in \mathds{N}</math> gilt.

Mit unserer anschaulichen Definition von <math>\mathds{N}</math> ist das klar: Aus (a) folgt <math>P(0)</math>. Mit (b) folgt dann <math>P(1)</math>. Mit (b) folgt dann weiter <math>P(2)</math>. So kann man sich zu jeder natürlichen Zahl hochhangeln. Das ist aber natürlich kein Beweis des Prinzips. Ein solcher Beweis kann nur gelingen, wenn man die Menge <math>\mathds{N}</math> formal definiert bzw. überhaupt erst einmal sagt, was Mengen eigentlich sind und welche Operationen mit ihnen erlaubt sind. Damit wollen wir uns hier nicht befassen (siehe z.B. hier). Es sei lediglich gesagt, dass das Prinzip der vollständigen Induktion die Eigenschaften der Menge der natürlichen Zahlen auszeichnet.

Das bedeutet konkret: Wenn man etwas über die natürlichen Zahlen beweisen will, dann muss man sich der vollständigen Induktion bedienen. Allerdings sollte sich das nur auf die Grundlagen beziehen, aus denen man auf direktem Wege weitere Aussagen über natürliche Zahlen ableiten kann, für die also keine separate vollständige Induktion mehr nötig ist. Mehr dazu später.

In konkreten Aufgaben, wo es darum geht, die Eigenschaft <math>P(n)</math> für alle <math>n \in \mathds{N}</math> nachzuweisen, nennt man den Nachweis von (a) den Induktionsanfang, und den Nachweis von (b) Induktionsschritt. Man kann auch andere Induktionsanfänge wählen: Wenn <math>n_0 \in \mathds{N}</math> beliebig ist und wir in (a) fordern, dass <math>P(n_0)</math> gilt, dann können wir mit (b) folgern, dass <math>P(n)</math> für alle <math>n \in \mathds{N}</math> mit <math>n \geq n_0</math> gilt.

2. Der Rekursionssatz

Was die Menge <math>\mathds{N}</math> der natürlichen Zahlen eigentlich auszeichnet und auch für die Praxis sehr wichtig ist, ist die Eigenschaft, Folgen (d.h. Abbildungen <math>\mathds{N} \to M</math>) rekursiv definieren zu können.

Genauer gesagt gilt der folgende Satz: Wenn <math>M</math> eine Menge ist, <math>m_0 \in M</math> ein Element ist und <math>S : M \to M</math> eine Abbildung ist, so gibt es genau eine Abbildung <math>a : \mathds{N} \to M</math>, sodass <math>a(0)=m_0</math> gilt und für alle <math>n \in \mathds{N}</math> gilt: <math>a(n+1)=S\bigl(a(n)\bigr)</math>. Die Rekursionsvorschrift ist hier also durch <math>S</math> gegeben, und der Startwert durch <math>m_0</math>. Wie man hier sieht, handelt dieser Rekursionssatz von Dedekind (den man erst beweisen kann, wenn man <math>\mathds{N}</math> formal definiert hat) nicht nur von der Menge <math>\mathds{N}</math>, sondern von dem Tripel <math>(\mathds{N},0,s)</math>, wobei <math>s : \mathds{N} \to \mathds{N},\, n \mapsto n+1</math> die Nachfolgerabbildung ist. Man kann stets auch bei einer beliebigen natürlichen Zahl <math>n_0</math> starten und Abbildungen <math>\mathds{N}_{\geq n_0} \to M</math> rekursiv definieren.

Aus der Eindeutigkeit im Rekursionssatz folgt übrigens das Prinzip der vollständigen Induktion: Man betrachte hierbei <math>a : \mathds{N}\to \{0,1\}</math> definiert durch <math>(a(n)=1) \Leftrightarrow P(n)</math> Aus <math>P(0)</math> folgt dann <math>a(0)=1</math>, und <math>P(n) \Rightarrow P(n+1)</math> besagt <math>a(n)=1 \Rightarrow a(n+1)=1</math>. Die konstante Abbildung <math>n \mapsto 1</math> erfüllt dieselbe Rekursionsvorschrift, sodass also <math>a(n)=1</math> für alle <math>n \in \mathds{N}</math> gilt, d.h. <math>P(n)</math> gilt für alle <math>n \in \mathds{N}</math>. Der Rekursionssatz ist also stärker als die vollständige Induktion.

Mit dem Rekursionssatz lässt sich die gesamte Arithmetik der natürlichen Zahlen definieren. So ist etwa die Addition <math>m+n</math> rekursiv durch <math>m+0:=m</math> und <math>m+(n+1):=(m+n)+1</math> definiert. Daraus lassen sich dann per vollständiger Induktion Rechenregeln wie etwa <math>m+(n+k)=(m+n)+k</math> nachweisen. Wir wollen aber in diesem Artikel die Arithmetik der natürlichen und sogar reellen Zahlen als gegeben hinnehmen.
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]