Vollständige Induktion: Teilbarkeit für alle Zahlen n>=0 beweisen |
04.04.2018, 16:24 | mrclndr | Auf diesen Beitrag antworten » | ||||
Vollständige Induktion: Teilbarkeit für alle Zahlen n>=0 beweisen
Ich hatte dazu folgenden Gedankengang:
Meine Frage ist: Ist das sinnvoll oder ist das völliger Blödsinn und beweist eigentlich überhaupt nichts? Ich habe mir ganz konkret bei der Formulierung einer Formel schwer getan, die ich für den Beweis verwenden kann. Bei der gegebenen Aussage muss man sich ja irgendwie die andere Seite des -Zeichens überlegen, um das zu einer Gleichung zu machen. In meinem Fall () konnte diese nicht abhängig vom k sein, wie das ja oft in Summenformeln der Fall ist, denn bei und hätte ich dann direkt im Induktionsbeginn die falsche Aussage . Darum die Idee mit der Variable , die nicht durch den "Counter" beeinflusst werden kann und mir sozusagen eher indirekt meine Beweisabsicht (nämlich Teilbarkeit durch ) anzeigt. Ich steige auch nach langer "Mathe-Pause" wieder ein und daher sind die Basics ein bisschen eingerostet. Kann also gut sein, dass ich schon an einer sehr frühen Stelle rein rechnerisch ganz schlimmen Blödsinn mache. Vielleicht kann mir ein guter Mensch sagen, ob ich damit auf dem ganz falschen Dampfer bin. Vielen Dank! |
||||||
04.04.2018, 16:37 | rumar | Auf diesen Beitrag antworten » | ||||
kleiner Tipp Um die Aufgabe sofort etwas angenehmer zu gestalten, würde ich stattdessen den Term für alle ganzzahligen mit betrachten. Dieser Term lässt sich sofort deutlich vereinfachen; man muss sich mit weniger Potenzausdrücken rumschlagen. |
||||||
04.04.2018, 16:58 | mrclndr | Auf diesen Beitrag antworten » | ||||
OK, danke! Ich werde das mal probieren. Vorher sollte ich mir wohl eh nochmal die binomischen Gesetze auch für Exponenten größer 2 anschauen... Also meine Lösung ist ja erstmal rechnerisch falsch (ist mir leider etwas zu spät aufgefallen), ich würde mich da nochmal dransetzen und dann hier noch einmal nachhaken. |
||||||
04.04.2018, 17:45 | mrclndr | Auf diesen Beitrag antworten » | ||||
RE: kleiner Tipp
OK, also ich habe jetzt nochmal Folgendes probiert:
Ich bin deshalb langsam mit meinem Latein am Ende (probiere seit vorgestern recht amateurhaft diverse Lösungswege durch) und würde mich über einen Tipp freuen, was der richtige Ansatz sein könnte, um das zu lösen. |
||||||
04.04.2018, 17:59 | Helferlein | Auf diesen Beitrag antworten » | ||||
Ohne mich groß einmischen zu wollen: Was willst Du eigentlich mit dieser komischen Summe? Du musst doch nur zeigen, dass die rechte Summe, bestehend aus drei Summanden mit kubischen Exponenten, durch 9 teilbar ist, d.h. |
||||||
04.04.2018, 19:27 | mrclndr | Auf diesen Beitrag antworten » | ||||
OK, danke, ich komme leider auch damit nicht weiter, weil mein Ansatz wohl einfach nicht passt. Die Summenformel hab ich als Notbehelf angewandt, um irgendeine "Regel" zu haben, wie ich sowohl n als auch n+1 in einen gemeinsamen Induktionsschritt bringen kann. Sonst verstehe ich nämlich nicht, wie ich z.B. den von dir formulierten Ausdruck eben um n+1 erweitere – bzw. worauf genau ich überhaupt als Ergebnis abziele. Meine Bücher sagen, ich nehme A(n) an und beweise unter dieser Annahme, dass auch A(n+1) wahr ist – das Konzept ist klar soweit, auch axiomatisch usw.usf., aber ich scheitere außer in seltenen Ausnahmefällen an diesem letzten, aber doch relativ entscheidenden Schritt. Einer der ganz wenigen Beweise mittels vollständiger Induktion, die mir nicht wie Zauberei vorkamen, hat eben auch mit einer Summenformel gearbeitet. Darum der Versuch. Aber ich werde dann einfach mal schauen, ob ich irgendeine Erklärung der Beweisprinzips finde, die mir einleuchtet; ich denke, da gibt es wohl ein recht grundlegendes Verständnisproblem bei mir. |
||||||
Anzeige | ||||||
|
||||||
04.04.2018, 19:37 | Helferlein | Auf diesen Beitrag antworten » | ||||
Dann mal Schritt für Schritt: Induktionsverankerung:n=1 Es ist Induktionsannahme: Für ein bestimmtest n gilt Induktionsschluß: Die Aussage gilt auch für n+1, d.h. Nutze nun die Annahme, um den Schluß durchzuführen. |
||||||
04.04.2018, 20:40 | mrclndr | Auf diesen Beitrag antworten » | ||||
OK, Knoten geplatzt, glaube ich: Ich habe die Induktionsannahme umgeformt, sodass und damit das aus der Gleichung im Induktionsschritt mit substituiert. Durch Ausrechnen (diesmal sogar unter Beachtung binomischer Formeln) komme ich auf: Dass nach dem Ausrechnen negativ ist, sollte ja kein Problem sein, da wir ja nach wir vor im Bereich sind. Jedenfalls habe ich damit unter Verwendung der Aussage für (von der ich annehme, dass sie durch teilbar ist) gezeigt, dass die Aussage für ebenfalls durch teilbar ist. Oder? Danke auf jeden Fall! So nah war ich bisher noch nicht dran, ich habe da wohl einfach um mehrere Ecken zu viel gedacht. |
||||||
05.04.2018, 00:06 | Helferlein | Auf diesen Beitrag antworten » | ||||
Auch wenn Du dicht an der Lösung dran bist, habe ich meine Zweifel, ob Du die Sache wirklich durchschaut hast. Wo hast Du denn gezeigt, dass existiert und wieso sollte das negativ sein, wo doch laut Induktionsannahme gilt? Für die Teilbarkeit reicht eine ganze Zahl als Teiler aus, aber in diesem Beweis kann es sich nur um positive Teiler handeln. Dein Ziel sollte es sein konkret angeben zu können und aus der Darstellung zu schließen, dass es sich um einen natürliche Zahl handelt. |
||||||
05.04.2018, 09:43 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Kleine Anmerkung:
Der Induktionsanfang (bzw. Induktionsverankerung) sollte daher bei n=0 statt bei n=1 erfolgen. |
||||||
05.04.2018, 14:26 | rumar | Auf diesen Beitrag antworten » | ||||
RE: kleiner Tipp Ich möchte nun doch noch meinen vorgeschlagenen Ansatz zu Ende fführen. Wie schon gesagt, betrachte ich den Term mit dem um 1 verschobenen Index, also Dabei können wir uns auf die N mit beschränken - allerdings klappt eigentlich alles auch schon für n=0 sowie auch für negative Werte. Der Term lässt sich sofort vereinfachen zu: Wegen des schon offensichtlichen Faktors 3 bleibt nur noch zu zeigen, dass im zweiten Faktor noch ein weiterer Faktor 3 steckt. Für diesen Nachweis kann man nun die vollständige Induktion noch einsetzen. Für n=1 ist , also durch 3 teilbar. Sei nun n eine natürliche Zahl, für welche U(n) durch 3 teilbar ist, also mit ganzzahligem k. Dann folgt: D.h. , auch U(n+1) ist wieder durch 3 teilbar, was noch zu zeigen war. |
||||||
05.04.2018, 16:33 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ein möglicher direkter Weg (ohne Induktion) könnte über gehen: a) Von den drei aufeinander folgenden ganzen Zahlen im Produkt ist genau eine durch 3 teilbar, somit auch deren Produkt. b) Auch denkbar ist es, die grundsätzlich geltende Ganzzahligkeit der Binomialkoeffizienten auszunutzen, sofern man diese verwenden darf: Es ist und damit . |
||||||
05.04.2018, 18:40 | mrclndr | Auf diesen Beitrag antworten » | ||||
Ist das das Ergebnis? Damit müsste für jedes ebenfalls sein. Die Teilbarkeit durch 9 ist offensichtlich. Und ist damit der Beweis vollendet, da ich durch Annahme der Wahrheit von n und damit der Wahrheit von auch beweisen konnte, dass es ein wahres gibt? Hab ich das richtig verstanden (und gemacht)? Danke euch, rumar und HAL 9000! Hab eure Vorschläge gelesen und durchgedacht. Würde selber nicht so ohne Weiteres draufkommen. Ich versuch, die Basics dieser Beweisführung zu checken, und bin dann hoffentlich auch irgendwann in der Lage, solche alternativen Wege zu finden. :-) |
||||||
05.04.2018, 19:35 | Helferlein | Auf diesen Beitrag antworten » | ||||
Da ich deiner Argumentation nicht vollständig folgen kann, kann ich Dir leider auch nicht sagen, ob Du das Vorgehen richtig verstanden hast. Ich hätte zum Beispiel nicht die beiden Gleichungen voneinander abgezogen, da die letzte erst noch zu zeigen ist. Ferner kann ich in deiner Argumentation nicht erkennen, wieso "die Teilbarkeit durch 9 offensichtlich ist". Vermutlich beziehst Du Dich auf die . Aber um die geht es an der Stelle doch gar nicht mehr. Ziel war es eine natürliche Zahl anzugeben, für die gilt. Hier noch mal in Reinform, wie ich es gemacht hätte: Es gilt . Mit ist also auch durch 9 teilbar. |
||||||
05.04.2018, 20:41 | mrclndr | Auf diesen Beitrag antworten » | ||||
Du meinst, es ist sauberer, sich wie du der Umformung mit und zu bedienen (und darüber die Induktionsannahme reinzubringen), weil ich damit die Terme der Ausgangsform bzw. der zu beweisenden Form der letzten Gleichung erst einmal "intakt" lasse?
OK – also es passiert da jetzt verkürzt folgendes:
|
||||||
05.04.2018, 21:11 | Helferlein | Auf diesen Beitrag antworten » | ||||
zu 2. Nicht wird als wahr angenommen, sondern die Existenz einer natürlichen Zahl . Der Rest sollte stimmen, wobei ich 4. ziemlich kompliziert ausgedrückt finde. Um zu testen, ob Du es wirklich verstanden hast, kannst Du mit Induktion versuchen zu zeigen, dass stets durch zwei teilbar ist oder alternativ: ist immer durch sechs teilbar. |
||||||
06.04.2018, 13:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Im Zusammenhang mit solchen Teilbarkeitsaussagen zu Polynomen sowie den obigen Überlegungen dazu gilt folgende interessante Aussage:
Die Rückrichtung ist trivial, wirklich interessant ist die Hinrichtung. |
||||||
06.04.2018, 21:38 | mrclndr | Auf diesen Beitrag antworten » | ||||
habe ich, glaube ich, hingekriegt – es kommt heraus, d.h. . Und bei erhalte ich . Da habe ich aufgrund der Brüche kurz überlegt, ob ich einfach so annehmen darf, dass das eine natürliche Zahl wird, aber und einer der Faktoren im Zähler ist definitiv gerade (d.h. durch 2 teilbar, d.h. ich kann den Nenner in jedem Fall wegkürzen). War das wieder mal unnötig kompliziert? ;-) Aber die Lösungen sind richtig, oder? |
||||||
06.04.2018, 22:03 | Helferlein | Auf diesen Beitrag antworten » | ||||
Ich denke jetzt hast Du das Prinzip verstanden. Beides ist richtig gelöst. Abschließend vielleicht noch die Bemerkung, dass Induktion zwar ein schönes Beweisverfahren ist, man aber oft auf direkterem Weg einen Beweis führen kann. Die beiden Beispiele von mir sind direkt beweisbar, wenn man , sowie ausnutzt. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|