Die Mathe-Redaktion - 28.04.2017 00:30 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 384 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Stern Mathematik: Vollständige Indoktrination
Freigegeben von matroid am Mi. 23. März 2016 20:42:30
Verfasst von Martin_Infinite -   2555 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Vollständige Indoktrination

Die vollständige Induktion steht im ersten Semester auf dem Lehrplan und wird mit vielen einfachen Aufgaben eingeübt. Das hat oftmals zur Folge, dass Studienanfänger alles, wo eine natürliche Zahl vorkommt, mittels vollständiger Induktion beweisen möchten, oder sogar beweisen sollen.

Was diese Einschränkung für Auswirkungen auf die mathematische Kreativität hat, und dass andere Beweismethoden oftmals viel erhellender und eleganter sind, darum wird es in diesem Artikel gehen. Dazu werden viele Beispiele herangezogen. Es werden auch genügend Beispiele dafür besprochen, wo eine vollständige Induktion sinnvoll oder sogar notwendig ist.
 
Dieser Artikel richtet sich v.a. an fortgeschrittene Schüler und Studienanfänger.


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.

3. Die Summenformel von Gauß

Sei <math>n \in \mathds{N}</math>. Für die Summe der ersten <math>n</math> natürlichen Zahlen gilt die Summenformel

<math>\displaystyle 1 + 2 + \dotsc + n = \frac{n \cdot (n+1)}{2}.</math>
 
Laut einer Anekdote hat Carl Friedrich Gauß dafür als neunjähriger Schüler einen sehr einleuchtenden Beweis vorgelegt (welcher allerdings schon in der vorgriechischen Mathematik bekannt war): Man summiere die natürlichen Zahlen einmal aufsteigend, und einmal absteigend auf:
 
<math>\begin{array}{ccccccccc}
1 & + & 2 & + & 3 & + & \dotsc & + & n \\
n & + & n{-}1 & + & n{-}2 & + & \dotsc & + & 1
\end{array}</math>
 
Wenn wir beide Summen summieren, ergibt sich einerseits <math>2 \cdot (1 + 2 + \dotsc + n)</math>, und andererseits durch Umordnung
 
<math>(1 + n) + (2 + (n{-}1)) + (3+(n{-}2)) + \dotsc + (n+1).</math>

Jeder Summand hat hier den Wert <math>n+1</math>, und es gibt <math>n</math> Summanden. Wir erhalten also tatsächlich
 
<math>2 \cdot (1 + 2 + \dotsc + n) = n \cdot (n+1).</math>
 
Wir haben hier keine vollständige Induktion benötigt. Wir haben uns allerdings auf grundlegende Rechentechniken mit natürlichen Zahlen berufen, und außerdem endliche Summen benutzt. Die Pünktchenschreibweise könnte uns daran zweifeln lassen, dass wir hier sauber gearbeitet haben. An der Universität wird nun üblicherweise zum Zwecke der Präzisierung folgendes gemacht: Die Studenten sollen die Formel

<math>\displaystyle \sum_{i=1}^{n} i = \frac{n \cdot (n+1)}{2}</math>
 
mit vollständiger Induktion nach <math>n</math> beweisen. Wie das geht, möchte ich hier nicht wiederholen. Es bringt jedenfalls keinerlei Einsicht und ist lediglich eine Rechenaufgabe, die die Definition des Summensymbols <math>\Sigma</math> und die Bruchrechenregeln ausnutzt. Wenn man die Aufgabe erledigt hat, weiß man aber noch nicht, wie man überhaupt auf diese Formel gekommen ist, wenn man nicht ohnehin schon Gauß' Herleitung kannte. Wenn man vor dem Problem steht, eine andere Summe, etwa <math>\sum_{i=1}^{n} i^3</math>, auszuwerten, dann hat man durch den Induktionsbeweis für <math>\sum_{i=1}^{n} i</math> nichts dazugelernt, was einem dabei weiterhelfen könnte. Wenn man also darauf gedrillt wird, immer Induktionsbeweise zu führen, dann entgeht einem die Möglichkeit, kreative mathematische Argumente zu entdecken, oder es zumindest zu versuchen und damit zu üben. Viele Studienanfänger starten zwar eine Induktion, wissen dann aber im Induktionsschritt auch nicht wirklich weiter.
 
An der Universität sollen die Beweise natürlich präzise sein. Wäre es also nicht viel erhellender, wenn man den intuitiven Beweis von Gauß präzisieren würde? Wir müssen ihn nicht fallenlassen und so tun, als ob es sich um ein historisches Artefakt einer informalen Mathematiktradition handelt, welches von der vollständigen Induktion abgelöst worden ist. Wir nehmen es nun also in Angriff, den Beweis von Gauß auf ein präzises Fundament zu stellen.
 

4. Rechenregeln mit Summen

Zunächst einmal ist für eine endliche Folge von reellen Zahlen <math>a_1,\dotsc,a_n</math> (mit <math>n \in \mathds{N}_{\geq 1}</math>) die Summe

<math>\displaystyle \sum_{i=1}^{n} a_i</math>

rekursiv definiert durch

<math>\displaystyle \sum_{i=1}^{1} a_i = a_1</math>

und

<math>\displaystyle \sum_{i=1}^{n+1} a_i = \sum_{i=1}^{n} a_i \, + \, a_{n+1}.</math>

Zum Beispiel gilt also <math>\sum_{i=1}^{4} a_i = ((a_1+a_2)+a_3)+a_4</math>. Wir kürzen diesen Ausdruck mit <math>a_1+a_2+a_3+a_4</math> ab. Genauso benutzt man für beliebiges <math>n \in \mathds{N}_{\geq 1}</math> manchmal anstelle von <math>\sum_{i=1}^{n} a_i</math> die Pünktchenschreibweise <math>a_1+a_2+\dotsc+a_n</math>, wenn dies zu keinen Verwirrungen führt. Ganz ähnlich definiert man für eine Folge <math>a_{n_0},\dotsc,a_n</math> mit einem beliebigen Startindex <math>n_0</math> die Summe <math>\sum_{i=n_0}^{n} a_i</math> rekursiv; für <math>n < n_0</math> sei dies <math>=0</math>. Man kann sich dann leicht die Rechenregel

<math>\displaystyle (0) ~~~~ \sum_{i=1}^{n} a_i = \sum_{i=1}^{j} a_i \, + \, \sum_{i=j+1}^{n} a_i</math>   Aufspaltungsregel

für <math>1 \leq j \leq n</math> überlegen. Weil die Addition von reellen Zahlen kommutativ und assoziativ ist (das müssen wir an dieser Stelle als bekannt voraussetzen), erwarten wir, dass wir die Summanden <math>a_i</math> in der Summe <math>\sum_{i=1}^{n} a_i</math> beliebig umordnen können. Das heißt: Für jede bijektive Abbildung <math>\sigma : \{1,\dotsc,n\} \to \{1,\dotsc,n\}</math> gilt

<math>\displaystyle (1) ~~~  \sum_{i=1}^{n} a_i = \sum_{i=1}^{n} a_{\sigma(i)}.</math>    verallgemeinerte Kommutativität
 
Das beweisen wir nun mittels vollständiger Induktion nach <math>n</math>. Der Fall <math>n=1</math> ist klar. Nun gelte die Behauptung für ein <math>n</math>. Wenn <math>\sigma(n+1)=n+1</math>, dann schränkt sich <math>\sigma</math> zu einer bijektiven Abbildung <math>\tau: \{1,\dotsc,n\} \to \{1,\dotsc,n\}</math> ein. Wenden wir die Induktionsannahme also auf <math>\tau</math> an, so bekommen wir
 
<math>\displaystyle  \sum_{i=1}^{n+1} a_{\sigma(i)} =\sum_{i=1}^{n} a_{\sigma(i)} \, + \, a_{\sigma(n+1)} =\sum_{i=1}^{n} a_{\tau(i)} \, + \, a_{n+1} = \sum_{i=1}^{n} a_i \, + \, a_{n+1} = \sum_{i=1}^{n+1} a_i.</math>
 
Nun gelte <math>\sigma(n+1) \neq n+1</math>. Wähle das <math>j \in \{1,\dotsc,n\}</math> mit <math>\sigma(j)=n+1</math>. Dann gilt
 
<math>\displaystyle \displaystyle  ~~~\,\sum_{i=1}^{n+1} a_{\sigma(i)} \\\medskip
= \sum_{i=1}^{n} a_{\sigma(i)} \, + \, a_{\sigma(n+1)} \\ \medskip =\sum_{i=1}^{j-1} a_{\sigma(i)} \, + \, a_{\sigma(j)} +
\sum_{i=j+1}^{n} a_{\sigma(i)} \,+\, a_{\sigma(n+1)}  \\ \medskip
=\sum_{i=1}^{j-1} a_{\sigma(i)} \, + \, a_{\sigma(n+1)} + \sum_{i=j+1}^{n} a_{\sigma(i)} \,+\, a_{n+1}  \\ \medskip
=\sum_{i=1}^{n} a_{\tau(i)} \, + \, a_{n+1},</math>
 
wobei die bijektive Abbildung <math>\tau : \{1,\dotsc,n\} \to \{1,\dotsc,n\}</math> definiert ist durch <math>\tau(i)=\sigma(i)</math> für <math>i \neq j</math> und <math>\tau(j)=\sigma(n+1)</math>. Wenden wir also die Induktionsannahme an, so erhalten wir
 
<math>\displaystyle =\sum_{i=1}^{n} a_i \, + \, a_{n+1} =\sum_{i=1}^{n+1} a_i. ~~~ \checkmark</math>

Aus (1) folgt, dass wir <math>\sum_{i \in A} a_i</math> für jede endliche Menge <math>A</math> und jede Abbildung <math>a : A \to \mathds{R}</math> eindeutig definieren können, indem wir irgendeine Bijektion <math>\sigma : \{1,\dotsc,n\} \to A</math> wählen und dann die Summe als <math>\sum_{i=1}^{n} a_{\sigma(i)}</math> definieren; das Ergebnis hängt nicht von der Wahl von <math>\sigma</math> ab. Die Regel (0) nimmt hier die Form

