Hallo!
Ich soll folgende Aufgabe lösen:
Zeige mit vollständiger Induktion: 4^n – 1 ist für alle natürlichen Zahlen n durch 3 teilbar.
Ich habe eigtl wenig Probleme mit der vollst. Ind., aber hier fehlt mir der Ansatz. Ich bräuchte doch wenigstens eine Gleichung/Ungleichung, um das Problem anzugehen. Kann mir jemand einen Tipp geben, wie die aussehen könnte?
Danke im Vorraus!
Lg hunter87
Hallo hunter87,
ich würde sagen, dass man es so machen kann:
Induktionsanfang: n=1 4^1-1 = 3 -> ist durch 3 teilbar.
Induktionsschritt: zeige, dass 4^(k+1)-1=3s ist.
4^(k+1)-1
= 4^k*4-1
= 4*(4^k-1+1)-1
= 4*(4^k-1)+4-1
= 4*(4^k-1)+3
= 4*3s+3
= 3*(4s+1)
das ist immer durch 3 teilbar.
daher ist 4^(k+1)-1 durch 3 teilbar.
nach der vollständigen Induktion ist somit 4^k-1 für alls k aus N durch 3 teilbar.
ich hoffe, dass kann helfen.
Viele grüße
niceday
Guten morgen.
Wenn ich deine Umformung ansehen, habe ich mich mit der Formel wohl undeutlcih ausgedrückt:
(4^n)-1 wäre wohl besser gewesen. Sorry!
Trotdem kann ich teilen deiner Ausarbeitung nicht folgen.
Induktionsanfang: n=1 4^1-1 = 3 -> ist durch 3 teilbar.
Induktionsschritt: zeige, dass 4^(k+1)-1=3s ist.
4^(k+1)-1
= 4^k*4-1
Sorry, aber hier kann ich dir nicht mehr folgen. Wie kommst du von (k+1) auf (k*4)
= 4*(4^k-1+1)-1
Genauso hier: Wie kommst du von (k*4) auf (4^k)
= 4*(4^k-1)+4-1
= 4*(4^k-1)+3
= 4*3s+3
= 3*(4s+1)
das ist immer durch 3 teilbar.
daher ist 4^(k+1)-1 durch 3 teilbar.
nach der vollständigen Induktion ist somit 4^k-1 für alls k
aus N durch 3 teilbar.ich hoffe, dass kann helfen.
Viele grüße
niceday
Danke trotzdem für deine Mühe!
hunter87
Hallo,
4^(k+1)-1
= 4^k*4-1Wie kommst du von (k+1) auf (k*4)
Du darfst um k*4 keine Klammer setzen, weil der Operator ^ stärker bindet als *.
Die fragliche Umformung lautet
4^{k+1} - 1 = 4^k \cdot 4 - 1
und ist genauso richtig wie der Rest der Rechnung:
\begin{eqnarray}
\quad
&=& 4 \cdot (4^k-1+1)-1 \nonumber\
&=& 4 \cdot (4^k-1)+4-1 \nonumber\
&=& 4 \cdot (4^k-1)+3 \nonumber\
&=& 4 \cdot 3s+3 \nonumber\
&=& 3 \cdot (4s+1) \nonumber
\end{eqnarray}
habe ich mich mit der Formel wohl undeutlcih ausgedrückt:
(4^n)-1 wäre wohl besser gewesen.
Das ist von niemandem falsch verstanden worden.
Gruß
Martin
Geht das so?
#1 a0 = 0 und somit durch 3 Teilbar
#2 Nun gehen wir davon aus, dass a(n) durch 3 teilbar ist und muessen fuer die vollstaendige Induktion zeigen, dass auch a(n+1) durch 3 Teilbar ist.
a(n+1) = a(n) * 4 + 3
Da a(n) durch 3 teilbar ist, bleibt auch die neue Zahl a(n)*4 durch 3 teilbar. Und eine durch 3 teilbare Zahl, die um 3 erhoeht wird, bleibt natuerlich auch durch 3 teilbar.
Die laienhafte Ausdrucksweise bitte ich zu entschuldigen.
Ja.
Als Leitfaden bzw. Grundstruktur ist das gut.
Wobei aber dann die Begründung der einzelnen Schritte wieder wie weiter oben aussieht.
Gruß Lutz
Ja, problemlos
Hallo,
daran gibt es nichts zu beanstanden. Es kann aber auch Spaß machen, eine gute Darstellung eines Beweises in mathematischer Symbolsprache auszutüfteln. Das ist oft sogar viel leichter als man vielleicht gedacht hätte. Hier könnte man sich etwa überlegen, den Sachverhalt „die Zahl n ist durch 3 teilbar“ einfach durch \frac{n}{3} \in \Bbb{N} auszudrücken. Eine von vielen möglichen Varianten eines darauf aufbauenden Beweises:
Zunächst definiere ich Ak wie folgt
A_{k} := \frac{4^k - 1}{3}
und rechne anschließend Ak + 1 aus (Zwischenschritte weggelassen):
A_{k+1} = \frac{4^{k+1} - 1}{3} = … = 4 \cdot \frac{4^k - 1}{3} + 1 = 4 : A_k + 1
Nach dieser Vorarbeit ist die Induktion kurz und schmerzlos erledigt:
Ind.anfang:
A_0 = … = 0 \quad\Rightarrow\quad A_0 \in \Bbb{N}
\quad\textnormal{ok!}
Ind.schritt:
A_k \in \Bbb{N}
\quad\Rightarrow\quad
4 A_k + 1 \in \Bbb{N}
\quad\Rightarrow\quad
A_{k+1} \in \Bbb{N}
\quad\textnormal{ok!}
Fertig.
Gruß
Martin
Induktionsschritt (von n auf n + 1):
4^(n+1) - 1 = 4 * 4^n - 1 = 3 * 4^n + 4^n - 1
3 * 4^n ist offensichtlich durch 3 teilbar und 4^n - 1 ist nach Induktionsvorraussetzung durch 3 teilbar. Q. e. d.
Mit freundlichen Grüßen, Tanja
Hallo,
Ich soll folgende Aufgabe lösen:
Zeige mit vollständiger Induktion: 4^n – 1 ist für alle
natürlichen Zahlen n durch 3 teilbar.
Nur spaßeshalber: das ganze geht auch ohne Induktion.
4^n - 1 = (2^n)^2 - 1 = (2^n - 1) * (2^n + 1).
Es ist eine von drei aufeinanderfolgenden Zahlen durch 3 teilbar, also auch eine von 2^n-1, 2^n und 2^n+1. 2^n hat als Primteiler nur die 2, also ist entweder 2^n-1 oder 2^n+1 durch 3 teilbar und damit auch das Produkt.
4^n - 1 ist durch 3 teilbar, wenn 4^n - 1 \mod 3 = 0
4^n - 1 \mod 3
= \prod_{i=1}^n 4 - 1 \mod 3
= ( \prod_{i=1}^n (4\mod 3) - 1 ) \mod 3
= ( \prod_{i=1}^n 1 - 1 ) \mod 3
= 0
Gruß
Diether
Hallo,
Nur spaßeshalber: das ganze geht auch ohne Induktion.
richtig, und ich kann noch einen Weg anbieten: Einfach das Ergebnis ausrechnen! Man muss lediglich darauf kommen, die 3 als 4 – 1 darzustellen, aber dann läuft die Polynomdivision von
(4n – 1) : (4 – 1)
wie geölt. Das Ergebnis ist
4n–1 + 4n–2 + … + 43 + 42 + 4 + 1
und das ist evidenterweise ganzzahlig.
Und noch mehr: Ersetzt man alle Vieren durch irgendeine andere Zahl, bleibt alles richtig. Das bedeutet, dass nicht nur 4n – 1 stets durch 3 teilbar ist, sondern allgemeiner an – 1 für beliebige a stets durch a – 1 teilbar ist (*).
Gruß
Martin
(*) Und der Vollständigkeit halber: Dies wiederum ist nur ein Spezialfall der noch allgemeineren Aussage, dass an – bn stets durch a – b teilbar ist.