Vollständige Induktion ohne Summenzeichen?
Hi.
Ich habe eine Aufgabenstellung erhalten, wobei ich mit Hilfe der vollständige Induktion das beweisen soll:
3^(2n) - 1 ist für ∀n ∈ ℕ durch 8 ohne Rest teilbar.
Ich habe es zuvor nur mit einem Summenzeichen gemacht und weiß nicht wie es ohne geht.
Kann mir jemand dabei helfen? / Paar Tipps geben?
3 Antworten
Hallo,
Du darfst die Behauptung benutzen.
Du darfst also so tun, als sei bereits bewiesen, daß 3^(2n)-1 durch 8 teilbar wäre.
Natürlich mußt Du durch Nachrechnen zeigen, daß es zumindest für n=1 stimmt:
3^(2*1)-1=9-1=8 und 8 ist ohne Rest durch 8 teilbar.
Damit ist der Induktionsanfang gemacht.
Nun zeigst Du, daß die Behauptung - angenommen, sie sei wahr - auch für n+1 stimmt, daß also 3^(2*(n+1))-1 auch durch 8 teilbar ist.
Dazu wandelst Du diesen Term so um, daß in ihm 3^(2n)-1 vorkommt, denn das soll ja durch 8 teilbar sein.
3^(2(n+1))-1=3^(2n+2)-1=3^2*3^(2n)-1=9*3^(2n)-1.
3^(2n-1) kommt hier schon mal vor, kann aber nicht einfach abgespalten werden, weil die 1 hinten nicht an der 9 hängt.
Darum benutzt Du einen Trick: 9=8+1, daher:
(8+1)*3^(2n)-1=8*3^(2n)+3^(2n)-1.
Nun hast Du eine Summe, deren erster Teil 8*3^(2n) das Achtfache von 3^(2n), einer natürlichen Zahl ist und damit durch 8 teilbar.
Der zweite Teil ist 3^(2n)-1, der ja laut Behauptung auch durch 8 teilbar ist.
Da Du beim Induktionsanfang gezeigt hast, daß 3^(2n)-1 für n=1 durch 8 teilbar ist und beim Induktionsschritt gezeigt hast, daß - wenn es für irgendein n gilt, dann auch für den Nachfolger eines beliebigen n, ist die Behauptung für jedes n gültig, denn daß es für n=1 gilt, hast Du durch Nachrechnen gezeigt. Daß man, setzt man für n den Nachfolger n+1 ein, ebenfalls eine durch 8 teilbare Zahl bekommt, stimmt es auch für n=1+1, also n=2. Stimmt es aber für n=2, stimmt es auch für n=2+1=3 usw. Das kannst Du bis in alle Ewigkeit so weitermachen, also für den Nachfolger vom Nachfolger vom Nachfolger, so daß Du alle möglichen n erwischst.
Herzliche Grüße,
Willy
Als Schüler hatte ich das Prinzip nie richtig kapiert und mich dann irgendwie durchgepfuscht. Erst lange nach dem Abi habe ich dann wirklich begriffen, wie und warum die vollständige Induktion funktioniert und habe seitdem - zumindest mit den üblichen Aufgaben - keine Probleme mehr. Deswegen versuche ich immer, es anderen möglichst einfach zu erklären.
Meine Antwort und Lösung ist im Vergleich zu deiner eher puristisch. Aber vielleicht kann man auch aus dem Vergleich dieser beiden Antworten etwas lernen. Gruß von Littlethought.
Induktionsanfang: n=1
Das ist natürlich durch 8 teilbar.
Induktionsannahme:
Induktionsschritt
Das ist offensichtlich wegen des Faktors 8 vor der Klammer durch 8 teilbar.
q.e.d
Du warst etwas schneller als ich. Wenn deine Antwort schon sichtbar gewesen wäre als ich meine schrieb, hätte ich verzichtet.
Hinweis: [ x mod 8 ] ist der ganzahlige Rest der bei der Division von x durch 8 übrig bleibt.
Beh: [ 3^(2n) - 1] mod 8 = 0 ; <=> [ 3^(2n)] mod 8 =1 ;
Begründung:
Beh. ist wahr für n =1 . (trivial)
Annahme:: Beh. ist wahr für N. => [ 3^(2N)] mod 8 =1 ;
Es ist zu zeigen dass dann die Beh. auch für N+1 wahr ist.
{ 3^[2(N+1) ] } mod 8 = { 9*3^[2N ] } mod 8 = { [9 mod 8] * [ 3^(2N) ] mod 8 } = 1 * 1 .
( 1*1 -1 ) mod 8 = 0 . q.e.d.
So geht's auch. Du hast allerdings einen Tippfehler drin: ([9 mod 8]*3°82N)] mod 8).
Die 82 soll doch sicher (2 bedeuten.
Ja Danke. Das Problem mit der Shift-Taste. Ich korrigiere das noch.
Dachte ich mir schon, da ( und 8 auf derselben Taste liegen. Passiert mir auch nicht selten.
Sehr lieb. Du hast ihm nicht nur die Lösung der Aufgabe sondern das gesamte Verfahren der Induktion erklärt.