<math>\displaystyle (0') ~~~ \sum_{i \in A \cup B} a_i = \sum_{i \in A} a_i \, + \, \sum_{i \in B} a_i</math>    Aufspaltungsregel

für disjunkte Mengen <math>A,B</math> an. Wir erwarten ferner, dass für jede weitere Folge <math>b_1,\dotsc,b_n</math> die Rechenregel

<math>\displaystyle (2) ~~~ \sum_{i=1}^{n} a_i \, + \, \sum_{i=1}^{n} b_i = \sum_{i=1}^{n} (a_i+b_i)</math>    Additivität

gilt. Wir beweisen dies per Induktion nach <math>n \in \mathds{N}_{\geq 1}</math>. Der Induktionsanfang mit <math>n=1</math> ist klar, beide Seiten sind dann nach Definition <math>a_1+b_1</math>. Nun gelte die Gleichung für ein <math>n</math>. Wir zeigen, dass sie auch für <math>n+1</math> gilt:

<math>\displaystyle ~~~~\, \sum_{i=1}^{n+1} a_i \, + \, \sum_{i=1}^{n+1} b_i \\ \medskip =\Left(\sum_{i=1}^{n} a_i \, + \, a_{n+1}\Right) + \Left(\sum_{i=1}^{n} b_i \, + \, b_{n+1}\Right)\\ \medskip
 =\Left(\sum_{i=1}^{n} a_i \, + \, \sum_{i=1}^{n} b_i\Right) + (a_{n+1} + b_{n+1})\\ \medskip
 =\sum_{i=1}^{n} (a_i+b_i) + (a_{n+1} + b_{n+1})\\ \medskip
 =\sum_{i=1}^{n+1} (a_i+b_i). ~~~ \checkmark</math>

Beim zweiten Gleichheitszeichen haben wir hier Assoziativität und Kommutativität der Addition reeller Zahlen ausgenutzt.

Wenn die Folgenglieder <math>a_1,\dotsc,a_n</math> einen konstanten Wert <math>r</math> haben, dann gilt natürlich

<math>\displaystyle (3) ~~~ \sum_{i=1}^{n} r = n \cdot r.</math>   konstante Summen

Das sieht man leicht per Induktion nach <math>n \in \mathds{N}_{\geq 1}</math>, wobei hier die Rechenregeln <math>1 \cdot r = r</math> und <math>(n{+}1) \cdot r = n \cdot r + r</math> eingehen (die man, je nach Konstruktion von <math>\mathds{R}</math>, auch beweisen kann).

5. Beweis der Summenformel von Gauß

Wir können nun den Beweis von Gauß folgendermaßen in aller Präzision führen: Wir beginnen mit

<math>\displaystyle 2 \cdot \sum_{i=1}^{n} i =   \sum_{i=1}^{n} i \, + \, \sum_{i=1}^{n} i.</math>
 
Weil die Abbildung <math>\{1,\dotsc,n\} \to \{1,\dotsc,n\}</math>, <math>i \mapsto n+1-i</math> bijektiv ist (sie ist zu sich selbst invers!), gilt wegen (1)

<math>\displaystyle \sum_{i=1}^{n} i = \sum_{i=1}^{n} (n+1-i).</math>
 
Wir erhalten daher mit (2) und (3):

<math>\displaystyle 2 \cdot \sum_{i=1}^{n} i =\sum_{i=1}^{n} i \, + \, \sum_{i=1}^{n} (n+1-i) = \sum_{i=1}^{n} (i+n+1-i) = \sum_{i=1}^{n} (n+1) = n \cdot (n+1). ~~~ \checkmark</math>
 
Wenn man nur auf die Summenformel von Gauß fokussiert ist, scheinen wir hier relativ viel Aufwand betrieben zu haben. Jedoch sind die allgemeinen Rechenregeln mit endlichen Summen sehr nützlich und werden auch in vielen anderen Situationen ständig verwendet. Es ist also gut, dass wir sie einmal bewiesen haben, weil sich damit nun viele andere Rechnungen wie von selbst ergeben. Unser Beweis der Summenformel von Gauß ist nur eines von vielen Beispielen.
 
Zudem ist unser Beweis bzw. der Beweis von Gauß, wie bereits gesagt, eine Herleitung der Summenformel und nicht nur eine bloße Überprüfung einer Formel, deren Herkunft zunächst einmal ungewiss ist. Herleitungen sind immer erhellender als bloße Überprüfungen. Denn sie bringen Einsichten, die man auch woanders sinnvoll einsetzen kann.
 
Bei den Beweisen von (1),(2) und (3) hatten wir allerdings keine andere Wahl, als die vollständige Induktion zu nutzen, weil es sich um derart grundlegende Aussagen handelt, dass sie sich nicht auf etwas sonst bereits Bekanntes (ohne Zirkularität) zurückführen lassen. Zudem war nicht wirklich eine Herleitung erforderlich, um auf diese naheliegenden Rechenregeln zu kommen.

Eine alternative Herleitung inkl. Verallgemeinerung der Summenformel gibt es in Abschnitt 13.

6. Eine Ungleichung zwischen Potenz und Quadrat

Berechnen wir einmal die Werte von <math>2^n</math> und <math>n^2</math> für <math>n=0,\dotsc,10</math>, so bekommen wir schnell die Vermutung, dass <math>2^n \geq n^2</math> für <math>n \geq 4</math> und sogar <math>2^n > n^2</math> für <math>n \geq 5</math> gilt.

<math>\begin{tabular}{c|lllllllllll}
$n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
$2^n$ & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 \\
$n^2$ & 0 & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81 & 100\end{tabular}</math>
 
Die Ungleichung <math>\forall n \in \mathds{N}_{\geq 4} (2^n \geq n^2)</math> wollen wir zunächst mit vollständiger Induktion beweisen: Der Induktionsanfang mit <math>n=4</math> ist klar, beide Seiten sind <math>16</math>. Es gelte nun <math>2^n \geq n^2</math>. Dann folgt

<math>\displaystyle 2^{n+1}= 2^n \cdot 2 \geq n^2 \cdot 2 = n^2 + n^2,</math>

und andererseits

<math>\displaystyle (n+1)^2 = n^2 + 2n + 1.</math>

Es würde also reichen, <math>n^2 \geq 2n+1</math> zu zeigen, denn dann folgt <math>2^{n+1} \geq (n+1)^2</math>. Wenn wir jetzt nicht nachdenken wollen, können wir diese Gleichung ebenfalls mit vollständiger Induktion beweisen. Der Induktionsanfang gilt schon für <math>n=3</math>, denn es gilt <math>3^2=9 \geq 7=2 \cdot 3+1</math>. Wenn nun <math>n^2 \geq 2n+1</math> gilt, dann folgt

<math>\displaystyle (n+1)^2 = n^2 + 2n +1  \geq (2n+1)+2n+1=4n+2=2n+(2n+2) \geq 2n+3=2(n+1)+1.</math>

Man kann sich auch etwas geschickter anstellen und die Ungleichung <math>n^2 \geq 2n+1</math> direkt einsehen:

<math>n^2 = n \cdot n \geq n \cdot 3 = 2n + n \geq 2n+1.</math>

Darauf musste man erst einmal kommen.
 
Es geht aber auch ganz anders, nämlich mit einem kombinatorischen Beweis. Dies bedeutet, dass man mit endlichen Mengen arbeitet (also solche, die mit einer Menge der Form <math>\{1,\dotsc,n\}</math> mit <math>n \in \mathds{N}</math> gleichmächtig sind) und die Anzahl <math>\#</math> ihrer Elemente berechnet (z.B. <math>\#\{\spadesuit,\clubsuit\}=2</math>). Aus Resultaten über endliche Mengen ergeben sich dann Resultate über natürliche Zahlen. Das lässt sich auch alles formalisieren, wenn man allgemeine Rechenregeln wie etwa
 
<math>\#(A \sqcup B) = \# A + \# B</math>
 
und

<math>\#(A \times B) = \# A \cdot \#B</math>
 
beweist (in der Reihenfolge!), für die sich die vollständige Induktion nach <math>\# B</math> anbietet.
 
Wir beginnen mit der Beobachtung, dass <math>2^n</math> die Anzahl der Teilmengen von <math>\{1,\dotsc,n\}</math> ist (bzw. einer beliebigen <math>n</math>-elementigen Menge). Das sieht man so: Eine Teilmenge von <math>\{1,\dotsc,n+1\}</math> enthält entweder <math>n+1</math> und dann ist der Rest eine Teilmenge von <math>\{1,\dotsc,n\}</math>, oder aber sie enthält <math>n+1</math> nicht und ist ohnehin schon eine Teilmenge von <math>\{1,\dotsc,n\}</math>. Es gibt also doppelt so viele Teilmengen von <math>\{1,\dotsc,n+1\}</math> wie Teilmengen von <math>\{1,\dotsc,n\}</math>. Ferner hat <math>\{1,\dotsc,0\}:=\emptyset</math> genau eine Teilmenge, nämlich <math>\emptyset</math>. Wir sehen also, dass die Anzahl der Teilmengen von <math>\{1,\dotsc,n\}</math> dieselbe Rekursion wie <math>2^n</math> erfüllt und daher mit <math>2^n</math> übereinstimmen muss. Alternativ könnte man auch gleich die allgemeine Rechenregel
 
<math>\# \mathrm{Abb}(A,B) = \#B^{\# A}</math>
 
für endliche Mengen <math>A,B</math> beweisen (per Induktion nach <math>\# A</math>) und dann benutzen, dass es eine Bijektion zwischen Abbildungen <math>A \to \{0,1\}</math> und Teilmengen von <math>A</math> gibt, nämlich <math>f \mapsto f^{-1}(\{1\})</math>.
 
Die Menge <math>\{1,\dotsc,n\}</math> hat genau eine leere Teilmenge, <math>\emptyset</math>, und genau <math>n</math> Teilmengen <math>\{1\},\dotsc,\{n\}</math> mit genau einem Element. Wie viele Teilmengen mit genau <math>2</math> Elementen gibt es? Jedes Paar <math>(i,j)</math> mit <math>1 \leq i,j \leq n</math> und <math>i \neq j</math> liefert eine solche Teilmenge <math>\{1,\dotsc,n\}</math>, aber weil dabei <math>(i,j)</math> und <math>(j,i)</math> dieselbe Teilmenge liefern, gibt es doppelt so viele Paare wie Teilmengen mit <math>2</math> Elementen. Die Anzahl der Paare ist <math>n \cdot (n-1)</math>, weil es nämlich für das <math>i</math> genau <math>n</math> mögliche Wahlen gibt, und dann für <math>j</math> nur noch <math>n-1</math> mögliche Wahlen. Also gibt es <math>\frac{n(n-1)}{2}</math> Teilmengen mit zwei Elementen. Wegen <math>2 < n-2 < n</math> für <math>n \geq 5</math> erhalten wir auch noch die Teilmengen mit <math>n-2</math> Elementen, die aber durch Komplementbildung zu den Teilmengen mit <math>2</math> Elementen korrespondieren. Ihre Anzahl ist also ebenfalls <math>\frac{n(n-1)}{2}</math>. Wir haben damit insgesamt mindestens
 
<math>1 + n + 2 \cdot \frac{n(n-1)}{2} = n^2+1</math>

Teilmengen gefunden. Es gilt also <math>2^n > n^2</math> für <math>n \geq 5</math>.
 
Wenn man bereits mit Binomialkoeffizienten vertraut ist (vgl. Abschnitt 10), so kann man dieses Argument auch viel knapper präsentieren:

<math>\displaystyle 2^n = \sum_{k=0}^{n} \binom{n}{k} \geq \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \binom{n}{n-2} = n^2+1.</math>
 
Und genau hier wird die Stärke dieses Ansatzes klar: Wir können <math>2^n</math> viel genauer nach unten abschätzen und müssen dabei nichts weiter tun, als ein paar Binomialkoeffizienten aufzusummieren. Es handelt sich um keine zufällige Beobachtung, die mit einer Tabelle von Zahlenwerten vermutet und dann per Induktion bestätigt wird, sondern um eine systematische Herleitung. Übrigens gilt noch genauer für <math>n \geq 5</math>

<math>\displaystyle 2^n \geq 2 \binom{n}{0} + 2 \binom{n}{1} + 2 \binom{n}{2} = n^2+n+2,</math>
 
wobei Gleichheit für <math>n=5</math> gilt.
 
Kombinatorisch ist übrigens die obige Ungleichung <math>n^2  \geq 2n+1</math> (für <math>n \geq 3</math>) sofort klar. Man muss dafür ja nur <math>2n+1</math> verschiedene geordnete Paare <math>(i,j)</math> mit <math>1 \leq i,j \leq n</math> angeben. Und dafür bieten sich etwa <math>(1,1),\dotsc,(n,1)</math>, <math>(1,2),\dotsc,(n,2)</math> und <math>(1,3)</math> an. Hieran sieht man sehr schön, wie die Kombinatorik den Zahlen und ihrer Arithmetik eine anschauliche Bedeutung gibt und damit den Umgang mit ihnen erleichtert.

7. Die geometrische Summe

Für <math>n \in \mathds{N}</math> und zwei reelle Zahlen <math>a,b</math> gilt die Gleichung

<math>\displaystyle (a-b) (a^n + a^{n-1} b + \dotsc + a b^{n-1} + b^n) = a^{n+1} - b^{n+1},</math>
 
oder etwas präziser aufgeschrieben

<math>\displaystyle (a-b) \sum_{i=0}^{n} a^{n-i} b^i = a^{n+1}-b^{n+1}.</math>
 
Ein separater Beweis mit vollständiger Induktion ist hier nicht nötig. Stattdessen sollte man sich auf die allgemeinen Rechenregeln

<math>\displaystyle (4) ~~~ r \sum_{i=0}^{n} a_i = \sum_{i=0}^{n} r a_i</math>   verallgemeinertes Distributivgesetz

<math>\displaystyle (5) ~~~ \sum_{i=0}^{n-1} a_{i+1} = \sum_{i=1}^{n} a_i</math>   Indexshift

 
berufen, die auch in vielen anderen Situationen sehr hilfreich sind und sich ganz leicht per vollständiger Induktion bestätigen lassen. Damit können wir den Wert der Summe auch herleiten, d.h. wir müssen das Ergebnis <math>a^{n+1}-b^{n+1}</math> gar nicht vorab kennen, um es zu überprüfen, wie das bei einem Induktionsbeweis der Fall wäre.

Mit (4) und (5) berechnen wir nun:
 
<math>\displaystyle ~~~\, (a-b) \sum_{i=0}^{n} a^{n-i} b^i \\ \medskip
= a  \sum_{i=0}^{n} a^{n-i} b^i \, - \,  b \sum_{i=0}^{n} a^{n-i} b^i \\ \medskip
= \sum_{i=0}^{n} a^{n-i+1} b^i - \sum_{i=0}^{n} a^{n-i} b^{i+1} \\ \medskip
= \sum_{i=0}^{n} a^{n-i+1} b^i - \sum_{i=1}^{n+1} a^{n-i+1} b^{i} \\ \medskip
= a^{n+1}+\sum_{i=1}^{n} a^{n-i+1} b^i   - \sum_{i=1}^{n} a^{n-i+1} b^{i} - b^{n+1}\\ \medskip
= a^{n+1} - b^{n+1}.</math>
 
Falls <math>a \neq b</math>, können wir das Ergebnis auch schreiben als

<math>\displaystyle \sum_{i=0}^{n} a^i b^{n-i} = \frac{a^{n+1} - b^{n+1}}{a-b}.</math>
 
Der Spezialfall <math>b=1</math> lautet:

<math>\displaystyle \sum_{i=0}^{n} a^i = \frac{a^{n+1}-1}{a-1}</math>   geometrische Summenformel
 
Hierfür gibt es auch geometrische Beweise (siehe hier). Wir können denselben Beweis auch etwas intuitiver mit der Pünktchenschreibweise notieren: Wir multiplizieren dazu <math>(a-b)(a^n + a^{n-1} b + \dotsc + a b^{n-1} + b^n)</math> aus (d.h. wenden das Distributivgesetz an) und erhalten

<math>a^{n+1} + a^n b + \dotsc + a^2 b^{n-1} + a b^n - a^n b - a^{n-1} b - \dotsc - a b^n - b^{n+1}.</math>
 
Hierbei kürzen sich alle Terme weg, außer <math>a^{n+1}</math> und <math>b^{n+1}</math>. Auch das ist ein präziser Beweis, sobald man die hier implizit verwendeten Rechenregeln allgemein bewiesen hat.

8. Eine alternierende Summe

Wir möchten die alternierende Summe <math>\sum_{i=1}^{2n} \frac{(-1)^{i-1}}{i}</math> berechnen (oder jedenfalls etwas vereinfachen). Wir bedienen uns dabei lediglich der allgemeinen Rechenregeln für Summen:
 
<math>\displaystyle ~~~\,\sum_{i=1}^{2n} \frac{(-1)^{i-1}}{i} \\ \medskip
=\sum_{\substack{i \in \{1,\dotsc,2n\} \\ i \text{ ungerade}}} \frac{(-1)^{i-1}}{i} + \sum_{\substack{i \in \{1,\dotsc,2n\} \\ i \text{ gerade}}} \frac{(-1)^{i-1}}{i} \\ \medskip
=\sum_{i=1}^{n} \frac{1}{2i-1} + \sum_{i=1}^{n} \left(-\frac{1}{2i}\right) \\ \medskip
=\sum_{i=1}^{n} \frac{1}{2i-1} + \sum_{i=1}^{n} \left(\frac{1}{2i}-\frac{1}{i}\right) \\ \medskip
=\sum_{i=1}^{n} \frac{1}{2i-1} + \sum_{i=1}^{n} \frac{1}{2i} -  \sum_{i=1}^{n} \frac{1}{i} \\ \medskip
=\sum_{i=1}^{2n} \frac{1}{i} -  \sum_{i=1}^{n} \frac{1}{i} \\ \medskip
=\sum_{i=n+1}^{2n} \frac{1}{i}.</math>
 
Man könnte auch verlangen, die Gleichung

<math>\displaystyle  \sum_{i=1}^{2n} \frac{(-1)^{i-1}}{i} = \sum_{i=n+1}^{2n} \frac{1}{i}</math>

per Induktion nach <math>n</math> zu zeigen. Aber das wäre wieder nichts weiter als eine isolierte Rechenübung, die nicht die Frage beantworten kann, wie man überhaupt auf die rechte Seite gekommen ist.

9. Binomialkoeffizienten und der binomische Lehrsatz

Seien <math>a,b</math> zwei reelle Zahlen und <math>n</math> eine natürliche Zahl. Multiplizieren wir das Produkt

<math>(a+b)^n = (a+b) \cdot \dotsc \cdot (a+b)</math>

mit <math>n</math> Faktoren aus, d.h., wir benutzen das Distributivgesetz mehrmals, so entsteht eine Summe von Produkten der Form <math>d_1 \cdot \dotsc \cdot d_n</math>, wobei jeweils <math>d_i=a</math> oder <math>d_i=b</math> ist. Wenn hierbei <math>k \in \mathds{N}</math> die Anzahl der <math>a</math>s ist, so ist folglich <math>n-k</math> die Anzahl der <math>b</math>s. Wir erhalten also als Faktor <math>a^k b^{n-k}</math>. Dieser kommt allerdings mehrfach vor. So tragen zum Beispiel für <math>n=5</math> sowohl <math>a \cdot a \cdot b \cdot b \cdot  b</math> als auch <math>b \cdot a \cdot b \cdot  b \cdot a</math> zum Faktor <math>a^2 b^3</math> bei. Allgemein kommt <math>a^k b^{n-k}</math> genau dann vor, wenn wir uns beim Ausmultiplizieren der <math>n</math> Faktoren <math>a+b</math> genau <math>k</math> mal für <math>a</math> und bei den restlichen Faktoren für <math>b</math> entschieden haben. Wir sehen daher, dass <math>a^k b^{n-k}</math> genau so oft vorkommt, wie es Teilmengen von <math>\{1,\dotsc,n\}</math> mit <math>k</math> Elementen gibt. Dieser Anzahl gibt man nun einen Namen: Der Binomialkoeffizient <math>\binom{n}{k}</math> sei die Anzahl der Teilmengen von <math>\{1,\dotsc,n\}</math> mit genau <math>k</math> Elementen. Wir haben damit bewiesen:
 
<math>\displaystyle \displaystyle (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.</math>
 
Dies ist der binomische Lehrsatz. Unser etwas informale Beweis lässt sich auch relativ leicht formalisieren, und ist in jedem Falle viel erhellender als ein Induktionsbeweis des binomischen Lehrsatzes, wo wiederum unklar wäre, wo überhaupt die rechte Seite herkommt. Dabei ist es doch ganz einfach: Die rechte Seite ist das Ergebnis des Ausmultiplizierens von <math>(a+b) \cdot \dotsc \cdot (a+b)</math>, mehr nicht!
 
Für die konkrete Berechnung der Binomialkoeffizienten ist die folgende Rekursionsgleichung sehr nützlich:

<math>\displaystyle \binom{n}{0} = 1, ~ \binom{0}{k+1}=0 \text{  und  } \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}.</math>
 
Die ersten beiden Aussagen sind klar, denn eine Menge hat immer genau eine Teilmenge mit keinem Element, nämlich <math>\emptyset</math>, und die leere Menge nur sich selbst als Teilmenge. Die dritte Aussage können wir uns so überlegen, dass eine <math>k</math>-elementige Teilmenge von <math>\{1,\dotsc,n+1\}</math> entweder <math>n+1</math> enthält und dann der Rest eine <math>k-1</math>-elementige Teilmenge von <math>\{1,\dotsc,n\}</math> ist, oder aber <math>n+1</math> nicht enthält und damit eine <math>k</math>-elementige Teilmenge von <math>\{1,\dotsc,n\}</math> ist.
 
Mit der Rekursionsgleichung kann man nun das sog. Pascalsche Dreieck aufzeichnen (vgl. Wikipedia). Natürlich gilt <math>\binom{n}{k}=0</math> für <math>k>n</math>, weil es dann keine entsprechenden Teilmengen gibt. Ferner ist die Symmetrie <math>\binom{n}{k} = \binom{n}{n-k}</math> durch Komplementbildung der Teilmengen klar. Die mehr oder weniger explizite Formel

<math>\displaystyle\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dotsc \cdot (n-k+1)}{1 \cdot 2 \cdot \dotsc \cdot k}</math>
 
kann man sich ebenfalls leicht kombinatorisch überlegen (keine Induktion ist notwendig), ähnlich wie im Spezialfall <math>k=2</math>, den wir in Abschnitt 6 gesehen hatten.

10. Eine Summe mit Binomialkoeffizienten

Wir möchten für <math>n \in \mathds{N}_{\geq 1}</math> die Summe <math>\sum_{k=1}^{n} k  \binom{n}{k}</math> berechnen. Der binomische Lehrsatz ist zwar nicht direkt anwendbar, aber wir können uns mit einem Trick behelfen: Es gilt für <math>1 \leq k \leq n</math> die Gleichung

<math>\displaystyle \binom{n}{k} = \frac{n}{k} \, \binom{n-1}{k-1}.</math>

Dies ist eine Umformulierung der expliziten Gleichung von <math>\binom{n}{k}</math>. Alternativ kann man sich <math>k \binom{n}{k} = \binom{n-1}{k-1} n</math> auch kombinatorisch überlegen. Damit können wir nun also berechnen:

<math>\displaystyle \sum_{k=1}^{n} k  \binom{n}{k} = \sum_{k=1}^{n} n \binom{n-1}{k-1} = n \sum_{k=0}^{n-1} \binom{n-1}{k} = n 2^{n-1}.</math>
 
Es war also keine vollständige Induktion nötig (und wäre auch gar nicht möglich gewesen, ohne das Ergebnis <math>n 2^{n-1}</math> schon zu kennen). Zur Abschreckung zeigen wir einmal, was man dabei hätte rechnen müssen: Der Anfang <math>n=1</math> ist klar, beide Seiten sind gleich <math>1</math>. Die Gleichung gelte für ein <math>n</math>. Dann berechnen wir:

<math>\displaystyle ~~~\,\sum_{k=1}^{n+1} k  \binom{n+1}{k} \\ \medskip
= \sum_{k=1}^{n+1} \left(k  \binom{n}{k}+k  \binom{n}{k-1}\right) \\ \medskip
=\sum_{k=1}^{n} k  \binom{n}{k} + \sum_{k=1}^{n+1} k \binom{n}{k-1} \\ \medskip
=\sum_{k=1}^{n} k  \binom{n}{k} + \sum_{k=0}^{n} (k+1) \binom{n}{k} \\ \medskip
=2 \sum_{k=1}^{n} k  \binom{n}{k} + \sum_{k=0}^{n} \binom{n}{k} \\ \medskip
= 2 n 2^{n-1} + 2^n = (n+1) 2^n.</math>
 
Es gibt übrigens noch einen alternativen, sehr eleganten analytischen Beweis: Wir leiten die aus dem binomischen Lehrsatz bekannte Gleichung von Polynomen

<math>\displaystyle (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k</math>

formal nach <math>x</math> ab und erhalten dadurch (unter Verwendung der Ableitungsregeln)

<math>\displaystyle n (1+x)^{n-1} = \sum_{k=1}^{n} \binom{n}{k} k x^{k-1}.</math>

Einsetzen von <math>x=1</math> liefert das Gewünschte. Diese Technik des Ableitens lässt sich in vielen Situationen anwenden; siehe zum Beispiel diesen Artikel.

11. Eine Ungleichung mit der Fakultät

Für <math>n \in \mathds{N}_{\geq 1}</math> behaupten wir

<math>\displaystyle n! > \left(\frac{n}{2}\right)^{\mathlarger{\frac{n}{2}}}\hspace{-3pt}.</math>
 
Dabei ist die Fakultät <math>n! = 1 \cdot \dotsc \cdot n</math> rekursiv durch <math>0! = 1</math> und <math>(n+1)! = n! \cdot (n+1)</math> definiert. Bevor man hier gleich reflexartig anfängt, eine Induktion zu starten und beim Induktionsschritt ziemlich sicher ratlos verbleibt, sollte man sich lieber die Faktoren in der Fakultät genauer anschauen. Wenn <math>n</math> zum Beispiel gerade ist, dann sind die letzten <math>n/2</math> Faktoren <math>n/2+1,\dotsc,n/2+n/2=n</math> allesamt größer als <math>n/2</math>. Die behauptete Ungleichung ist also sofort klar. Wenn <math>n</math> ungerade ist, so lauten die letzten <math>(n+1)/2</math> Faktoren <math>(n+1)/2,\dotsc,(n+1)/2 + (n-1)/2=n</math>. Diese sind allesamt größergleich als <math>(n+1)/2</math>. Wir sehen daher <math>n! \geq ((n+1)/2)^{(n+1)/2} > (n/2)^{n/2}</math>.

Benutzt haben wir hier natürlich die allgemeinen Rechenregeln für Produkte. Zum Beispiel dass aus <math>a_i > b_i > 0</math> für <math>i=1,\dotsc,n</math> auch <math>\prod_{i=1}^{n} a_i > \prod_{i=1}^{n} b_i</math> folgt. Das lässt sich sofort per Induktion nach <math>n</math> bestätigen. Eine noch viel einfachere Ungleichung ist

<math>\displaystyle n! \geq 2^{n-1}</math>

für <math>n \geq 1</math>. Dies ist klar, denn in <math>n! = 2 \cdot \dotsc \cdot n</math> ist jeder der <math>n-1</math> Faktoren <math>\geq 2</math>. Keine separate Induktion ist nötig - die würde alles nur verkomplizieren.

12. Eine Summe mit Fakultäten

Wogegen es für die Summe <math>\sum_{k=1}^{n} k!</math> anscheinend keine Vereinfachung gibt, können wir die Summe <math>\sum_{k=1}^{n} k \cdot k!</math> drastisch vereinfachen: Wir schreiben <math>k=(k+1)-1</math> (um gleich die Rekursionsgleichung der Fakultät auszunutzen!) und ziehen die Summe damit auseinander:

<math>\displaystyle\sum_{k=1}^{n} k \cdot k! = \sum_{k=1}^{n} (k+1) \cdot k! - \sum_{k=1}^{n} k! = \sum_{k=1}^{n} (k+1)! - \sum_{k=1}^{n} k! = \sum_{k=2}^{n+1} k! - \sum_{k=1}^{n} k!</math>

Hier kürzt sich fast alles weg. Wir erhalten:
 
<math>\displaystyle \sum_{k=1}^{n} k \cdot k! = (n+1)! - 1.</math>
 
Wir haben hierfür lediglich die allgemeinen Rechenregeln für Summen benutzt. Ein separater Induktionsbeweis wäre zwar auch möglich, aber weniger erhellend. Im Induktionsschritt verwendet man i.W. <math>(n+1)! - 1 + (n+1) (n+1)! = (n+2)! - 1</math>.

13. Potenzsummen

Wir geben zunächst eine alternative Herleitung für die Summenformel <math>\sum_{i=1}^{n} i = \frac{n(n+1)}{2}</math> an. Es gilt einerseits
 
<math>\displaystyle \sum_{i=1}^{n} (i+1)^2 = \sum_{i=1}^{n} (i^2+2i+1) = \sum_{i=1}^{n} i^2 +  2 \sum_{i=1}^{n} i + \sum_{i=1}^{n} 1 =  \sum_{i=1}^{n} i^2 +  2 \sum_{i=1}^{n} i + n,</math>

und andererseits

<math>\displaystyle \displaystyle \sum_{i=1}^{n} (i+1)^2 = \sum_{i=2}^{n+1} i^2 = \sum_{i=1}^{n} i^2 + (n+1)^2-1.</math>

Wir erkennen damit (nach Kürzen von <math>\sum_{i=1}^{n} i^2</math>)

<math>\displaystyle 2 \sum_{i=1}^{n} i + n =  (n+1)^2-1,</math>

also

<math>\displaystyle \sum_{i=1}^{n} i = \frac{(n+1)^2 - n - 1}{2} = \frac{n(n+1)}{2}.</math>
 
Genauso können wir nun, darauf aufbauend, auch eine Formel für die Summe der Quadrate <math>\sum_{i=1}^{n} i^2</math> herleiten: Einerseits ist

<math>\displaystyle \sum_{i=1}^{n} (i+1)^3 = \sum_{i=1}^{n} (i^3 + 3i^2+3i+1) = \sum_{i=1}^{n} i^3 + 3 \sum_{i=1}^{n} i^2 + 3 \sum_{i=1}^{n} i + \sum_{i=1}^{n} 1 \\ \medskip ~~~~~~~~~~~~~~ = \sum_{i=1}^{n} i^3 + 3 \sum_{i=1}^{n} i^2 + 3 \frac{n(n+1)}{2} + n,</math>
 
und andererseits

<math>\displaystyle \sum_{i=1}^{n} (i+1)^3 = \sum_{i=2}^{n+1} i^3 = \sum_{i=1}^{n} i^3 + (n+1)^3-1.</math>
 
Daraus folgt durch Umstellen:

<math>\displaystyle \sum_{i=1}^{n} i^2 = \frac{(n+1)^3-1 - 3 \frac{n(n+1)}{2} - n}{3} = \frac{n(n+1)(2n+1)}{6}.</math>
 
Völlig analog lässt sich nun auch, darauf aufbauend, <math>\sum_{i=1}^{n} i^3</math> explizit berechnen (dies sei eine Übung für den Leser). Tatsächlich lässt sich mit diesem Vorgehen die allgemeine Potenzsumme <math> \sum_{i=0}^{n} i^d</math> für beliebige Exponenten <math>d \in \mathds{N}</math> rekursiv aus den Potenzsummen <math>\sum_{i=0}^{n} i^{\ell}</math> mit <math>0 \leq \ell<d</math> berechnen (ich wähle hier <math>i=0</math> als Startindex, damit die Summe auch für <math>d=0</math> das Richtige ergibt, was sich wiederum in der Rekursionsformel für <math>\ell=0</math> niederschlägt). Siehe dazu hier. Über eine kombinatorische Herleitung habe ich hier geschrieben. Dies ist alles offenbar viel erhellender und lehrreicher, als eine - scheinbar vom Himmel gefallene - Formel für einen festen Exponenten <math>d</math> per Induktion zu beweisen.

14. Teilbarkeitsaussagen

(1) Für <math>n \in \mathds{N}</math> ist <math>7^{2n}-2^n</math> stets durch <math>47</math> teilbar. Bevor man hier reflexartig eine Induktion startet, sollte man sich einfach daran erinnern, dass aufgrund der Formel in Abschnitt 7 stets <math>a-b</math> ein Teiler von <math>a^n-b^n</math> ist. Wenden wir das auf <math>a=7^2=49</math> und <math>b=2</math> an, so sind wir sofort fertig. Dass <math>a-b</math> ein Teiler von <math>a^n-b^n</math> ist, sieht man auch daran, dass <math>a^n-b^n</math> ein Polynom in <math>a</math> mit Nullstelle <math>a=b</math> ist.

(2) Die natürliche Zahl <math>n(n+1)</math> ist stets durch <math>2</math> teilbar, d.h. gerade. Das liegt einfach daran, dass <math>\frac{n(n+1)}{2}</math> die Anzahl der <math>2</math>-elementigen Teilmengen einer Menge mit <math>n+1</math> Elementen ist (vgl. Abschnitt 6), also sicherlich eine natürliche Zahl ist. Genauso ist <math>n(n+1)(n+2)</math> stets durch <math>3</math> teilbar, etc.

(3) Genauer gesagt ist sogar immer eine der <math>m</math> Zahlen <math>n,n+1,n+2,\dotsc,n+(m-1)</math> durch <math>m</math> teilbar. Das ergibt sich aus dem Satz über die Division mit Rest:
 
Für alle <math>n,m \in \mathds{N}</math> mit <math>m > 0</math> gibt es eindeutig bestimmte <math>q,r \in \mathds{N}</math> mit <math>n = qm + r</math> und <math>r < m</math>.
 
Dies ist eine derart grundlegende Aussage über natürliche Zahlen, dass man sie wohl mit der vollständigen Induktion beweisen muss. Im Induktionsschritt nimmt man <math>n=qm+r</math> an und unterscheidet zwei Fälle: <math>r+1 < m</math> und <math>r+1=m</math>. Im ersten Fall hat man <math>n+1=qm+(r+1)</math> und ist fertig, und im zweiten Fall hat man <math>n+1=(q+1)m</math> und ist fertig. Das jedenfalls zur Existenz. Die Eindeutigkeit lässt sich direkt beweisen, also ohne Induktion.

(4) Für <math>n \in \mathds{N}</math> ist <math>11^{n+2}+12^{2n+1}</math> stets durch <math>133</math> teilbar. Auch hier muss man nicht zwangsläufig eine Induktion machen: Modulo <math>133</math> rechnet man

<math>11^{n+2} + 12^{2n+1} = 11^2 \cdot 11^n + 12 \cdot (12^2)^n \\ \medskip
~~~~~~~~~~~~~~~~~~~\,\, = 121 \cdot 11^n + 12 \cdot (144)^n \equiv -12 \cdot 11^n + 12 \cdot 11^n = 0.</math>
 
Wenn man Modulo-Arithmetik noch nicht kennt, kann man dieses Argument auch so aufschreiben:

<math>11^{n+2} + 12^{2n+1} = 121 \cdot 11^n + 12 \cdot (144)^n = 133 \cdot 11^n + 12 \cdot ((133+11)^n-11^n).</math>
 
Hier sieht man nun die Teilbarkeit durch <math>133</math>.

15. Eine Formel für die Ableitung

Sei <math>n \in \mathds{N}</math>. Die Formel für die <math>n</math>-te Ableitung des Monoms <math>x^n</math> ist bekanntlich <math>n x^{n-1}</math>. Das lässt sich per Induktion nach <math>n</math> bestätigen, wobei wir im Induktionsschritt die Produktregel benutzen:

<math>\displaystyle (x^{n+1})' = (x^n x)' = (x^n)'  x + x^n  x' = n x^{n-1} x + x^n  = n x^n + x^n = (n+1)  x^n.</math>
 
Man könnte es aber auch direkt mit der Definition der Ableitung nachrechnen:
 
<math>\displaystyle (x^n)' = \lim_{h \to 0} \frac{(x+h)^n-x^n}{h} = \lim_{h \to 0} \sum_{k=0}^{n-1} \binom{n}{k} x^k h^{n-k-1} =  \sum_{k=0}^{n-1} \binom{n}{k} x^k \lim_{h \to 0} h^{n-k-1} \\ \medskip ~~~~~~\, =  \sum_{k=0}^{n-1} \binom{n}{k} x^k \left\{\begin{array}{cc} 0 & k < n-1 \\ 1 & k=n-1 \end{array}\right. = \binom{n}{n-1} x^{n-1} = n x^{n-1}.</math>

Es gibt eine weitere Alternative: Man beweise per vollständiger Induktion die verallgemeinerte Produktregel

<math>\displaystyle (f_1 \cdot \dotsc \cdot f_n)' = \sum_{k=1}^{n} f_1 \cdot \dotsc \cdot f_{k-1} \cdot f_k' \cdot f_{k+1} \cdot \dotsc \cdot f_n.</math>

Für <math>f_1=\dotsc=f_n=x</math> ergibt sich dann <math>(x^n)' = n x^{n-1}</math>. Der Vorteil ist hier, dass wir diese verallgemeinerte Produktregel auch in anderen Situationen wiederverwerten können. Zum Beispiel können wir direkt ohne großes Nachdenken die Ableitung von <math>e^x \cdot x^2 \cdot \sin(x)</math> hinschreiben.

16. Auswahl einer Basis

Hier noch ein Beispiel, wo es meiner Einschätzung nach wirklich Sinn ergibt, eine (separate) vollständige Induktion zu verwenden: Es sei <math>V</math> ein endlich-erzeugter Vektorraum. Wir möchten zeigen, dass <math>V</math> eine Basis besitzt. Wir wählen dazu ein endliches Erzeugendensystem <math>b_1,\dotsc,b_n</math>. Wenn dieses linear unabhängig ist, sind wir fertig. Ansonsten gibt es eine nichttriviale Linearkombination. Wenn der Koeffizient vor <math>b_j</math> etwa nicht verschwindet, so sehen wir, dass <math>b_j</math> im Erzeugnis von <math>b_1,\dotsc,b_{j-1},b_{j+1},\dotsc,b_n</math> liegt. Wir haben unser Erzeugendensystem also verkürzt. Wiederholen wir dieses Verfahren, landen wir irgendwann bei einer Basis <math>b_{i_1},\dotsc,b_{i_d}</math>.
 
Ist das ein Beweis? Es wäre sicherlich besser, wenn wir mehr über dieses "irgendwann" sagen könnten. Doch zunächst verstärken wir einmal die Behauptung. Wir behaupten, dass es für jedes endliche Erzeugendensystem <math>(b_i)_{i \in I}</math> eines beliebigen Vektorraumes eine Teilmenge <math>T \subseteq I</math> gibt, sodass <math>(b_i)_{i \in T}</math> eine Basis ist. Und genau das können wir nun per vollständiger Induktion nach der Anzahl der Elemente <math>\# I</math> beweisen, wobei unser obige Beweis schon im Prinzip den Induktionsschritt beinhaltet. Der Induktionsanfang mit <math>I=\emptyset</math> ist klar. Nun sei <math>(b_i)_{i \in I}</math> ein Erzeugendensystem. Wenn es linear unabhängig ist, wählen wir <math>T=I</math> und sind fertig. Wenn nicht, gibt es ein <math>j \in I</math>, sodass sich <math>b_j</math> durch die <math>b_i</math> mit <math>i \neq j</math> linear kombinieren lässt. Es ist folglich auch <math>(b_i)_{i \in I \setminus \{j\}}</math> ein Erzeugendensystem. Nach Induktionsannahme gibt es eine Teilmenge <math>T \subseteq I \setminus \{j\}</math>, sodass <math>(b_i)_{i \in T}</math> eine Basis ist. Weil auch <math>T \subseteq I</math> gilt, sind wir fertig.

17. Zerlegung durch Geraden

In wieviele Gebiete wird die Ebene durch <math>n</math> Geraden geteilt? Offenbar hängt dies von der Lage der Geraden ab. Wenn wir zwei parallele Geraden haben, so gibt es <math>3</math> Gebiete, aber für zwei Geraden mit einem Schnittpunkt gibt es <math>4</math> Gebiete:
 
 
<math>\begin{tikzpicture}
\draw (0,0) to (2,0);
\draw (0,1) to (2,1);
\end{tikzpicture} \hspace{1cm} \begin{tikzpicture}
\draw (0,0) to (2,1);
\draw (0,1) to (2,0);
\end{tikzpicture}</math>
 
 
Es gibt offenbar mehr Gebiete, wenn sich die Geraden in sog. allgemeiner Lage befinden. Wir werden also nicht die genaue Anzahl der Gebiete bestimmen, sondern lediglich eine obere Schranke, die im Fall allgemeiner Lage auch angenommen wird. Hier einmal solche Konfigurationen von <math>3,4</math> bzw. <math>5</math> Geraden:

<math> \begin{tikzpicture}[scale=1.3]
\draw (0,0) to (2,1.5);
\draw (0,2) to (2,0.5);
\draw (0.7,0) to (0.7,2);
\end{tikzpicture} \hspace{1cm} \begin{tikzpicture}[scale=1.3]
\draw (0,0) to (2,1.5);
\draw (0,2) to (2,0.5);
\draw (0.7,0) to (0.7,2);
\draw (0,1.2) to (2,1.2);
\end{tikzpicture} \hspace{1cm} \begin{tikzpicture}[scale=1.3]
\draw (0,0) to (2,1.5);
\draw (0,2) to (2,0.5);
\draw (0.7,0) to (0.7,2);
\draw (0,1.2) to (2,1.2);
\draw (1.2,2) to (0.3,0);
\end{tikzpicture}</math>

Die bisherigen Werte sind also für <math>n=0,\dotsc,5</math> gegeben durch <math>1,2,4,7,11,16</math>. Die Differenzfolge ist <math>1,2,3,4,5</math>, und es scheint so weiterzugehen. Wir vermuten daher, dass die Anzahl der Gebiete höchstens <math>1 + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2}</math> ist. Das lässt sich nun durch vollständige Induktion bestätigen: Die <math>n+1</math>-te Gerade kann höchstens <math>n</math> Geraden schneiden und liefert bei jedem neuen Schnittpunkt ein neues Gebiet. Hinzu kommt noch das äußere Gebiet, welches sie ohnehin schon zerteilt hat. Es kommen also höchstens <math>n+1</math> neue Gebiete hinzu. Wenn es also vorher höchstens <math>1 + \frac{n(n+1)}{2}</math> waren, sind es nun höchstens <math>1 + \frac{n(n+1)}{2} + (n+1) = 1+ \frac{(n+2)(n+1)}{2}</math>, was zu zeigen war.

Ich denke, dass die vollständige Induktion hier wirklich sinnvoll gewesen ist. Man sieht beim Induktionsschritt außerdem, was passiert, wenn eine Gerade hinzukommt. Dennoch, auch hier gibt es einen sehr schönen kombinatorischen Beweis. Siehe dazu hier. Es gibt außerdem einen topologischen Beweis, der die Euler-Charakteristik der induzierten Zerlegung der Sphäre <math>S^2</math> ausnutzt. Siehe dazu hier.

18. Aufgaben

Bei den folgenden Aufgaben ist die Lösungsmethode explizit nicht vorgeschrieben. Der Leser soll selbst entscheiden, wie er vorgeht. Manchmal ist eine Induktion sinnvoll, manchmal zwar möglich, aber umständlich, und manchmal ist sie gar nicht angebracht. Im letzteren Fall helfen andere Überlegungen weiter.
 
 (1) Sei <math>n \in \mathds{N}</math>. Zeige <math>\sum_{k=1}^{n} (2k-1) = n^2</math>.

 (2) Zeige <math>\sum_{i \in I} \sum_{j \in J} a(i,j) = \sum_{(i,j) \in I \times J} a(i,j) = \sum_{j \in J} \sum_{i \in I} a(i,j),</math> wobei <math>a : I \times J \to \mathds{R}</math> eine Abbildung und <math>I,J</math> endliche Mengen sind.
 
 (3) Zeige <math>\sum_{k \geq 0} \binom{n}{2k} = 2^{n-1}</math> für <math>n \in \mathds{N}_{\geq 1}</math>.

 (4) Zeige <math>\sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n+1}{n}</math> für <math>m,n \in \mathds{N}</math>.
 
 (5) Sei <math>n \in \mathds{N}_{\geq 1}</math>. Berechne <math>\sum_{k=1}^{n} k^2 \binom{n}{k}</math>.

 (6) Sei <math>n \in \mathds{N}_{\geq 1}</math>. Berechne <math>\sum_{k=1}^{n} \frac{1}{k^2+k}</math>.

 (7) Sei <math>n \in \mathds{N}</math> und <math>U(n) = \{z \in \mathds{C} : z^n=1\}</math> die Menge der <math>n</math>-ten Einheitswurzeln. Berechne <math>\sum_{z \in U(n)} z</math>.
 
 (8) Für <math>n \in \mathds{N}_{\geq 1}</math> sei <math>\phi(n)</math> die Anzahl der zu <math>n</math> teilerfremden Zahlen im Bereich <math>\{1,\dotsc,n\}</math>. Zeige, dass für teilerfremde Zahlen <math>n,m \in \mathds{N}_{\geq 1}</math> die Gleichung <math>\phi(n \cdot m)=\phi(n) \cdot \phi(m)</math> gilt.
 
 (9) Die Fibonacci-Folge <math>(F_n)_{n \in \mathds{N}}</math> ist rekursiv durch <math>F_0=0</math>, <math>F_1=1</math> und <math>F_{n+2}=F_n + F_{n+1}</math> definiert. Zeige für <math>n,m \in \mathds{N}</math> die Gleichung <math>F_{m+n+1}=F_{n+1} F_{m+1} + F_n F_m.</math>

