"Seht Euch doch diesen Mathematiker an", sagt der Logiker, "er bemerkt, dass die ersten neunundneunzig Zahlen kleiner als hundert sind und schließt daraus auf Grund von etwas, das er Induktion nennt, dass alle Zahlen kleiner als hundert sind.""Ein Physiker glaubt", sagt der Mathematiker, "das 60 durch alle Zahlen teilbar ist. Er bemerkt, dass 60 durch 1, 2, 3, 4, 5 und 6 teilbar ist. Er untersucht noch ein paar Fälle wie 10, 20 und 30, die, wie er sagt, aufs Geratewohl herausgegriffen sind. Da 60 auch durch diese teilbar ist, betrachtet er seine Vermutung als hinreichend durch den experimentellen Befund bestätigt."
"Ja, aber seht Euch doch die Ingenieure an", sagt der Physiker. "Ein Ingenieur hatte den Verdacht, dass alle ungeraden Zahlen Primzahlen sind. Jedenfalls, so argumentiert er, kann 1 als Primzahl betrachtet werden. Dann kommen 3, 5 und 7, alle zweifellos Primzahlen. Dann kommt 9; ein peinlicher Fall, wir scheinen hier keine Primzahl zu haben. Aber 11 und 13 sind unbestreitbar Primzahlen. 'Auf die 9 zurückkommend', sagt er, 'schließe ich, dass 9 ein Fehler im Experiment sein muss.'"
Es liegt nur allzu sehr auf der Hand, dass Induktion zum Irrtum führen kann. Um so bemerkenswerter ist es, da die Irrtumswahrscheinlichkeiten so überwältigend erscheinen, dass Induktion manchmal zur Wahrheit führt.
[Mathematik-Folklore]
Die vollständige Induktion ist eine der 3 grundlegenden mathematischen Beweistechniken - neben 'direkt' und 'indirekt durch Widerspruch'. Um eine Beweistechnik als Mittel der korrekten logischen Argumentation zu akzeptieren, muss man diese Technik verstanden haben. Das Prinzip der vollständigen Induktion ist immerhin schon so komplex, dass es Gegenstand von Witzen sein kann.
In einem Beitrag der TU Freiberg steht
Der erste Mathematiker, der einen formalen Beweis durch vollständige Induktion angab, war der italienische Geistliche Franciscus Maurolicus (16.9.1494 - 21./22.7.1575). Er war Abt von Messina und wurde als größter Geometer des 16. Jahrhunderts angesehen. In seinem 1575 veröffentlichten Buch Arithmetik benutzte Maurolicus die vollständige Induktion unter anderem dazu, für jede positive ganze Zahl n die Gültigkeit vonÜbrigens das Gegenteil von Induktion ist die Deduktion, bei der man vom Allgemeinen auf das Einzelne schließt. Beispiel: Alle Menschen haben einen Kopf. Peter ist ein Mensch. Folgerung: Peter hat einen Kopf. Aber darum soll es weiter nicht gehen.- 1 + 3 + 5 + ... + (2n-1)=n*n
zu beweisen. Die Induktionsbeweise von Maurolicus waren in einem knappen Stil geschrieben, dem man nur schwer folgen kann. Eine bessere Darstellung dieser Methode wurde von dem französischen Mathematiker Blaise Pascal (1623 - 1662) angegeben. In seinem 1662 erschienen Buch Traite du Triangle Arithmetique bewies er eine Formel über die Summe von Binomialkoeffizienten mittels vollständiger Induktion. Er benutzte diese Formel dann um das heute nach ihm benannte Pascalsche Dreieck zu entwickeln.
Obwohl die Methode der vollständigen Induktion also bereits 1575 bekannt war, wurde der Name dafür erst 1838 erstmalig gebraucht. In jenem Jahr veröffentlichte Augustus de Morgan (1806 - 1871), einer der Begründer der Mengenlehre, den Artikel Induction (Mathematics) in der Londoner Zeitschrift "Penny Cyclopedia". Am Ende dieses Artikels benutzte er den Namen für die vollständige Induktion erstmals im heute üblichen Sinn. Jedoch fand diese Bezeichnung erst in unserem Jahrhundert ihre weite Verbreitung.
[Zitat aus einem Internet-Artilel "Vollständige Induktion" von Prof. Dr. rer. nat. Udo Hebisch]
Ich werde unten vielfältige Beispiele für Beweise mit vollständiger Induktion geben.
Wenn also der Induktionsanfang abgesichert ist, dann weiß man, dass die Behauptung für alle n kleinergleich einem bestimmten n0 gilt (das ist oft nur eine einzige natürliche Zahl, meistens die 1).
Diese Formulierung mit n0 nennt man dann die Induktionsvoraussetzung.
Nun kommt der Induktionsschritt. Formal lautet der:
Aus der Gültigkeit der Behauptung für n≤n0 folgt die Gültigkeit der Behauptung für n≤n0+1 (die Induktionsbehauptung).
Wenn man das zeigen kann, was hat man dann davon?
Wenn die Behauptung für n0=1 gilt, dann gilt sie auch für n0=2.
Wenn die Behauptung für n0=2 gilt, dann gilt sie auch für n0=3.
Wenn die Behauptung für n0=3 gilt, dann gilt sie auch für n0=4.
usw.
Den Induktionsschritt von n->n+1 kann man beliebig oft (in Gedanken) anwenden. Die Schlussweise ist immer die gleiche.
Folglich gilt die Behauptung für alle n ∈ IN.
Ich habe jetzt zur Verdeutlichung immer n0 geschrieben, weil man die Induktionsvoraussetzung nur für eine oder einige natürliche Zahlen geprüft hat und voraussetzen darf. Mehr war im Induktionsanfang ja nicht nachgewiesen worden. In der Praxis schreibt man eigentlich immer n statt n0 und weiß dennoch, was gemeint ist.
Vielleicht sollte ich zur Klarheit noch die Begriffe Aussage und Aussageform erklären. Eine Aussage ist eine überprüfbare Eigenschaft irgendwelcher konkreten Dinge. Beispiele: [Menschen haben einen Kopf] oder [Primzahlen sind durch 2 teilbar]. Eine Aussage kann wahr oder falsch sein, aber sie ist auf jeden Fall überprüfbar bzw. entscheidbar. Eine Aussageform dagegen ist eine Aussage, die eine Variable enthält, z.B. [n ist durch 2 teilbar]. Bei der vollständigen Induktion ist A(0) eine Aussage und A(n) eine Aussageform. Auch [A(n)→A(n+1)] ist eine Aussageform. Dagegen ist das, was man eigentlich mit vollständiger Induktion beweisen will, nämlich [Für alle natürlichen Zahlen n gilt A(n)] eine Aussage und keine Aussageform, denn dies ist eine Aussage über alle natürlichen Zahlen, deren Wahrheitsgehalt nicht von der Wahl eines bestimmten n abhängt. Die Aussage ist nämlich falsch, wenn sie für eine einzige natürliche Zahl n0 nicht gilt, egal welches. Ein Beispiel: Die Aussage [alle natürlichen Zahlen sind kleiner als 100] ist falsch. Die Aussageform [die natürliche Zahl n ist kleiner als 100] dagegen ist wahr für n<100 und falsch für n>99.
Falsches Beispiel 1:
Behauptung: In einen Koffer passen beliebig viele Paar Socken.
Beweis durch vollständige Induktion: Induktionsanfang: n=1: Ein Paar passt in einen leeren Koffer, Ok!Induktionsschluss von n auf n+1: In einem Koffer seien n Paar Socken. Ein Paar passt immer noch hinein, das ist eine allgemeingültige Erfahrung. Also sind nun n+1 Paar in dem Koffer. Ok!
Dieses Beispiel (gefunden bei
www.mathekiste.de
) ist ein Witz und gehört zur Mathematik-Folklore. Der echte Fehler in diesem "Beweis" liegt darin, dass man Erfahrung nur mit geringen Anzahlen von Socken hat.
Falsches Beispiel 2:
Behauptung: Wenn sich unter n Tieren ein Elefant befindet, dann sind alle diese Tiere Elefanten.
Beweis durch vollständige Induktion:
Induktionsanfang: n=1 : Wenn von einem Tier eines ein Elefant ist, dann sind alle diese Tiere Elefanten.
Induktionsvoraussetzung: Die Behauptung sei richtig für alle natürlichen Zahlen kleiner oder gleich n.
Induktionsschluss: Sei unter n+1 Tieren eines ein Elefant. Wir stellen die Tiere so in eine Reihe, dass sich dieser Elefant unter den ersten n Tieren befindet. Nach Induktionsannahme sind dann alle diese ersten n Tiere Elefanten. Damit befindet sich aber auch unter den letzten n Tieren ein Elefant, womit diese auch alle Elefanten sein müssen. Also sind alle n+1 Tiere Elefanten. ?????Was daran falsch ist?
Im Fall n+1=2 kann man den Elefanten zwar so stellen, dass er bei den ersten n=1 Tieren steht. Folglich sind alle Tiere unter den ersten n=1 Tieren Elefanten. Aber deshalb befinden sich unter den "letzten" n Tieren nicht notwendig Elefanten.
Der Induktionsschluss funktioniert nur für n>1, denn nur dann können aus einem Elefanten zwei (oder mehr) werden und ist damit auch ein Elefant unter den letzten n Tieren.
Die Induktionsvoraussetzung war aber gezeigt für n=1.
Man müsste also zunächst zeigen, dass von zwei Tieren, von denen eines ein Elefant ist, auch das andere ein Elefant ist. Aber das wird schwer.
Der eigentliche Fehler des "Beweises" liegt darin, dass (n+1)/2 nicht immer größer als 1 ist. Wenn wir uns n+1 Dinge in einer Reihe vorstellen, dann sehen wir vor unserem inneren Auge eine lange Reihe, mit 10 oder 20 oder 1000 Dingen (Tieren). Aber eine Reihe von Tieren kann auch aus 2 Tieren bestehen. Dafür gilt der vermeintliche Induktionsschluss nicht.
Die Durchführung des Induktionsschritts erfordert zudem handwerkliche mathematische Fähigkeiten. Gerade bei Induktionsbeweisen muss man die Regeln der Termumformungen und die Handhabung von Summenzeichen und Variablenindizes beherrschen. Nur dann kann man die richtige Idee auch wirklich verifizieren.
Die natürlichen Zahlen standen ganz am Anfang unseres Aufbaus des Zahlensystems. Wir haben so getan, als seien sie unproblematisch und jedermann vom Abzählen und vom Anordnen her wohlbekannt. Das war auch in der geschichtlichen Entwicklung der Mathematik so. Während die irrationalen und die negativen Zahlen den Gegenstand von langwierigen Auseinandersetzungen bildeten, kümmerte man sich um die natürlichen Zahlen nur wenig. Gegen Ende des 19. Jahrhundert änderte sich dies. Den Mathematikern war es gelungen alle anderen Zahlenarten auf die natürlichen zurückzuführen. Damit stellte sich die Frage "Was ist eigentlich eine natürliche Zahl?" Eine Antwort hierauf gab der italienische Mathematiker Giuseppe Peano (1858-1932) im Jahre 1889. Peano nannte fünf Eigenschaften, die die Menge der natürlichen Zahlen N kennzeichnen:Man nennt diese Eigenschaften heute die Peano-Axiome. Mit dem Begriff "Axiom" bezeichnet man Annahmen, die man als wahr voraussetzt. Für die Zwecke der Mathematik genügt es, die Menge der natürlichen Zahlen als dasjenige Gebilde zu betrachten, das diese fünf Eigenschaften besitzt.Die Axiome der natürlichen Zahlen nach Peano:
- 1 ist eine natürliche Zahl.
- Zu jeder Zahl n gibt es eine eindeutig bestimmte natürliche Zahl n*, genannt der Nachfolger von n.
- 1 ist nicht der Nachfolger irgendeiner natürlichen Zahl.
- Zwei natürliche Zahlen n und m, deren Nachfolger gleich sind (d.h. m* = n*), sind selbst gleich (d.h. m = n).
- Es sei T eine Teilmenge der natürlichen Zahlen mit folgenden Eigenschaften:
Dann stimmt T mit N überein.
- 1 gehört zu T;
- gehört n zu T, dann ist auch der Nachfolger n* von n ein Element von T.
Oftmals ist man auch versucht, die Induktion immer für möglich zu halten, wenn nur ein n in der Behauptung vorkommt. Wenn man etwas beweisen will oder muss, dann ist die Suche nach der richtigen Beweismethode erforderlich. Die Möglichkeit der Verwendung der vollst. Induktion gehört dazu. Man muss aber auch lernen, wann die vollständige Induktion nicht geeignet ist. Beispiel: Die Aussage: [Die Folge a(n) = 1/n ist immer positiv.] kann man nicht mit vollständiger Induktion beweisen. Wie sollte man aus A(n): [1/n > 0] denn folgern, dass A(n+1): [1/(n+1) > 0] ist? Gut, beide Aussageformen sind wahr, aber man kann A(n+1) nicht aus A(n) folgern. Man muss hier andere Argumente verwenden. Nicht aus jeder wahren Voraussetzung kann man jede andere wahre Behauptung folgern.
d(n) = n/2 * (n-3)berechnet werden kann! Für welche n gilt die Formel?
Lösung:
Idee: vollst. Induktion über die Anzahl der Ecken.
Induktionsanfang für ein Dreieck. Ein Dreieck hat keine Diagonalen, also d(3) = 0 = 3/2 * (3 - 3). Für n=3 ist die Behauptung richtig.
Induktionsschritt: Stelle Dir ein konvexes n-Eck vor (z.B. ein Fünfeck). In dieses zeichne eine Diagonale von einem beliebigen Eckpunkt zu einem "übernächsten" Eckpunkt, also so, dass ein Dreieck und ein (n-1)-Eck entsteht.
Konvexes, ebenes n-Eck, durch eine Diagonale zerlegt in ein (n-1)-Eck und ein 3-Eck |
Das Dreieck hat keine und das (n-1)-Eck hat d(n-1) Diagonalen (Induktionsvoraussetzung).
Außerdem muss man noch die Diagonalen von der Ecke des Dreiecks, die nicht eine Ecke des (n-1)-Ecks ist, zu allen Ecken des (n-1)-Ecks, die nicht Eckpunkt des Dreiecks sind, zählen - und nicht zu vergessen die eine Diagonale, mit der das Dreieck abgeteilt wurde.
Folgt: d(n) = d(n-1) + (n-3) + 1
= (n-1)/2 * ((n-1)-3) + (n-3) + 1
= (n-1)*(n-4)/2 + n -2
= (n2-5n+4)/2 + n -2
= (n2-3n)/2
= (n * (n-3)) / 2
Fertig.
Einige Bemerkungen:
Zunächst ist festzustellen, dass ein "höchstens" fehlt. Durch n Geraden wird die Ebene höchstens in ... Teile zerlegt. Die Geraden könnten ja parallel oder identisch sein.
Induktionsanfang: n=1. Eine Gerade teilt die Ebene in 2 Gebiete und (12+1+2)/2 ist gleich 2.
Die (n+1)-te Gerade teilt maximal n+1 Gebiete |
Lösung:
die Potenzmenge P(M) ist die Menge aller Teilmengen von M. Die Frage ist also, wieviele verschiedene Teilmengen man aus m Elementen bilden kann. Um das zu zählen gibt es verschiedene Möglichkeiten, ja nachdem, was man verwenden darf. Was man immer anwenden kann, ist vollständuge Induktion.
A) Wenn M={}, also |M|=0, dann ist P(M)={{}}, denn nur die leere Menge ist Teilmenge der leeren Menge. Also |P(M)|=1=20.
B) Sei nun |M|=n+1. Sei x ein bestimmtes Element aus M. Bilden wir nun alle Teilmengen.
Wir können die Teilmengen aufteilen in
a) die Teilmengen, die x nicht enthalten,
b) die Teilmengen, die x enthalten.
Nach Induktionsvoraussetzung wissen wir, das die Anzahl der Teilmengen bei a) = 2n ist, denn es handelt sich ja um alle Teilmengen einer Menge mit n Elementen.
In allen Teilmengen aus b) können wir das Element x entfernen. Dann ist die Anzahl dieser Mengen also auch = 2n, denn es handelt sich auch hier um alle Teilmengen einer Menge mit n Elementen.
Addiere nun die Anzahlen für a) und b)
2n + 2n = 2n+1.
Fertig.
Auch das geht mit Induktion.
Für n=0 steht da (1+x)0 = (00)*x0 und das ist richig.
Für n=1: 1+x = (10)*x0 + (11)*x1 auch richtig.
Nun der Induktionsschritt:
(1+x)n+1 = (1+x)n * (1+x)
= (1+x) * ∑n i=0 (ni)*xi
= 1* ∑n i=0 (ni)*xi + x* ∑n i=0 (ni)*xi
= ∑n i=0 (ni)*xi + ∑n i=0 (ni)*xi+1
jetzt verschiebe ich den Index in der zweiten Summe.
= ∑n i=0 (ni)*xi + ∑n+1 i=1 (ni-1)*xi
In den beiden Summen kommen die Potenzen x1 bis xn vor. Aber x0 ist nur in der ersten Summe und xn+1 nur in der zweiten Summe. Ich zerlege die Summen dementsprechend.
= 1 + ∑n i=1 (ni)*xi + ∑n i=1 (ni-1)*xi + xn+1
Und dann kann ich die beiden Summen zusameenfassen:
= 1 + ∑n i=1 [(ni) + (ni-1) ]*xi + xn+1
Nun gilt für die Binomialkoeffizienten die folgende Beziehung: (ni) + (ni-1) = (n+1i)
Das eingesetzt ergibt:
= 1 + ∑n i=1 (n+1i)*xi + xn+1
und dann
= ∑n+1 i=0 (n+1i)*xi
Entschuldigung, dass ich es dabei belasse. Bei der vorigen Aufgabe mit (1+x)n war ich noch ausführlich. Hier ist es doch genau dasselbe.
Wir beweisen zuerst folgenden
Hilfssatz: Gilt für reelle Zahlen b1, ... ,bn:Beweis des Hilfssatzes mit vollständiger Induktion über n.
∏k=1n bk = 1, so ist ∑k=1n bk ≥ n
Gleichheit gilt genau dann, wenn b1=b2=...=bn.
Aus der Induktionsvoraussetzung folgt für die n Zahlen
b1*b2, b3, ... ,bn, bn+1:Insgesamt erhält man:b1*b2 + ∑k=3n+1 bk ≥ n.
Zurück zum Beweis der Behauptung über geometrisches und arithmetisches Mittel
Wenn a1 = a2 = ... = an, dann ist die Behauptung trivial, und die Ungleichung gilt mit Gleichheit.
Nehmen wir also an, dass die ai nicht alle gleich sind.
Sei G := .
Betrachte bi := ai / G.
Nach Konstruktion ist ∏k=1n bk = 1.
Da nicht alle bi gleich sind, folgt aus dem Hilfssatz:
QED.
Vollst. Induktion über n.
n=1: 1=1 ok
n+1: Es ist ∑n+1 i=1 i3 = [ ∑n i=1 i3 ] + (n+1)3
Die Summe bis n kann nach Induktionsvoraussetung ersetzt werden:
= [ ∑n i=1 i ]2 + (n+1)3
und das soll gleich [ ∑n+1 i=1 i ]2 sein.
Um das zu sehen, wende ich die Binomische Formel auf
[ ∑n+1 i=1 i ]2 = [ (∑n i=1 i ) + (n+1) ]2 an:
= [ (∑n i=1 i ) ]2 + 2(n+1)*(∑n i=1 i ) + (n+1)2
Für die Summenformel in der Mitte setze ich den seit Gauss bekannten Ausdruck ein:
= [ (∑n i=1 i ) ]2 + 2(n+1)*1/2*n*(n+1) + (n+1)2
= [ (∑n i=1 i ) ]2 + (n+1)*n*(n+1) + (n+1)2
in den hinteren beiden Summanden klammere ich (n+1)2 aus:
= [ (∑n i=1 i ) ]2 + (n+1)2* (n + 1)
= [ (∑n i=1 i ) ]2 + (n+1)3
Das war's.
Beispiele
S(1,1)=∑1 i=1 a(i) = 1/3
S(2,4)=∑4 i=2 a(i) = 1/15 + 1/35 + 1/63 = 1/9
S(5,12)=∑12 i=5 a(i) = 1/27
Die Anzahl der Summanden je Summe ist 1, 3, 9.
Von vorne beginnend kann man jeweils die nächsten 3k Summanden addieren (k≥0) und deren Summe ist gleich 1 / 3k+1.
Also:
Die ersten 30 Summanden addiert, ergibt 1/31.
Die nächsten 31 Summanden addiert, ergibt 1/32.
usw.
Es läuft darauf hinaus, dass ∑n i=1 a(i) <= ∑x k=0 S(y,z) = ∑x i=1 (1/3)i. Das ist eine geometrische Reihe mit q=1/3, der nur der i=0-Term fehlt. Mit 0-Term ist die Summe der geom. Reihe gleich (1-qn)/(1-q). Ohne 0-Term ist die Summe (1-qn)/(1-q) - 1. Mit q=1/3 kann man hier zeigen, dass das immer kleiner 1/2 ist.
Was muss man nun noch tun?
1. Eine Berechnungsvorschrift für x, y und z in ∑n i=1 a(i) <= ∑x k=0 S(y,z) angeben.
2. Mit Induktion beweisen, dass diese Summen für die passenden x,y,z gleich 1/3? ist.
Versuch mal, was Du auf diese Art erreichen kannst.
Der Ansatz für den Beweis ist, dass man - wie ich schon
geschrieben habe - die Summanden zu Gruppen zusammenfasst
(immer 3k Summanden, also erst 1, dann 3, dann 9 usw.) und
für jede Teilsumme (die nenne ich S(i,j)) zeigt, dass sie
kleiner oder gleich etwas ist.
Dabei hat man es mit sehr unangenehmen Indexrechnungen zu
tun.
Aber um zu verstehen, was ich meine, kannst Du ja mal die
Teilsummen bilden.
Auch wenn Du das dann nicht formal hinbekommst, hast Du
dennoch etwas verstanden.
Der Induktionsanfang ist klar
n=1 => 72 - 21 = 47; 47 ist Teiler von 47
und die Induktionsbehauptung auch: A(n+1): 47 ist ein Teiler von 7(2n+2) - 2(n+1)
Wie kann ich diesen Ausdruck vereinfachen, so dass eine Aussage stehen bleibt, von der auch 47 Teiler ist.
Ganz einfach:
72n - 2n = [72]n - 2n.
Induktionsschritt:
[72]n+1 - 2n+1
= [72]n*[72] - 2n+1
Ergänze in der Klammer -2 und hinter der Klammer
mache das durch +2*[72]n wieder gut.
= [72]n*[72-2] +2*[72]n - 2*2n
= [72]n*[72-2] + 2*[72]n - 2*2n
= [72]n*[72-2] + 2*( [72]n - 2n )
Jeder der beiden Summanden enthält also einen Faktor, der nach Induktionsvoraussetzung durch 47 teilbar ist. Folglich ist der gesamte Ausdruck durch 47 teilbar.
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 p1,....,pn.
Dann betrachte die Zahl p=p1*...*pn+1, welche offensichtlich
durch keines der pi, i=1,...,n teilbar ist. Dann muss p, welches ja von allen
pi verschieden ist, offensichtlich eine Primzahl sein.
Das ist ein Widerspruch zur Annahme.
Also war die Annahme falsch, es muss demnach unendlich viele Primzahlen geben.
Es seien die ersten n Primzahlen bekannt. Dann betrachte Zahl q = p1*...*pn+1, welche offensichtlich durch keines der pi, 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
p1, ... , pn. Es muss demnach eine weitere Primzahl geben, die q teilt. Diese "andere" Primzahl ist größer als pn. 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 p1=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 p1,....,pn 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.
Anfangswerte sind a(0) = 1
a(1) = 2
Ich rechne zuerst einige weitere Folgenglieder aus:
a(2) = 1 + 3*a(0) + ∑-1 k=0 a(k)
Die Summe hat also keine Summanden!
=> a(2) = 1+3*1 = 4
a(3) = 1 + 3*a(1) + ∑0 k=0 a(k)
Die Summe hat nur einen Summanden: k=0!
=> a(3) = 1+3*a(1) + a(0) = 1 + 3*2 + 1 = 8
a(4) = 1 + 3*a(2) + ∑1 k=0 a(k)
Die Summe hat zwei Summanden: k=0 und k=1!
=> a(4) = 1+3*a(2) + a(0) + a(1) = 1 + 3*4 + 1 + 2 = 16
a(5) = 1 + 3*a(3) + ∑2 k=0 a(k)
=> a(5) = 1+3*a(3) + a(0) + a(1) + a(2) = 1 + 3*8 + 1 + 2 + 4 = 32
Das sieht so aus, als ob a(n) = 2n sein könnte.
Diese Vermutung habe ich durch die ersten berechneten Folgenglieder gefunden.
Ich weiß noch nicht, ob diese Vermutung richtig ist, aber ich will versuchen sie zu beweisen.
Wenn ich a(n) = 2n beweisen kann, dann habe ich die geforderte Formel für a(n).
Beweis mit vollständiger Induktion.
Die Behauptung a(n) = 2n ist richtig für n=1,2,3,4 und 5 (wie man oben gesehen hat).
Nun zum Induktionsschritt. Wir wissen, dass für alle n≤n0 gilt: a(n) = 2n.
a(n+1) = 1 + 2a(n-1) + ∑n-1 k=0 a(k) = 1 + 2*2n-1 + ∑n-1 k=0 2k
Die Summe ∑n-1 k=0 2k ist gleich (2n-1)/(2-1). Diese Formel ist bekannt, denn es handelt sich um eine geometrische Reihe mit q=2.
Das setze ich ein:
a(n+1) = 1 + 2*2n-1 + (2n-1-1)/(2-1) = 1 + 2*2n-1 + 2n - 1 = 2n + 2n = 2n+1
Genau das wollten wir zeigen.
Also gilt für alle n: a(n) = 2n
Die schwierigere Frage bei rekursiv definierten Folgen ist die, wie man eine geschlossene Form findet. In dieser Aufgabe ist die Vermutung an=(n+1)/n nach einigen ausgerechneten Werten leicht zu raten.
Um jetzt die Vermutung zu beweisen, muss man nichts besonderes beachten. Ziel ist eine vollständige Induktion.
Für n=1 ist die Behauptung wahr.
Und nun der Schluss von n auf n+1.
Wenn also die Behauptung an=(n+1)/n wahr ist,
dann ist jetzt zu zeigen, dass auch an+1=(n+2)/(n+1) wahr ist.
Wegen der rekursiven Definition ist an+1=2-1/an. [*]
Und nach Voraussetzung der vollständigen Induktion hier: an = (n+1)/n. [**]
Gleichung [**] in [*] einsetzen, umformen und umordnen, dann steht da
an+1=2-n/(n+1) = (2n+2-n)/(n+1) ) (n+2)/(n+1).
Das war zu zeigen.
Das Problem bei dieser Aufgabe ist eher, dass sie sehr einfach ist und man Mühe hat, keinen Beweisschritt auszulassen.
Was waren die Schritte:
Sei n ∈ Z und nehmen wir an, dass es zwei verschiedene Repräsentationen gibt.
Also einerseits ∑k i=0 ai*3i = n
und andererseits ∑l i=0 bi*3i = n.
Wir können o.B.d.A annehmen, dass k≥l, ansonsten vertauschen wir eben k und l.
Außerdem können wir, falls l<k ist, die zweite Summe auch bis k laufen lassen mit Koeffizienten bi=0 für l<i≤k.
Dann haben wir in beiden Summen gleich viele Summanden. Jetzt bilde die Differenz:
∑k i=0 ai*3i - ∑k i=0 bi*3i
= ∑k i=0 (ai-bi)*3i = 0
Beweise nun, dass die Koeffizienten alle Null sind und zwar durch vollständige Induktion über k.
k=0 => (a0-b0)*1 = 0 => a0 = b0
Nun k->k+1. Hinschreiben, dann umsortieren und schließlich:
∑k i=0 (ai-bi)*3i = (bk+1-ak+1)*3k+1
Man sieht, die rechte Seite der Gleichung ist durch 3k+1 teilbar. Da auf der linken Seite nur kleiner Dreierpotenzen vorkommen
und außerdem -2 < ai-bi < 2 für alle 0≤ i ≤ k, folgt dass bk+1-ak+1=0. Auf den Rest der Darstellung wende die Induktionsvoraussetzung an (hat ja Summe bis k). Immer gilt ai = bi.
Fertig.
Achtung: Hier wurde nicht gezeigt, daß die geforderte Darstellung existiert. Es wurde gezeigt, daß die Darstellung eindeutig ist, falls sie existiert. Wir haben immer noch keine Ahnung, wie man eine solche Darstellung für ein n ausrechnen kann. Mehr war aber nicht verlangt.
Die Funktion f(x)=x-n=1/xn kann man auch schreiben als f(x)=g(x)/h(x) mit g(x)=1 und h(x)=xn.
Die Quotientenregel sagt f'(x)=[g'(x)*h(x)-g(x)*h'(x)]/(h(x))2
Wenn schon als bekannt benutzt werden darf, daß h'(x)=n*xn-1, dann erhält man:
f'(x) = [0*h(x)-1*n*xn-1]/x2n = -n*xn-1/x2n = -n/xn+1 = -n*x-n-1
Wenn h'(x)=n*xn-1 auch bewiesen werden soll, dann mache das mit Induktion unter Verwendung der Produktregel.
Bemerkung:
Ich drücke die Funktion f(x) als Quotient der Funktionen g(x)/h(x) aus.
Die Regel für die Ableitung von Quotienten ist schon bekannt, und ich benutzte sie.
Der Sinn dieses Ansatzes ist, die negativen Exponenten in positive Exponenten von Funktionen im Nenner eines Quotienten zu verwandeln.
Dann setze ich für g, g', h und h' die jeweiligen Ableitungen ein. Für g(x)=1 ist g'(x)=0. Für h(x)=xn ist h'(x)=n*xn-1.
Mit etwas Termumformung und den Potenzrechenregeln (xn-1/x2n ist gleich 1/xn+1, denn 2n-(n-1) ist n+1) komme ich dann zum Ergebnis.
Und auch wegen der Potenzrechenregeln ist (xn)² = (x2n)
Weiterführende Links bei Matroids Matheplanet.
Sehr schöne und von der Idee her abwechslungsreiche Induktionsbeweise gibt es auch in der Kombinatorik und Graphentheorie (Induktion über die maximale Valenz einer Ecke). Vielleicht schreibe ich darüber das nächste mal.
|
Mathematisch für Anfänger |