Vollständige Induktion Teilbarkeit

23.04.2011, 23:41

Boban

Vollständige Induktion Teilbarkeit

Meine Frage:
Hallo,
verbringe jetzt bereits mehr als 2 Stunden mit der Lösung dieser Aufgabe, komme jedoch leider nicht weiter.

Aufgabenstellung:
Zeigen Sie mit vollständiger Inuduktion:

Für
$\begin{eqnarray*} n\in \mathbb N gilt: 7^{2n+1}-7 \end{eqnarray*}$ ist durch 6 teilbar

Noch dazu gesagt sei dass die Menge N inkl 0 gemeint ist.

Meine Ideen:
So bisher bin ich soweit gekommen:

Induktionsanfang: A(0)
$\begin{eqnarray*} 7^{1} -7= 0 \end{eqnarray*}$
--> ist durch 6 teilbar, also wahr.

Induktionsschritt: A(k)=>A(k+1)

Induktionsvoraussetzung:
$\begin{eqnarray*} 7^{1} -7= 0 \end{eqnarray*}$ ist durch 6 teilbar

Induktionsbehauptung:
$\begin{eqnarray*} 7^{2(k+ 1)+1} -7 \end{eqnarray*}$ ist durch 6 teilbar

Beweis:
$\begin{eqnarray*} =7^{2k+4} -7 = 7^{4} * 7^{2k} -7 \end{eqnarray*}$

$\begin{eqnarray*} = 2401 * 7^{2k} -7 \end{eqnarray*}$
So 2400 ist ja mal durch 6 teilbar.
$\begin{eqnarray*} 7^{2k+1} \end{eqnarray*}$ ja laut Induktionsvoraussetzung auch. Doch was mache ich jetzt mit dem Rest? Oder bin ich auf der komplett falschen Spur?

Vielen Danke schonmal im Voraus und schöne Ostern smile

24.04.2011, 00:09

lgrizu

Auf diesen Beitrag antworten »

RE: Vollständige Induktion Teilbarkeit

Zitat:

Original von Boban

Induktionsvoraussetzung:
$\begin{eqnarray*} 7^{1} -7= 0 \end{eqnarray*}$ ist durch 6 teilbar

Die Vorraussetzung ist falsch, sie sollte sein: $\begin{eqnarray*} 6|(7^{2n+1}-7) \end{eqnarray*}$ .

Zitat:

Original von Boban

Induktionsbehauptung:
$\begin{eqnarray*} 7^{2(k+ 1)+1} -7 \end{eqnarray*}$ ist durch 6 teilbar

Wieso die Unterscheidung zwischen Behauptung und Vorraussetzung?

Zitat:

Original von Boban
Beweis:
$\begin{eqnarray*} =7^{2k+4} -7 = 7^{4} * 7^{2k} -7 \end{eqnarray*}$

Wo kommt denn hier die 4 her? verwirrt

Da gilt $\begin{eqnarray*} 6|(7^{2n+1}-7) \end{eqnarray*}$ muss $\begin{eqnarray*} 7^{2n+1} \equiv 1 \mod 6 \end{eqnarray*}$ sein, es ist also zu zeigen, dass dann auch $\begin{eqnarray*} 7^{2(n+1)+1} \equiv 1 \mod 6 \end{eqnarray*}$ ist.

24.04.2011, 00:38

Boban

Auf diesen Beitrag antworten »

Okay vielen vielen Dank erstmal, für die Hilfe, ich versuche es nochmals.
Warum die Unterscheidung zwischen IB und IV kann ich nicht sagen smile

Mein Lehrer hat uns ein Ablaufschema gegeben nach der wir jede vollständige Induktion abarbeiten sollen. Die 4 kam daher dass ich den Exponenten falsch aufgelöst hatte und Punkt vor Strich nicht beachtet hatte smile

Induktionsvoraussetzung:
$\begin{eqnarray*} 6|7^{2k+1}-7 \end{eqnarray*}$

Induktionsbehauptung:
$\begin{eqnarray*} 6|7^{2(k+1)+1}-7 \end{eqnarray*}$