(10) Wieviele Diagonalen besitzt ein konvexes <math>n</math>-Eck?

Schluss

Ich habe über die Jahre in meinen Beiträgen dem Matheplaneten sehr oft auf darauf hingewiesen, dass man sogenannte "Induktionsaufgaben" auch anders angehen kann und welche Nachteile Induktionsbeweise haben. Es war also längst überfällig, diese verstreuten Beiträge zu sammeln und in Form dieses Artikels zu präsentieren. Natürlich gibt es trotzdem Aussagen, und zwar auch einfache, für deren Beweis die vollständige Induktion wie geschaffen ist. Auch diese sind in diesem Artikel nicht zu kurz gekommen. Meiner Meinung nach sollte der Fokus beim Einüben der vollständigen Induktion auf solche Aussagen gelegt werden. Dennoch, bei einer Übungsaufgabe sollte die Beweismethode niemals strikt vorgegeben werden; diese Einschränkung ist fast schon eine Art Indoktrination und besitzt langfristig gesehen keine Vorteile. Wenn in einer Aufgabe eine natürliche Zahl vorkommt, so sollten nicht nur die "Induktionsglocken" klingeln, sondern es sollte auch all das herangezogen, was man bereits zuvor bewiesen hat bzw. weiß, und damit die Aufgabe analysiert und bewältigt werden. Ich hoffe, dass euch dieser Artikel etwas meine Sichtweise näherbringen konnte. In den Kommentaren kann gerne zum Thema diskutiert werden.
 
