Analyse 1, 1. Kapitel, vollständige Induktion. In der Analyse wollen wir, oder im Allgemeinen in allen Mathefächern, wollen wir öfter Sätze oder Behauptungen beweisen. Es gibt natürlich viele Methoden, wie man Beweise durchführen kann.
Und eine Methode ist die sogenannte vollständige Induktion, welche man gut anwenden kann in Problemen, wo es eine Klasse von Aussagen gibt, die von natürlichen Zahlen abhängen. Das heißt, wir haben ein solches Beweisprinzip. Wir haben eine Klasse von Aussagen, an, mit n, sagen wir mal, natürliche Zahlen.
Was sind natürliche Zahlen? Das ist eine Menge von nicht-negativen Ganzzahlen, das heißt, das ist Menge von 0, 1, 2 und so weiter. Und wir wollen beweisen, dass alle diese Aussagen gelten.
Und eine Methode ist folgendes, wir sagen OK oder wir zeigen, es gibt einen sogenannten Induktionsanfang. Das heißt, es gibt eine Null, eine natürliche Zahl, sodass... A von N0 gilt, oder war ist, und dann haben wir solche Induktionsschritte, wo wir sagen, okay, Induktionsschritt, für jede N größer als N0 haben wir folgendes, Falls a von n gilt, dann gilt auch a n plus 1. Das heißt, wenn es für irgendwelche N gilt, dann gilt das auch für Nächste.
Und dann kann man sehen, wir haben eine Klasse von Aussagen, wo A1 war, und haben diese Induktionsstritt. Das sieht man, wenn A1 gilt, dann nach Induktionsstritt gilt auch A2, dann A3 und so weiter. Natürlich am besten zeigen wir auf ein Beispiel. Wir können das auf Satz 1 nennen. Und zwar, das wird folgendes.
Das für jede natürliche Zahl n gilt folgendes. Das 1 plus 2. plus n ist gleich n mal n plus 1 durch 2. Das heißt, wenn wir summieren 1 plus 2 bis plus n, wir müssen das nicht alle summieren, wir können gleich solche Formen benutzen. Wir wollen das beweisen, wir wollen zeigen, warum das gilt.
Und natürlich auch gesagt, das wird ein Beispiel von dieser Methode, das heißt wir wollen das mit Hilfe von mathematischer Induktion beweisen. Und das heißt wir wollen erst ein... Induktionsanfang haben und dann wollen wir Induktionsschritt haben. Okay, um die Notation schneller zu machen, ich werde sogenannte summieren Zeichen benutzen.
Das ist große griechische Buchstabe Sigma und das bedeutet, das ist Summe von Elementen. So, ich werde die Summe für K bis 1 bis N von K. Das heißt, das ist... die Summe, wir addieren für alle diesen Indexen diesen Elementen, das heißt das wird 1 plus 2 plus 3 bis n.
Okay, so, ja, Induktionsanfang, so wir machen das für n gleich 1. Wir wollen diese Behauptung beweisen für N gleich 1, das ist ganz ideal. Auf der linken Seite haben wir einfach die Summe. Von 1 bis 1, das heißt nur 1. Und auf rechter Seite haben wir n ist 1, das ist 1 mal 1 plus 1 durch 2. Und wir sehen, dass das hier gleich 1 ist. Das heißt, es gilt. Das heißt, linke und rechte Seite sind gleich.
Das heißt, für n gleich 1 das hier gilt. Das ist eigentlich ganz ideal. Und jetzt ist die Induktionsschrift. Induktionsschritt, das heißt, wenn es für n gilt, dann gilt es auch für n plus 1. Wir nehmen an, wir wissen, dass es für irgendwelche n, natürliche Zahl, das hier gilt und dann wollen wir zeigen, das gilt auch für n plus 1. Das heißt, wir fangen an mit der linken Seite, wir wollen berechnen, wie sieht diese Summe aus.
Ja, okay? Und wir sehen, das ist natürlich Summe von 1 bis n plus 1, aber wir erkennen das Scheiben aus die Summe von 1 bis n plus dieser letzte Element, das heißt 1 plus bis n plus n plus 1. Naja, aber wir wissen, dass diese Aussage gilt für n und das sagt uns eigentlich genau, dass das hier ist gleich n mal n plus 1 durch 2. Das hier ist genau n mal n plus 1 plus 2. Das heißt, was hier ist n, n plus 1 durch 2 plus n plus 1. Und wenn wir das zusammenbringen, haben wir 2 mal n plus 2 mal n plus 1. Diese 2 kommt von hier, weil wir haben durch 2 mal 2 gehabt. Und wir können das hier schreiben als n plus 1. mal n plus 1 plus 1 durch 2. Ich habe nur die Ordnung gewechselt und n plus 2 aus n plus 1 plus 1 geschrieben. Und wir sehen, dass das hier genau die rechte Seite für den Fall ist, wenn n gleich n plus 1 ist. Das heißt, wir haben auch Induktionsschritt bewiesen und sind fertig mit dem Beweis.
Das war natürlich ganz einfach. Eigentlich kann man, kann jemand sagen, naja, wir haben das nur für n1 und größer bewiesen, und eigentlich, wir wollen das für alle natürlichen Zahlen, und man kann sagen, ok, was bedeutet, wenn wir die Summe von 1 bis 0 nehmen, das bedeutet, das ist eine leere Summe, so auf der linken Seite haben wir einfach 0, Aber wenn n gleich 0 ist, ist die rechte Seite auch gleich 0. So man kann sagen, ja, auch für n gleich 0 gilt das. Wir machen auch ein anderes Beispiel. Und zwar, wir werden eine ähnliche Formel beweisen.
Und war folgendes. Für jede... natürliche Zahl n gilt, und jetzt nehmen wir wieder eine Summe, aber nur von ungeraden Zahlen, das heißt wir nehmen die Summe von 1 bis n von 2k minus 1. Okay, und wir behaupten, dass das hier ist gleich n Quadrat.
So, wieder ein Beweis. Wir sehen, dass das eine Familie von Aussagen ist, die mit n, eine natürliche Zahl, indexiert sind. Wir können eine mathematische Induktion probieren.
Wie ist es mit n gleich 1, so Anfang, Induktionsanfang. Wenn 1 gleich n gleich 1 ist, dann haben wir die Summe von 1 bis 1 und nur ein Element. k ist gleich 1, das heißt 2 mal 1 minus 1 ist 1. Und auf rechter Seite haben wir 1 Quadrat, das heißt das gilt.
Sehr gut, jetzt probieren wir diesen Induktionsstrich zu machen. Das heißt, wir wissen, es gilt für n und wir wollen zeigen, dass es gilt für n plus 1. Wir nehmen die Summe. von 1 bis n plus 1 von 2k minus 1 und schreiben wir wie vorher als die Summe bis n von 2k minus 1 plus dieses letzte Element, welches ist... 2 mal n plus 1, das ist 2n plus 2 minus 1, das heißt 2n plus 1. Was wir sehen ist, dass hier können wir natürlich schon diese Aussage für n benutzen, das heißt wir wissen, dass das hier ist n Quadrat, das heißt wir haben n Quadrat plus 2n plus 1 und wir wissen, dass das genau ist hier.
n plus 1 Quadrat. Und damit haben wir das bewiesen für alle n größer als 1 und wenn n gleich 0 ist, dann haben wir leere Menge hier, so leere Summe und n gleich 0 gibt uns 0 auf der rechten Seite. Allerdings ist es öfter so, dass man hat eine Behauptung und es gibt mehr Möglichkeiten, wie kann man das beweisen. Das kann man auch in diesem Fall, es ist nicht unbedingt nötig, diese mathematische Induktion zu benutzen.
Man kann das auch anders beweisen, und zwar zum Beispiel kann man Satz 1 benutzen. Wie? Weil ich sehe folgendes, das ist die Summe von ungeraden Zahlen, zwischen 1 und 2n.
Ich kann nehmen alle Zahlen und ich schmeiße die geraden Zahlen weg. Das heißt, ich. Ich benutze folgende Bemerkung, dass 1 plus 3 plus 5 plus 7 zum Beispiel ist eigentlich 1 plus 2 plus 3 plus 4 plus 5 plus 6 plus 7 plus 8, wobei ich 2, 4, 6 und 8 streiche.
Das heißt, ich kann schreiben, dass die Summe von k von 1 bis n von 2k minus 1 ist eigentlich die Summe von 1 bis 2n von k minus, jetzt alle gerade Zahlen, aber gerade Zahlen zwischen 2, 4, 6, 8 sind einfach 2 mal 1, 2, 3 und 4, das heißt 2 mal die Summe zwischen k gleich 1 bis n von k, ja, Und hier kann ich Satz 1 benutzen, welcher sagt, okay, das hier ist 2n, 2n plus 1 durch 2, minus 2 mal, und das hier wieder Satz 1, so hier verwenden wir Satz 1 eigentlich 2 mal, haben wir n, n plus 1 durch 2, Und jetzt, wenn wir unser Algebra richtig machen, kriegen wir, 2 geht weg, diese 2 geht weg, wir haben n mal 2n plus 1 minus n mal n plus 1, das heißt, diese n, n ist gleich hier, und wir haben 2n plus 1 minus n plus 1, das heißt, bleibt n übrig. das heißt ein Quadrat, genau, wie behauptet. So man sieht es gibt mehr Möglichkeiten, es ist nicht immer so, dass den Beweis, ok ich zeige es immer nur, der einzige Beweis.
Ok, wir gehen weiter mit anderen Definitionen, wo es auch ein bisschen mit Induktion zu tun hat und zwar von so genannte Fakultät. Was ein Fakultät ist, das ist, so für jede n setzen wir n Fakultät auf englisch factorial als Produkt zwischen 1 und n von k Das hier ist eine große griechische Pi, das ist das Zeichen für Todo. Das ist eigentlich 1 mal 2 mal bis n.
Das ist das Produkt von Zahlen zwischen 1 und n. und wenn man ein bisschen überlegt, was bedeutet wenn n gleich 0 wird, das ist die zwischen k gleich 1 bis 0, das heißt es ist eine leere Menge und dann man überlegt, okay, wenn ich die Summe, ein Produkt von keiner Lm nehme, das soll 1 sein. Das heißt, Man kann es als Bemerkung nehmen, dass 0 Faktorial ist 1 nach dieser Definition.
Und warum ist Fakultät wichtig für uns? Es gibt eine folgende Beobachtung oder Bemerkung, man kann das nennen als kombinatorische Bedeutung von Fakultät. Was das sagt ist, dass eigentlich n-Fakultät ist genau Zahl von Anordnungen einer Menge mit n Elementen. So, ist Zahl von unterschiedlichen Anordnungen.
von n Mengen, sagen wir mal, a1 bis, von Mengen, n Elementen, von Menge von n Elementen. So, hier kommt ein Beweis. Wie kann man das zeigen?
So, wieder, wir werden mathematische Induktion anwenden. Für n gleich 1 haben wir auf linker Seite 1 Fakultät von 1, das ist 1. 1 Faktorial, das ist 1. Und wenn wir ein Element haben, wie viele Möglichkeiten gibt es, diese Elemente einordnen? Naja, eigentlich nur ein. Es gibt nur eine Anordnung.
Jetzt wollen wir Induktionsschritt machen. Meistens ist es so, dass dieser Anfangsschritt nicht so schwierig ist, weil dann muss man diese Behauptung nur für ein Zahl oder für ein n zeigen und dann meistens schwieriger ist dieser Induktionsschritt, weil da muss man eigentlich für jede Schritte das zeigen, für beliebige n oder für n groß genug. Wie zeigen wir diesen Induktionsschritt? Das heißt, wir wollen berechnen, wie viele unterschiedliche Anordnungen von n plus 1 Elementen gibt, so Wir wollen zeigen, wie viele solche Anordnungen es gibt und wie wir das machen können. Wir haben diese n plus 1 Elemente und wir konzentrieren uns auf dem letzten Element an plus 1. Und wir sagen jetzt, okay wir haben Elementen a1 bis an plus 1. Und wir sagen, okay, eine Möglichkeit ist, dass a auf erste Stelle steht, das heißt, wir sagen c ist Menge von Anordnungen mit a auf erstes.
Und wir fragen, okay, wie viel gibt es solcher Anordnungen? Okay, so A1 ist, A1 plus 1 ist auf erster Stelle, dann bleibt ein Stern übrig und wir haben n Elemente. Das heißt, wir haben nach dieser Induktionsvoraussetzung, haben wir n Fakultät von solcher Anordnungen.
Das heißt, die Größe von C1 ist genau n Fakultät und... So, noch einmal, ich wiederhole, wir nehmen a n plus 1, wir wissen, dass es auf erster Stelle ist, das heißt, wir haben noch von diesen n plus 1 noch n Stellen leer, und wir haben n Elemente, welche wir da ein und erkennen, und deshalb kriegen wir nach dieser Voraussetzung n Fakultät. Jetzt kann ich wiederholen mit c2. c2 kann ich sagen, ja, c2 ist die Menge, wo die a n plus 1 auf zweiter Stelle sitzt. und die andere erste dritte bis n plus erste Stelle sind leer, da kann ich wieder n Elementen setzen und dann kriege ich wieder n Fakultät.
Und das geht so bis cn plus 1, so die Bemerkung ist, dass die Größe von c1, so jede ci hat n Fakultät Element. hat Größe n Fakultät. Und wie viele gibt es c ist?
Es gibt c1, c2 bis c n plus 1. Das heißt, diese Zahl von Anordnungen ist n plus 1, das ist wie viel wir solche Mengen haben und jede Menge ist n Fakultät. Das heißt n plus 1 mal n Fakultät, aber wir wissen, dass hier ist genau n plus 1 Fakultät. Und damit ist dieser Beweis fertig.