Beweis:
$\begin{eqnarray*} = 7^{2k+2+1}-7 = 7^{2k+3}-7 =7^{2k} * 7^{3} -7 \end{eqnarray*}$
Nun weiß ich aber nicht weiter. Wenn ich es richtig verstanden habe, sollte ich jetzt den Ausdruck so umformen, dass ein Teil des Ausdrucks gleich der Induktionsvoraussetzung ist. Dann kann ich sagen, dass dieser Teil schon mal durch 6 teilbar ist, da die IV dies auch ist. Den Rest muss ich dann durch Ausklammern,... umformen bis er auch zeigt dass er durch 6 teilbar ist. Ist das so richtig? Doch wie geht es jetzt hier weiter?

Danke smile

24.04.2011, 09:41

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von Boban
Beweis:
$\begin{eqnarray*} = 7^{2k+2+1}-7 = 7^{2k+3}-7 =7^{2k} * 7^{3} -7 \end{eqnarray*}$

Ich würde folgende Umformung wählen: $\begin{eqnarray*} 7^{2k+1} \cdot 7^2 -7 \end{eqnarray*}$ .

Die Induktionsvorraussetzung ist nun $\begin{eqnarray*} 7^{2k+1} -7 \end{eqnarray*}$ ist durch 6 teilbar.

Wir formulieren das einmal um und betrachten die Division mit Rest durch 6.

Wir wissen, dass 7 bei Division durch 6 den Rest 1 hinterlässt, wenn dann also $\begin{eqnarray*} 7^{2k+1} -7 \end{eqnarray*}$ durch 6 teilbar ist, so muss auch $\begin{eqnarray*} 7^{2k+1} \end{eqnarray*}$ bei Division durch 6 den Rest 1 hinterlassen.

Wir betrachten also die Induktionsvorraussetzung, dass $\begin{eqnarray*} 7^{2k+1} \end{eqnarray*}$ bei Division durch 6 den Rest 1 hinterlässt und schauen uns einmal den Ausdruck $\begin{eqnarray*} 7^{2k+1} \cdot 49 \end{eqnarray*}$ an, welchen Rest hinterlässt dieser bei Division durch 6 ?

24.04.2011, 10:41

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von lgrizu
Wir betrachten also die Induktionsvorraussetzung, dass $\begin{eqnarray*} 7^{2k+1} \end{eqnarray*}$ bei Division durch 6 den Rest 1 hinterlässt und schauen uns einmal den Ausdruck $\begin{eqnarray*} 7^{2k+1} \cdot 49 \end{eqnarray*}$ an, welchen Rest hinterlässt dieser bei Division durch 6 ?

Ich denke, du bringst da "in versteckter Form" dann doch wieder Moduloarithmetik ins Spiel, was aber der Intention des Beispiels nicht angemessen ist, denn unter Benützung von

$\begin{eqnarray*} 7 \equiv 1 \mod 6 \end{eqnarray*}$

wäre die Aufgabe ja von allem Anfang an trivial gewesen...

Von daher erscheint es mir logischer, für den Induktionsschluss folgendermaßen zu argumentieren

$\begin{eqnarray*} 7^{2(k+1)+1}-7=7^{2k+1}\cdot 7^2-7=(7^{2k+1}-7)7^2+(7^3-7)=\ldots \end{eqnarray*}$

da dann die Induktionsvoraussetzung in direkter Form eingeht...

24.04.2011, 11:05

riwe

Auf diesen Beitrag antworten »

wäre das eine möglichkeit verwirrt

$\begin{eqnarray*} 7^{2n+1}-7=7(7^{2n}-1) \end{eqnarray*}$
......

für n+1 folgt damit

$\begin{eqnarray*} 7^{2n+1}-1=7(7^{2n}-1)+7-1 \end{eqnarray*}$

24.04.2011, 11:33

Mystic

Auf diesen Beitrag antworten »

@riwe

Geht natürlich auch, wenngleich das dann mit einem ganz kleinen Umweg verbunden ist... Viele Wege (oder waren's sogar alle?) führen nach Rom!... Augenzwinkern

Ist überhaupt eine seltsame Aufgabe, wenn ich mir das hier noch als Randbemerkung erlauben darf, denn einerseits gilt das ja nicht nur für ungerade Zahlen, sondern für beliebige natürliche Zahlen im Exponenten, andererseits wäre das in Modularithmetik die triviale Aussage, dass Potenzen von 1 mod 6 wieder 1 ergeben...

24.04.2011, 14:01

Boban

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

Zitat:

Super, vielen Dank, damit bin ich ans Ziel gekommen smile

Vielen Vielen Dank für eure Hilfe und noch einen schönen Ostersonntag.

Neue Frage »

Antworten »

Vollständige Induktion Teilbarkeit

Verwandte Themen