Ich bedanke mich bei meinen Korrekturlesern tactac und weird.


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Vollständige Indoktrination [von Martin_Infinite]  
Die vollständige Induktion steht im ersten Semester auf dem Lehrplan und wird mit vielen einfachen Aufgaben eingeübt. Das hat oftmals zur Folge, dass Studienanfänger alles, wo eine natürliche Zahl vorkommt, mittels vollständiger Induktion beweisen möchten, oder sogar bewei
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 2555
 
Aufrufstatistik des Artikels
Insgesamt 26 externe Besuche zwischen 2017.04 und 2017.04 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com2388.5%88.5 %
http://google.de27.7%7.7 %
http://www.bing.com13.8%3.8 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 22 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.04.25 13:44viewtopic.php?topic=223542&ref=https://www.google.de/&ff=y
2017.04.25 01:07http://google.de/url?sa=t&rct=j&q=
2017.04.19-2017.04.23 (20x)https://www.google.de/

[Seitenanfang]

" Stern Mathematik: Vollständige Indoktrination" | 21 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Vollständige Indoktrination
von freeclimb am Mi. 23. März 2016 21:58:20


Hallo, sehr schöner Artikel! Vielen Dank dafür, ein kleiner Tipsler ist mir aufgefallen. In der Zeile

<math>\displaystyle 2^{n+1}= 2^n \cdot 2 \geq n^2 = n^2 + n^2,</math>

