Anwendungsaufgaben zur Vollständigen Induktion

A:                Behauptung: Es gibt unendlich viele Primzahlen

Der geforderte Beweis wird oft durch Widerspruch geführt. Ich will das zunächst auch tun. Als zweiten Beweis gebe ich dann noch den durch vollst. Induktion. Man wird sehen, dass der Widerspruchsbeweis umständlicher ist. Es wird nämlich der Widerspruch genau mit der konstruktiven Idee für die vollst. Induktion erzeugt.

Wenn es wirklich unendlich viele Primzahlen gibt, kann man sicher nicht alle Primzahlen aufschreiben. Aber man kann die Möglichkeit prüfen, dass es nur endlich viele Primzahlen gibt und diese Möglichkeit konsequent weiter denken. Am Ende dieser Überlegung wird man feststellen, dass etwas nicht stimmt. Und wenn ein aufgrund logischer Gesetze entstandenes Endergebnis offensichtlich nicht wahr sein kann, ist erwiesen, dass auch die am Anfang getroffene Annahme nicht wahr sein kann. Aus etwas richtigem kann nach der mathematischen Logik niemals etwas falsches folgen. Diese Beweistechnik nennt man einen Widerspruchsbeweis.

Angenommen es gäbe nur endlich viele Primzahlen p₁,.,p_n.
Dann betrachte die Zahl p=p₁**p_n+1, welche offensichtlich durch keines der p_i, i=1,,n teilbar ist. Dann muss p, welches ja von allen p_i verschieden ist, offensichtlich eine Primzahl sein.
Das ist ein Widerspruch zur Annahme.
Also war die Annahme falsch, es muss demnach unendlich viele Primzahlen geben.

Der Beweis enthält eine konstruktive Idee, wie man aus den ersten n Primzahlen eine weitere Zahl konstruieren kann, durch die man die Existenz einer weiteren, der (n+1)-ten Primzahl, nachweisen kann .
Anstatt einen Beweis durch Widerspruch zu führen, hätte man auch den direkten Beweis führen können. Der geht dann so:

Es seien die ersten n Primzahlen bekannt. Dann betrachte Zahl q = p₁**p_n+1, welche offensichtlich durch keines der p_i, i=1,,n teilbar ist.

Wir wissen nicht, ob q eine Primzahl ist, darum betrachten wir jetzt beide Möglichkeiten.
Fall 1: q ist eine Primzahl. Dann haben wir eine weitere Primzahl gefunden.
Fall 2: q ist keine Primzahl. Dann gibt es einen echten Teiler von q. (Ein echter Teiler ist weder die 1 noch q selbst).
Diese Teiler ist nach Konstruktion von q keine der Primzahlen p₁, , p_n. Es muss demnach eine weitere Primzahl geben, die q teilt. Diese 'andere' Primzahl ist größer als p_n. Ich nenne diese neue Primzahl p^*. p^* ist nicht notwendigerweise die n+1 -te Primzahl (es kann zwischen der größten Primzahl unter den ersten n Primzahlen und der neuen Primzahl noch andere Primzahlen geben), aber aus der Existenz von n Primzahlen folgt die Existenz von mindestens n+1 Primzahlen. Diese Art zu schließen ist die vollständige Induktion. Als Induktionsanfang genügt die Existenz einer Primzahl. Ausgehend von p₁=2 weist man so die Existenz einer weiteren Primzahl nach.

Wer sich nun fragt, ob denn q nicht immer eine Primzahl ist, dem gebe ich ein Gegenbeispiel:
2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 ist keine Primzahl, denn 30031 = 59 * 509.

Im Induktionsschritt muss man deshalb vorsichtig sein.
Aus den ersten n Primzahlen p₁,.,p_n ergibt sich die Existenz einer weiteren. Wie diese neue Primzahl aber lautet, sagt der Beweis nicht.
Und die Primzahl p^* ist nicht notwendig die (n+1)-te Primzahl. Aber wenn es bis zu p^* mehr als n+1 Primzahlen gibt, dann ist das ja auch genug. Man sucht dann aus den mehr als n+1 Primzahlen die ersten n+1 heraus und kann damit den Induktionsschritt von n+1 auf n+2 durchführen.

Quelle:http://www.univie.ac.at/future.media/mo/materialien/matroid/files/vi/vi.html

Wie oft klingt es, wenn n Personen mit Gläsern anstoßen?

  (n-1) und   n ausmultipliziert ergibt :.

Wenn n Personen anstoßen klingt es also mal.

a=

1.Induktionsanfang

n= 2

a(2)=

a2)= 1

Bei zwei Personen klingt es ein mal, ist also richtig.

Die Aussage A ist für n= 2 wahr.

2.Induktionsvoraussetzung

Die Aussage A sei für n= k wahr, d.h. es gelte :a(k)=.

3.Induktionsbehauptung

Die Aussage A ist dann auch für den Nachfolger n=k+1 wahr das es gilt : a(k+1)= .

4.Induktionsschritt

a(k)=

Bei k+1 Personen kommen k Klänge dazu (bei 8 Personen kamen 7 Klänge dazu.).

a(k+1)=  +k

a(k+1)=  +

a(k+1)=

5.Induktionsschluss

Die Aussage A ist für n= 2 wahr. Aus der aus der angenommenen Gültigkeit der Aussage A für n= k, habe ich auf die Gültigkeit der Aussage A für n= k+1 geschlossen. Damit habe ich die Gültigkeit der Aussage A für alle natürlichen Zahlen n nachgewiesen.

Quelle: http://www.keilbach.onlinehome.de/schueler/mathe/m12/m12_indukt.html

Nebenstehender Rechenausdruck Leonard Eulers

  p= n² - n + 41

  liefert nacheinander Primzahlen ab 41. Gilt der Ausdruck für alle n ?

Lösung:

Wenn n= 41 ist, dann wird (-n+41) gleich null und es bleibt die Gleichung p= n² übrig. Da n² immer durch n teilbar ist, da n² durch n gleich n ist, gilt der Ausdruck für alle für alle n N

Quelle:http://ig.cs.tu-berlin.de/~gymstegl/math_onl/ma_profil/klausur2_profil.htm