Vollständige Induktion
-
Hallo zusammen,
ich beschäftige mich gerade mit dem Beweisverfahren der vollständigen Induktion. Zur Übung möchte ich eine Aufgabe lösen, bei der ich aber Probleme habe.
Ich habe eine Zahl k aus den natürlichen Zahlen. Nun möchte ich durch vollständige Induktion zeigen, dass diese Zahl für alle n aus den natürlichen Zahlen außer 0 die Zahl (k + 1)^n - 1 teilt.
Kurz: Ich möchte zeigen, dass k | (k+1)^n - 1 gilt.
Mein Ansatz:
Vorraussetzung: k ist aus den natürlichen Zahlen
Behauptung: Für alle n € |N \{0} gilt k | (k+1)^n - 1Induktionsanfang: Es gilt k € |N. Die Behauptung gilt schon einmal für n = 1, denn k | k.
Induktionsvorraussetzung: Für ein n € |N gilt k | (k+1)^n - 1.
Induktionsschluss: Jetzt möchte ich zeigen, dass die Behauptung auch für n+1 gilt.
k | (k+1)^(n+1) - 1
Jetzt muss ich dazu sagen, dass ich mit dem Paradebeispiel der vollständigen Induktion, der Beweis der gaus'schen Summenformel, keine Schwierigkeiten hatte. Da habe ich dann einfach den "n+1" Ausdruck auseinander gezogen. Das wollte ich hier auch machen:
k | (k+1)^n * (k+1) - 1
Aber was bringt mir das jetzt? Wie muss ich da jetzt umformen, sodass ich den Beweis fertigstelle? Was steht auf der anderen Seite? Bin ich überhaupt auf dem richtigen Weg?
Vielen Dank
lg, freakC++
-
Einmal Distributivgesetz auf der rechten Seite bringt dich zur Lösung.
(Eine Anmerkung zu der Aufgabe: Vollständige Induktion ist der denkbar dümmste Ansatz für den Beweis; Anstarren und sich an den binomischen Lehrsatz erinnern liefert viel mehr Einsicht)
-
Hallo YASC,
danke für deine Antwort. Ich habe ein paar Gegenfragen.
1.) Habe ich es richtig verstanden, dass ich immer auf die Induktionsvorraussetzung kommen muss? Das dachte ich eigentlich immer, denn beispielsweise bei dem Beweis der Gauß'schen Summenformel forme ich dann einfach solange um, bis ich die Äquivalenz gezeigt habe.
2.) Wo kann ich denn da das Distributivgesetz anwenden? Da kann ich doch nichts ausmultiplizieren oder ausklammern ?
Vielen Dank
lg, freakC++
-
freakC++ schrieb:
1.) Habe ich es richtig verstanden, dass ich immer auf die Induktionsvorraussetzung kommen muss?
Du musst sie irgendwo verwenden. Ansonsten ist das zwar auch ein Beweis, aber keiner mit vollständiger Induktion
2.) Wo kann ich denn da das Distributivgesetz anwenden? Da kann ich doch nichts ausmultiplizieren oder ausklammern ?
(k+1) ausmultiplizieren.
-
gelöscht
-
Stimmt
Ich hab folgendes Ergebnis: k | k(k+1) + (k+1)^n -1
Der zweite Summand ist gerade die Induktionsvorraussetzung von der ich weiß, dass sie durch k teilbar ist. Der erste Summand ist ein Vielfaches von k und damit auch durch k teilbar. Daher ist auch die Summe von k teilber.
Bin ich damit schon fertig?
Danke euch!
-
Ja, passt.
-
Da fehlt noch ein ^n bei dem k(k+1), oder? Ändert aber nichts an der Aussage.
-
Warum nimmst du eigentlich den Fall n = 0 raus? Für den funktionierts auch.
-
Super! Zur Übung habe ich mir noch eine andere Aufgabe herausgesucht, bei der ich zwar auf eine Lösung komme, aber nicht weiß, ob der Weg bist dahin korrekt ist.
Ich möchte zeigen, dass die Ungleichung 7^n >= n⁶ ist, wobei n größer als 4 ist und ich verwenden darf, dass die sechste Wurzel von 7 >= 6/5 ist. Der Induktionsanfang ist kein Problem und alles ist wunderbar. Nun möchte ich noch zeigen, dass diese Ungleichung auch für n+1 gilt:
7^{n+1} >= (n+1)^6
7^n * 7 >= (n+1)^6Achtung: Jetzt kommt der Schritt, bei dem ich nicht weiß, ob er richtig ist. Ich ersetze auf der linken Seite 7^n durch n⁶, da dies meine Induktionsvorraussetzung ist:
n^6 * 7 >= (n+1)^6 | SechsteWurzelZiehen
n * 7^(1/6) >= n+1 | durch n teilen7^(1/6) >= 1 + 1/n
Die rechte Seite kann niemals größer als 6/5 werden, weswegen die Gleichung stimmt.
Habe ich das richtig gemacht?
Danke!
-
Es ist nie verkehrt, die Induktionsvoraussetzung zu nutzen. Es kann allerdings sein, dass du dadurch zu grob abschätzt, sodass die Ungleichung nicht mehr gegeben ist.
Beispiel: Wenn ich n >= n zeigen will und an der Stelle n+1 >= n+1 die Induktionsvoraussetzung auf der linken Seite benutze, steht da n >= n+1. Ich hab mir also durch Einsetzen der Induktionsvoraussetzung die Ungleichung zerstört. Wenn allerdings nach dem Benutzen der Voraussetzung immer noch eine wahre Aussage da steht, funktioniert der Beweis.
Dafür schreibt man an der von dir markierten Stelle in der Regel sowas wie: "Es reicht zu zeigen, dass..."
-
Achja, den Induktionsschritt kann man auch als Einzeiler schreiben.
7^(n+1) = 7 * 7^n (IV)>= 7 * n^6 >= (6/5)^6 * n^6 >= ((n+1)/n)^6 * n^6 = (n+1)^6.
-
Das war gerade mein Problem. Ich wusste nicht, ob die Ungleichung dann noch überhaupt gilt. Wenn ich also diesen Satz dazu schreibe, dann sollte es funktionieren?!
Bedeutet dies, dass die Aufgabe richtig ist?
Durch das Nichtaktualisierung meines Browers habe ich gar nicht gemerkt, dass noch andere eine Antwort gepostet haben:
Michael E. schrieb:
Warum nimmst du eigentlich den Fall n = 0 raus? Für den funktionierts auch.
Das habe ich nur hier gemacht. Auf dem Blatt habe ich für n = 0 und n = 5 geprüft.
ipsec schrieb:
Da fehlt noch ein ^n bei dem k(k+1), oder? Ändert aber nichts an der Aussage.
Stimmt! Danke für den Hinweis.
Viele Grüße
lg, freakC++
-
Ja ist alles okay!