fehlt eine 2.

mfg

 [Bearbeiten]

Re: Vollständige Indoktrination
von Slash am Do. 24. März 2016 00:49:31


Ich habe jetzt erst gemerkt, dass der Titel "Vollständige Indoktrination" und nicht "Vollständige Induktion" lautet. Dabei habe ich den Titel mehrfach in den letzten Stunden gelesen (bzw. falsch gelesen). Tja, die Macht der Gewohnheit. wink

 [Bearbeiten]

Re: Vollständige Indoktrination
von xiao_shi_tou_ am Do. 24. März 2016 11:53:00


Wie immer, ein sehr schöner Artikel.

Ich hab mich als Schüler immer über Beweise geärgert, die "vom Himmel fallen",
vor allem Induktionsbeweise bei denen man genauso schlau ist nachdem man sie gemacht hat wie davor.
Schön, das Thema mal aus der Sicht eines Profis präsentiert zu bekommen.

Nachdem nun Nickel P. und Martin endliche Summen auf eine wackelfreie Basis gestellt haben,
sollte - zumindest hier auf dem MP - eigentlich niemand mehr daran zweifeln,
dass Beweise durch "direktes Umformen" formal genauso korrekt sind wie Beweise durch vollständige Indoktrination.

In der analytischen Zahlentheorie werden endliche Summen ja öfters
mal "intuitiv" umgeformt, z.B.
fed-Code einblenden
wobei natürlich der Autor die Begründung für die formale Korrektheit kennt.

Nun gibt es auch kompliziertere Induktionsbeweise.
Z.B. findet man in dem Buch "Drei Perlen der Zahlentheorie" von A.Chintschin einen induktiven Beweis von einer Mathematikerin namens Lukomskaja
für den Satz von Van der Waerden.

Kennt jemand einen weiteren Beweis für diesen Satz?
Ist es hier angebracht Induktion zu verwenden? Ich kenne mich mit dem Thema leider zu wenig aus, um das zu beurteilen.

lg Daniel.

 [Bearbeiten]

Re: Vollständige Indoktrination
von salomeMe am Do. 24. März 2016 12:16:14


Hi Martin_Infinite,

habe eben Deinen Artikel begonnen zu lesen. Vor knapp 50 Jahren war, falls ich mich recht erinnere, das Prinzip der Vollständige Induktion grundlegend anders vermittelt worden:

1. P(0) bzw. P(1) musste gezeigt und nicht angenommen werden. [Bestimmt kann man die Vollständige Induktion auch problembezogen, bei einer bestimmten natürlichen Zahl beginnen lassen, falls das Behauptete vorher nicht gilt.]
Ich hatte mal ein Heftchen über Fehler in mathematischen Beweisen gelesen, das einen ansonsten richtigen Induktionsbeweis enthielt, der zu einem falschen Ergebnis führte, weil die Eigenschaft nicht nur für ein bestimmtes n, sondern auch für das kleinste n angenommen wurde.

2. An etwas Unwichtiges kann ich mich auch noch erinnern: man hat immer von k auf k+1 geschlossen (wenn es für alle n zu beweisen war), wahrscheinlich aus didaktischen oder philosophischen Gründen - ich fand und finde das gut und mache es deshalb auch heute noch so.

Vielleicht liege ich ja falsch mit meinen Erinnerungen, aber falls nicht, sollte der Einstieg in Deinen Artikel leicht korrigiert werden.

Lass Dich bitte durch diesen Kommentar nicht ärgern - ich bin beeindruckt vom der Zahl und den Umfängen Deiner Veröffentlichungen sowie Deinen sonstigen Aktivitäten auf dem MP.

Beste Grüße
salomeMe

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Do. 24. März 2016 17:17:06


@freeclimb: Danke, ist korrigiert.
 
@Slash: Das war mein Plan.

@xiao_shi_tou_: Meinst du diesen Satz? Hier scheint eine vollständige Induktion sehr sinnvoll zu sein. Genau wie beim Satz von Ramsey. Aber ich bin auch kein Experte. Was alternative Beweise angeht, würde ich mal schauen, ob die von Timothy Gowers gefundene obere Schranke ein direkter Beweis für die Endlichkeit von <math>N(r,l)</math> ist.

@salomeMe: 1) Du hast meine Formulierung falsch verstanden. Das Prinzip der vollständigen Induktion ist ja eine Meta-Aussage der Form

Induktionsanfang + Induktionsschritt ==> Aussage.
 
Wenn ich die Aussage A ==> B formulieren möchte, dann kann ich das so machen: Wenn wir A annehmen, dann gilt B. Aber natürlich muss man dann trotzdem A beweisen, wenn man damit B beweisen möchte. Also: Unter der Annahme bzw. Voraussetzung, dass P(0) gilt und P(n) => P(n+1) für alle n gilt, gilt auch P(n) für alle n. Wenn man also P(n) für alle n zeigen will, zeigt man im Rahmen einer vollständigen Induktion P(0) und P(n) => P(n+1) für alle n, wobei letzteres bedeutet, dass man P(n) annimmt und daraus P(n+1) folgert. Natürlich gilt P(0) nicht automatisch.
 
2) Eine Umbenennung der Variable ist unnötig (und offenbart eigentlich sogar eine falsche Konzeption von Variablen) und ziemlich unpraktisch, wenn im Kontext bereits andere Variablen verbraucht sind.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Fr. 25. März 2016 09:17:10


Hier noch eine wirklich schöne und elementare Aussage, bei der man die vollständige Induktion gut einüben kann und zudem auch noch etwas geometrisches Verständnis lernen kann:
 
Sei <math>G</math> ein ebener zusammenhängender Graph mit <math>V</math> Knoten, <math>E</math> Kanten und <math>F</math> Gebieten (das unbeschränkte Gebiet eingeschlossen). Dann gilt die Eulersche Formel <math>V-E+F = 2</math>.

Beweis per Induktion nach <math>E</math>: Für <math>E=0</math> gilt offenbar <math>V=F=1</math> und die Aussage ist klar. Für <math>E>0</math> wählen wir eine Kante <math>e</math> aus. Wenn <math>e</math> keine Schleife ist, ziehen wir <math>e</math> zu einem Punkt zusammen:
 
<math>\begin{tikzpicture}[scale=0.5]
\draw (0,0) to (2,0) to (2,2) to [out=150,in=135] (0,0);
\draw (0,0) to (2,2);
\draw (2,2) to (4,1) to (2,0);
\draw (4,1) to [out=-45,in=-90] (5.5,1) to [out=90,in=45] (4,1);
\draw node at (2.3,1) {\scriptsize $e$};
\fill (0,0) circle (3pt);
\fill (2,0) circle (3pt);
\fill (2,2) circle (3pt);
\fill (4,1) circle (3pt);
\end{tikzpicture} \hspace{1cm}
\begin{tikzpicture}[scale=0.5]
\draw (0,0) to [out=0,in=-90] (2,2) to [out=150,in=135] (0,0);
\draw (0,0) to (2,2);
\draw (2,2) to (4,1) [out=225,in=-80] to (2,2);
\draw (4,1) to [out=-45,in=-90] (5.5,1) to [out=90,in=45] (4,1);
\fill (0,0) circle (3pt);
\fill (2,2) circle (3pt);
\fill (4,1) circle (3pt);
\end{tikzpicture}</math>
 
Das hinterlässt einen neuen ebenen zusammenhängenden Graphen mit <math>V-1</math> Knoten, <math>E-1</math> Kanten und <math>F</math> Gebieten. Nach Induktionsvoraussetzung gilt <math>(V-1)-(E-1)+F=2</math> und damit <math>V-E+F=2</math>. Wenn hingegen <math>e</math> eine Schleife ist, trennt <math>e</math> zwei Gebiete (auch wenn das anschaulich klar ist, müsste man es streng genommen noch beweisen). Entfernen wir nun <math>e</math>, so erhalten wir einen ebenen zusammenhängenden Graphen mit <math>V</math> Knoten, <math>E-1</math> Kanten und <math>F-1</math> Gebieten. Nach Induktionsvoraussetzung gilt <math>V-(E-1)+(F-1)=2</math> und damit <math>V-E+F=2</math>. QED
 
Auch hier gibt es sehr viele weitere Beweise (auch solche ohne Induktion). The Geometry Junkyard listet gleich 20 davon auf.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Gerhardus am Fr. 25. März 2016 12:36:32


Zur Nachhilfe hatte ich mal einen Studenten fürs Lehramt, für den war die vollständige Induktion (VI) ein rotes Tuch; er hat trotzdem das 1. Staatsexamen geschafft.
Vermutlich hatte er ein Problem mit Termumformungen; denn wer die nicht versteht, scheitert auch mit dem VI-Beweis. Wichtig dabei ist die Erfahrung, dass komplizierte Terme identisch sind mit einfachen. Da in der modernen Schule Formeln mit dem modernen Gedächtsnistraining gelernt werden, sind dafür Termumformungen nicht mehr erforderlich und dementsprechend uninteressant, um nicht zu sagen lästig. Dabei sind Termumformungen oft gut für Verblüffendes.
Spezielle endliche Reihen haben die Form:
(endliche Reihe)       f(1) + f(2) + … f(n) = S(n),
wobei f und S oft Polynome sind.
Für den Beweis zeigt man den Induktionsanfang  f(1) = S(1) und
den Induktionsschluss  S(n-1) + f(n) = S(n).
Beim Induktionsschluss geht es oft um Termumformungen. Der Dozent vergleicht beide Terme mit ein paar geschickten Tricks und schon denkt der arme Student, diese eleganten Tricks seien der Kern des VI-Beweises. Welch ein Irrtum! Man kann die Terme z.B. auf beiden Seiten stur in formale Polynome auflösen, um dann die Monome zu vergleichen.
Vielleicht sollte man mal das Pferd von hinten aufzäumen:
Man nehme ein beliebiges Polynom P(n) ≠ 0 (n ist Argument, nicht Exponent), multipliziere es mit n, d.h. S(n) = n∙P(n). Damit ist S(0) = 0 und der Induktionsanfang feritg.
Jetzt kommt die Termumformung f(n) = S(n) - S(n-1), die möglichst einfach ausfallen sollte, und fertig ist eine spezielle endliche Reihe (s.o.), die man, wenn man Muße hat, mit der VI beweisen kann, aber es steht ja schon alles da.
Nebenbei bemerkt: Wem in der Gauß'schen Summenformel S(n) = n(n+1)/2 auffällt, dass S(n-1) + S(n) = n², der erkennt sogleich, dass [S(n)]² die Summe der Kuben Σk³ (1 ≤ k ≤ n) ist, weil  f(n) = [S(n)]² - [S(n-1)]²  = [S(n) - S(n-1)]∙[S(n) + S(n-1)] = n³.
 

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Fr. 25. März 2016 17:10:35


@Gerhardus

Was du in

>Jetzt kommt die Termumformung f(n) = S(n) - S(n-1), die möglichst einfach ausfallen sollte, und fertig ist eine spezielle endliche Reihe (s.o.), die man, wenn man Muße hat, mit der VI beweisen kann, aber es steht ja schon alles da.<

beschreibst, ist eigentlich nur eine Anwendung des berühmt-berüchtigten "Teleskoptricks", da durch Einsetzen der Darstellung

f(n)=S(n)-S(n-1)

aus der ursprünglichen Summe

f(1)+f(2)+...+f(n)

in Verbindung mit S(0)=0 eine Teleskopsumme wird. Die Induktion wird dabei aber nicht gänzlich überflüssig, wie man vielleicht beim Lesen des oben Zitierten glauben könnte, man braucht sie streng genommen, um den "Teleskoptrick" selbst formal sauber beweisen zu können, auch wenn man das üblicherweise nicht macht, weil "es ja eh anschaulich klar ist".

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Fr. 25. März 2016 17:32:21


Die Gleichung S(n-1) + f(n) = S(n) ist nichts weiter als die (auch im Artikel genannte) Definition(!) von S(n).

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Sa. 26. März 2016 07:27:22


@Martin

Natürlich ist es richtig, dass <math>S(n)</math> bei gegebenem <math>f(n)</math> durch die Gleichungen

<math>S(0)=0,\quad S(n-1)+f(n) = S(n)</math>

bereits eindeutig festgelegt ist, nämlich als

<math>S(n)=\sum\limits_{k=1}^n f(k)</math>

aber Gerhardus verwendet diese Tatsache ja gerade, wenn ich ihn richtig verstanden habe, indem er obige Funktionalgleichung für <math>S(n)</math> auf andere Weise löst - oder einfach nur eine vorgegebene Lösung auf Korrektheit überprüft - um durch Gleichsetzung der beiden Lösungen eine Formel für obige Summe zu erhalten.

Man könnte beispielsweise für <math>f(n)=n^2</math> den allgemeinen Ansatz

<math>S(n)=a_3 n^3+a_2 n^2+ a_1 n</math>

machen (wobei ich hier <math>S(0)=0</math> schon habe einfließen lassen!), um dann aus

<math>f(n)=S(n)-S(n-1)</math>

durch Einsetzen und Koeffizientenvergleich

<math>a_3=\frac13,\ a_2=\frac12, \ a_1=\frac16</math>

zu gewinnen, womit man tatsächlich

<math>\sum\limits_{k=1}^n k^2=\frac{n^3}3+\frac{n^2}2+\frac{n}6</math>

bewiesen hat.

Ich sehe also schon, dass der Ansatz von Gerhardus eine etwas andere - und im Rahmen dieses Artikels, wo es ja nicht zuletzt um Alternativen zu den üblichen Induktionsbeweisen geht - durchaus wertvolle  Sicht der Dinge beinhaltet.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Sa. 26. März 2016 08:52:33


Achso. Das ist nur ein vollständiger Beweis, wenn der Ansatz als korrekt erwiesen ist (z.B. mit der rekursiven Charakterisierung von Polynomfolgen vom Grad <math>d</math> durch Differenzfolgen). Ein Ansatz kann theoretisch zu einer eindeutigen Lösung führen, die aber durchaus falsch sein kann, wenn der Ansatz nämlich falsch war.
 
Davon abgesehen gibt es nicht immer die Möglichkeit, eine Gleichung der Form <math>\sum_{k=1}^{n} f(k) = S(n)</math> direkt per Induktion zu zeigen, nämlich wenn <math>f(k)</math> eigentlich auch noch von <math>n</math> abhängt. Ein schönes Beispiel ist <math>\sum_{k \geq 0} \binom{n}{2k} = 2^{n-1}</math> für <math>n \geq 1</math>. Der Vorschlag von Gerhardus bezieht sich eigentlich nur auf Potenzsummen, und da gibt es ja viele allgemeine Methoden (eine wurde im Artikel genannt).

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Sa. 26. März 2016 11:28:00


Im konkreten Beispiel <math>f(n)=n^2</math> war der Ansatz

<math>S(n)=a_3n^3+a_2n^2+a_1n</math>

sicherlich korrekt, denn wie die Rechnung zeigt, gilt ja dann tatsächlich

<math>f(n)=S(n)-S(n-1)</math>

was in Verbindung mit <math>S(0)=0</math> aus der Summe

<math>\sum\limits_{k=1}^n f(n)</math>

durch Einsetzen eine Teleskopsumme mit Wert <math>S(n)</math> macht. Auch im allgemeineren Fall

<math>f(n)=n^m\quad (m \in \mathbb N)</math>

kann der analoge Ansatz

<math>S(n)=\sum\limits_{k=1}^{m+1} a_k n^k \quad (a_k \in \mathbb Q)</math>

nirgendwo zu Problemen führen, da in

<math>S(n)-S(n-1)=\sum\limits_{k=1}^{m+1}a_k\left(\sum\limits_{j=0}^{k-1}(-1)^{j+1}\binom kj n^j\right)=n^m</math>

jedes <math>a_k</math> mit dem von 0 verschiedenen Koeffizienten <math>k</math> auftritt, d.h., in eindeutiger Weise berechenbar ist, wenn man die Koeffizienten <math>a_j</math> mit <math>j>k</math> bereits kennt.

Und ja, die Beispiele, welche Gerhardus gab, bezogen sich jetzt zwar "nur" auf Potenzsummen, was aber nicht heißt, dass dieses Konzept nur für diese anwendbar wäre, sondern allgemein überall dort, wo die Funktionalgleichung

<math>S(0)=0, \quad S(n)-S(n-1)=f(n) \ (n>0)</math>

noch auf eine andere Art als die "triviale"

<math>S(n)=\sum\limits_{k=1}^n f(k)</math>

lösbar ist, wie z.B. für <math>f(k)=\sin(kx)</math>. Wie dieses Beispiel noch zeigt, kann <math>f(k)</math> dabei auch ruhig noch von anderen Variablen abhängen, solange nicht ausgerechnet die Summationsvariable <math>n</math> darunter ist.  wink


 [Bearbeiten]

Re: Vollständige Indoktrination
von Gerhardus am Mo. 28. März 2016 23:26:37


Mein Kommentar begann mit dem Problem, das Anfänger mit der vollständigen Induktion (VI) haben. Warum fällt ihnen das so schwer? Das ist ein Problem der Didaktik, wenn sie um das Problem zu viel drum herum redet, anstatt sich auf das Wesentliche zu beschränken. Dieses Problem habe ich, wenn ich Anfängern den VI-Beweis vermitteln soll.
Der Artikel handelt nur von der Alternative VI und anderer Beweis. Aber an wen soll sich so ein Artikel richten? Soll er nur deutlich machen, dass man Beweise auch anders führen kann? Nur an die, die den VI-Beweis bereits beherrschen und jetzt auf ihn fixiert sind?
Der Anfänger wird vermutlich über den Begriff Abspaltungsregel stolpern. Ich könnte antworten, diese Regel ist eine mit der VI beweisbare Verallgemeinerung des elementaren Assoziativgesetzes. Im Grunde ist ja alles klar. Der Rest ist Spielerei.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Kitaktus am Mi. 06. April 2016 13:07:19


Ich bin über den Satz gestolpert: "Das hat oftmals zur Folge, dass Studienanfänger alles, wo eine natürliche Zahl vorkommt, mittels vollständiger Induktion beweisen möchten, oder sogar beweisen sollen."

Ich weiß nicht, wie stark in Deinem Umfeld die Vollständige Induktion thematisiert wird, dass Du schon zum Begriff "Indoktrination" greifst.
Ich sehe das etwas entspannter.

In den entsprechenden Fäden wundere ich mich regelmäßig, warum man ausgiebig alternative Lösungswege vorschlägt und beschreibt, wenn der Beweis mit Induktion geführt werden _soll_. Das ist für mich so, als würde man jemanden, der Ausdauerlauf trainiert, vorschlagen, seine Trainingsstrecke mit dem Bus zurückzulegen, das ginge schneller und man hätte auch mehr Muße, die Landschaft zu genießen.
Ein großer Teil der Induktions-Übungsaufgaben wird gestellt, um die Technik zu üben!

Das insbesondere unerfahrenere Schüler und Studenten dazu neigen Induktion häufiger verwenden zu wollen, als es sinnvoll wäre, deckt sich mit meinen Erfahrungen. Ich denke das hängt mit der Unsicherheit zusammen, welche Techniken als "wasserdicht" gelten und welche nicht.
Da die Induktion i.d.R. explizit als Beweistechnik behandelt wird, wird sie als "auf jeden Fall akzeptiertes Werkzeug" wahrgenommen. Bei anderen Techniken, die oftmals intuitiver und weniger formal sind, besteht dagegen die Unsicherheit "darf man das so machen?"
Nicht zu Letzt wird das gespeist von der Erfahrung, das viele intuitive "Beweis"techniken der Schüler/Studenten von Lehrern/Übungsleitern/Dozenten vehement zurückgewiesen werden. Wie oft ist allein in diesem Forum der Satz gefallen "_So_ kann man das nicht beweisen!"

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Do. 07. April 2016 10:09:08


Es ist der Sache vielleicht dienlich, wenn man zwischen drei Typen von Aufgaben unterscheidet, die man mit vollständiger Induktion lösen kann.

1.Typ: Aufgaben, bei denen es darum geht, das Prinzip der vollständigen Induktion überhaupt erst einzuüben, weshalb auch dann tatsächlich nur eine Lösung mit Vollständiger Induktion Sinn macht.

2.Typ: Aufgaben nicht vom Typ 1, bei denen der Aufgabensteller vorgibt, dass sie mit vollständiger Induktion gelöst werden sollten, eine Einschränkung, die manchmal fragwürdig ist.

3.Typ: Aufgaben nicht vom Typ 1 oder 2, wo der Student gewissermaßen automatisch davon ausgeht, dass nur ein Beweis mit vollständiger Induktion in Frage kommt.

Ich denke, es geht Martin in erster Linie um diese unglückselige Fixierung der Studenten bei Aufgaben vom Typ 3. Kitaktus hat oben sehr plausible Gründe dafür angebenen, wodurch sie zustande kommt, trotzdem handelt es sich dabei natürlich um eine Fehlhaltung, welche man am besten durch das Aufzeigen von attraktiven Beweisvarianten bekämpfen kann, wie es in dem Artikel auch gemacht wird.

Von "Indokrination" kann man allerdings, soweit es Martin dabei um mehr als ein bloßes Wortspiel geht, nur bei Aufgaben vom Typ 2 sprechen und auch das ist das Wort "Induktion" oft nur in einem Hinweis versteckt, der eigentlich den Studenten auf den angeblich "richtigen" Weg führen sollte. Diesen sollte man dann vielleicht in vielen Fällen so umformulieren, dass der Beweis durch vollständige Induktion nur eine Option darstellt, oder ihn überhaupt weglassen.

Und ja, was ich selber durch die Diskussion hier gelernt habe, dass man für eine in der Schule sehr beliebte Klasse von Induktionsaufgaben, nämlich der Auffindung einer Summenformel

f(1)+f(2)+...+f(n)

wo f irgendeine Funktion darstellt, für welche obiger Ausdruck Sinn macht, nur versuchen muss, die Funktionalgleichung

S(0)=0, f(n)=S(n)-S(n-1) (n>0)

für S(n) zu lösen, was eine Art "diskrete Integration" darstellt, den Rest erledigt dann der "Teleskoptrick". Rein rechnerisch läuft das meist auf das Gleiche hinaus, wie der Schritt von n-1 auf n in einem Induktionsbeweis, zumindestens wenn die Formel für S(n) bereits vorgegeben ist, aus logischer Sicht ist das aber etwas ganz anderes: Die Induktion braucht man dafür nun tatsächlich nicht mehr, sie wurde in den Beweis des "Teleskoptricks" hinein verlagert (oder auch "outgesourced", wie man heutzutage sagt).

 [Bearbeiten]

Re: Vollständige Indoktrination
von lula am Fr. 08. April 2016 13:56:12


Der Artikel spricht mir aus dem Herzen, Es sind gute Bsp. für unnötige Industionsbeweise. , schön wäre es, wenn jetzt für zukünftige Fragen, bei denen unnötig Induktion angewandt werden soll, hier als link auftauchten.
danke Infinit
Gruß Lula

 [Bearbeiten]

Re: Vollständige Indoktrination
von DerEinfaeltige am Fr. 08. April 2016 19:45:53


Ich spiele mal den Advocatus Diaboli und möchte eine Lanze für die vollständige Induktion brechen.

Die VI ist schlichtweg das Beweismittel für Algorithmen und Programme. Um zeigen zu können, dass ein bestimmter Algorithmus funktioniert, ist das Training des Induktionsschemas

- Variante(n)?
- Invarianten?
- Terminierung?

unersetzlich und sollte dementsprechend selbst im Schlaf beherrscht werden.

Erst dann sollte man sich mit eleganteren(?) Beweismethoden beschäftigen.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Fr. 08. April 2016 20:05:36


@DerEinfaeltige: Hast du dir den Artikel angeschaut? Nirgendwo habe ich behauptet, dass Induktion immer das unterliegende Beweismittel ist. Und manchmal ist sie sogar das einzige Beweismittel. Der Artikel ist voll mit Beispielen dafür.

@weird: Wie gesagt, ist S(0)=0, f(n)=S(n)-S(n-1) nur die Definition von S(n). Das hat nichts mit Induktion zu tun.

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Sa. 09. April 2016 00:35:57


@MI

Ja, beide deine Aussagen kann ich voll unterschreiben, nur sehe ich nicht, wo sich das Ganze für dich "spießt". Für mich ist ja auch S(n) die eindeutige Lösung der Funktionalgleichung

S(0)=0, f(n)=S(n)-S(n-1)

d.h., man kann das als Definition von S(n) ansehen. Darauf baut ja gerade die Idee auf, dass wenn ich für S(n) eine Formel habe, die "passt" (sei es, dass sie gegeben ist, wie dies bei einem Induktionsbeweis typischerweise der Fall ist, sei es, dass ich sie erst finden muss, wie ich das oben am Beispiel f(n)=n² genauer ausgeführt habe), so kann ich sicher sein, dass sie mit der "trivialen" Lösung

S(n)=f(1)+f(2)+...+f(n)

übereinstimmt. Und ja, dass das noch "nichts mit Induktion zu tun hat" ist ja auch gerade das, was ich die ganze Zeit behaupte, sondern die Induktion kommt wie gesagt erst anschließend beim "Teleskoptrick" ins Spiel, aber auch nur, falls jemand das Bedürfnis hat, diesen streng formal beweisen zu wollen. Irgendwie reden wir also leider die ganze Zeit aneinander vorbei.

 [Bearbeiten]

Re: Vollständige Indoktrination
von Martin_Infinite am Sa. 09. April 2016 01:54:08


Man braucht keinen Teleskoptrick.

 [Bearbeiten]

Re: Vollständige Indoktrination
von weird am Sa. 09. April 2016 08:19:14


>Man braucht keinen Teleskoptrick.<

Auch das ist natürlich richtig. Der Teleskoptrick ist ja auch nur ein alternativer Weg, um zu zeigen, dass aus

S(0)=0, f(n)=S(n)-S(n-1)

tatsächlich

S(n)=f(1)+f(2)+...+f(n)

also dann diese eindeutige Summendarstellung von S(n) folgt.

Und ja, ich weiß schon, du wirst jetzt wieder sagen, das kann man ja auch viel einfacher sehen, nämlich so und so... Darum also hier vorweg: Auch das ist natürlich richtig, nur führt das wieder zum klassischen Induktionsschema, von dem ich gerade wegkommen wollte. Wir drehen uns also hier im Kreis.

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]