Vollständige Induktion

29.09.2008, 20:55

Musti

Auf diesen Beitrag antworten »

Vollständige Induktion

Zeige für alle $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ gilt:

$\begin{eqnarray*} 30 \end{eqnarray*}$ teilt $\begin{eqnarray*} n^5-n \end{eqnarray*}$

Meine Vorgehensweise:

Induktionsanfang: $\begin{eqnarray*} n_0=0 \end{eqnarray*}$

$\begin{eqnarray*} \frac{30}{0^5-0}=\frac{2\cdot 3\cdot 5}{0^5-0}=0 \end{eqnarray*}$

Induktionsanfang richtig, da: $\begin{eqnarray*} 30\cdot 0=2\cdot 3\cdot 5\cdot 0=0 \end{eqnarray*}$

Induktionsvoraussetzung: $\begin{eqnarray*} \forall 0\leq k\geq n \end{eqnarray*}$ gilt: $\begin{eqnarray*} \frac{30}{k^5-k} \end{eqnarray*}$

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{2\cdot 3\cdot 5}{(n+1)^5-(n+1)}=\frac{2\cdot 3\cdot 5}{n^5+5n^4+10n^3+10n^2+5n+1-n-1}=\frac{2\cdot 3\cdot 5}{\underbrace {n^5-n}_{Induktionsvoraussetzung}+5n^4+10n^3+10n^2+5n} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} 5 \end{eqnarray*}$ teilt $\begin{eqnarray*} (n^5-n+5n^4+10n^3+10n^2+5n) \end{eqnarray*}$ , und somit auch das Produkt $\begin{eqnarray*} 2\cdot 3\cdot 5 \end{eqnarray*}$ , da $\begin{eqnarray*} x|a \Rightarrow p|a \end{eqnarray*}$ , $\begin{eqnarray*} q|a \end{eqnarray*}$ und $\begin{eqnarray*} r|a \end{eqnarray*}$ mit $\begin{eqnarray*} x=p\cdot q\cdot r \end{eqnarray*}$ .

Ist das so korrekt?

Danke

29.09.2008, 21:05

tigerbine

Auf diesen Beitrag antworten »

Musst du es mit Induktion machen?

29.09.2008, 21:13

Musti

Auf diesen Beitrag antworten »

Ja es ist strikt vorgegeben... wieso was stimmt denn damit nicht?

29.09.2008, 21:14

tigerbine

Auf diesen Beitrag antworten »

Nein, ist sicher eine Möglichkeit. Wollte nur wissen ob es ein muss ist, oder man es auch mit Modulo versuchen könnte. Augenzwinkern

Augenzwinkern

29.09.2008, 21:17

kiste

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Musti
Zeige für alle $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ gilt:

$\begin{eqnarray*} 30 \end{eqnarray*}$ teilt $\begin{eqnarray*} n^5-n \end{eqnarray*}$

Meine Vorgehensweise:

Induktion muss nicht unbedingt sein da gibt es durchaus schnellere Wege, sprich modulo rechnen

Zitat:

Induktionsanfang: $\begin{eqnarray*} n_0=0 \end{eqnarray*}$

$\begin{eqnarray*} \frac{30}{0^5-0}=\frac{2\cdot 3\cdot 5}{0^5-0}=0 \end{eqnarray*}$

Das sieht total schrecklich aus. Du hast sogar durch 0 geteilt!
$\begin{eqnarray*} 30 \end{eqnarray*}$ teilt $\begin{eqnarray*} n^5-n \end{eqnarray*}$ heißt nichts anderes als dass $\begin{eqnarray*} \frac{n^5-n}{30} \in \mathbb N \end{eqnarray*}$ ist und nicht andersrum!

Zitat:

Induktionsanfang richtig, da: $\begin{eqnarray*} 30\cdot 0=2\cdot 3\cdot 5\cdot 0=0 \end{eqnarray*}$

stimmt, warum du allerdings 30 noch als Produkt von Primfaktoren geschrieben hast ist mir ein Rätsel. Unnötig!

Zitat:

Induktionsvoraussetzung: $\begin{eqnarray*} \forall 0\leq k\geq n \end{eqnarray*}$ gilt: $\begin{eqnarray*} \frac{30}{k^5-k} \end{eqnarray*}$

Was gilt? Ein Term ist keine Aussage. Außerdem hast du wieder Nenner und Zähler vertauscht.

Zitat:

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{2\cdot 3\cdot 5}{(n+1)^5-(n+1)}=\frac{2\cdot 3\cdot 5}{n^5+5n^4+10n^3+10n^2+5n+1-n-1}=\frac{2\cdot 3\cdot 5}{\underbrace {n^5-n}_{Induktionsvoraussetzung}+5n^4+10n^3+10n^2+5n} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} 5 \end{eqnarray*}$ teilt $\begin{eqnarray*} (n^5-n+5n^4+10n^3+10n^2+5n) \end{eqnarray*}$ , und somit auch das Produkt $\begin{eqnarray*} 2\cdot 3\cdot 5 \end{eqnarray*}$ , da $\begin{eqnarray*} x|a \Rightarrow x|(a\cdot b) \end{eqnarray*}$ gilt.

Das Argument verstehe ich nicht. Aber du kannst es sicher nochmal versuchen wenn Nenner und Zähler vertauscht sind(dann lässt sich auch wirklich die Vorraussetzung anwenden)

Zitat:

Ist das so korrekt?

Nein

Augenzwinkern

29.09.2008, 21:20

Musti

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Ohh du meine Güte, klar ich muss Nenner und Zähler immer vertauschen sorry... aber sonst müsste es doch stimmen oder?

Ich hab die 30 in Primfaktoren zerlegt, weil mein Prof. es uns als Tipp mitgegeben hat und am Ende steht dann auch die Begründung.

Modulo rechnen sollen wir hier aber nicht, wir sollen das mit vollständiger Induktion machen.

Anzeige

29.09.2008, 21:24

kiste

Auf diesen Beitrag antworten »

Du hast im Induktionsschritt dann trotzdem nur durch 5 teilbar gezeigt. Durch 2 und durch 3 teilbar fehlt dann noch, zusammen mit der Begründung warum man nur diese 3 Zahlen testen muss Augenzwinkern

Augenzwinkern

29.09.2008, 21:27

Musti

Auf diesen Beitrag antworten »

Es ist doch allgemein so, dass wenn:

$\begin{eqnarray*} x=p\cdot q \end{eqnarray*}$ , $\begin{eqnarray*} p\neq q \end{eqnarray*}$ Primzahlen, $\begin{eqnarray*} p,q\geq 2 \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} x|y \Leftrightarrow p|y \end{eqnarray*}$ und $\begin{eqnarray*} q|y \end{eqnarray*}$ reicht das nicht als Begründung?

29.09.2008, 21:30

kiste

Auf diesen Beitrag antworten »

Wenn du das vorraussetzen darfst ja.

29.09.2008, 21:32

Musti

Auf diesen Beitrag antworten »

Ja ich darf das voraussetzen.
Wie würde man es denn machen wenn man es nicht voraussetzen darf?
Und was meinst du und Tigerbine eigentlich mit modulo rechnen?

29.09.2008, 21:37

kiste

Auf diesen Beitrag antworten »

Direkt durch 30 teilbar beweisen oder eben das Lemma kurz beweisen.

Mit modulo geht das schnell:
$\begin{eqnarray*} n^5 - n \equiv 0 ~(30) \leftrightarrow n^5 - n \equiv 0 ~(5) \wedge n^5 - n \equiv 0 ~(3) \wedge n^5 - n \equiv 0 ~(2) \end{eqnarray*}$ .
Das erste ist der kleine Satz von Fermat, die anderen beiden kann man durch einsetzen von n=0,1 bzw. n=0,1,2 zeigen.

Schreibe am besten deinen Induktionsbeweis wenn er fertig ist nochmal schön hier hin. Du scheinst einige Probleme mit dem aufschreiben zu haben

29.09.2008, 21:52

Musti

Auf diesen Beitrag antworten »

Also ok ich versuche es nochmal von neu.

Induktionsanfang: $\begin{eqnarray*} n_0=0 \end{eqnarray*}$

$\begin{eqnarray*} A(0)=\frac{0^5-0}{30}=\frac{0^5-0}{2\cdot 3\cdot 5} =0 \end{eqnarray*}$ ist richtig, da $\begin{eqnarray*} 30\cdot 0=0 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} \exists m\in N \end{eqnarray*}$ mit $\begin{eqnarray*} 30m=n^5-n \end{eqnarray*}$

Induktionsvoraussetzung: $\begin{eqnarray*} \forall n_0\leq k \geq n \end{eqnarray*}$ ist $\begin{eqnarray*} A(k) \end{eqnarray*}$ wahr.

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{(n+1)^5-(n+1)}{2\cdot 3\cdot 5}=\frac{n^5+5n^4+10n^3+10n^2+5n+1-n-1}{2\cdot 3\cdot 5}=\frac{n^5-n+5n^4+10n^3+10n^2+5n}{2\cdot 3\cdot 5} \end{eqnarray*}$ , wegen $\begin{eqnarray*} \frac{n^5-n}{2\cdot 3\cdot 5} \end{eqnarray*}$ gilt: $\begin{eqnarray*} 5 \end{eqnarray*}$ teilt $\begin{eqnarray*} n^5-n+5n^4+10n^3+10n^2+5n \end{eqnarray*}$

Ferner gilt: $\begin{eqnarray*} x=p\cdot q \end{eqnarray*}$ , $\begin{eqnarray*} p\neq q \end{eqnarray*}$ Primzahlen, $\begin{eqnarray*} p,q\geq 2\Rightarrow x|y \Leftrightarrow x|p \end{eqnarray*}$ und $\begin{eqnarray*} x|q \end{eqnarray*}$ .

Somit gilt: $\begin{eqnarray*} (n^5-n+5n^4+10n^3+10n^2+5n)|(2\cdot 3\cdot 5) \end{eqnarray*}$

Hoffe das ist jetzt korrekt so verwirrt

verwirrt

Letzten Teil habe ich wieder vertauscht:S

29.09.2008, 22:01

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von Musti
Induktionsvoraussetzung: $\begin{eqnarray*} \forall n_0\leq k \geq n \end{eqnarray*}$ ist $\begin{eqnarray*} A(k) \end{eqnarray*}$ wahr.

Du meinst $\begin{eqnarray*} \forall k: n_0\leq k \leq n : A(k) \end{eqnarray*}$

Zitat:

wegen $\begin{eqnarray*} \frac{n^5-n}{2\cdot 3\cdot 5} \end{eqnarray*}$ gilt: $\begin{eqnarray*} 5 \end{eqnarray*}$ teilt $\begin{eqnarray*} n^5-n+5n^4+10n^3+10n^2+5n \end{eqnarray*}$

$\begin{eqnarray*} \frac{n^5-n}{2\cdot 3\cdot 5} \end{eqnarray*}$ ist ein Term keine Aussage, deswegen kannst du auch nicht wegen Term gilt blabla sagen.
Besser:
$\begin{eqnarray*} \frac{n^5-n+5n^4+10n^3+10n^2+5n}{2\cdot 3\cdot 5} = \frac{n^5-n}{2\cdot 3\cdot 5} +\frac{5n^4+10n^3+10n^2+5n}{2\cdot 3\cdot 5} \end{eqnarray*}$ . Für den ersten Term kannst du jetzt IV benutzen.

Zitat:

Ferner gilt: $\begin{eqnarray*} x=p\cdot q \end{eqnarray*}$ , $\begin{eqnarray*} p\neq q \end{eqnarray*}$ Primzahlen, $\begin{eqnarray*} p,q\geq 2\Rightarrow x|y \Leftrightarrow x|p \end{eqnarray*}$ und $\begin{eqnarray*} x|q \end{eqnarray*}$ .

Erkläre wo du das benutzt. Etwas wie: "Da ... gilt zeigen wir nur die Teilbarkeit durch 2,3,5 seperat.

Zitat:

Somit gilt: $\begin{eqnarray*} (n^5-n+5n^4+10n^3+10n^2+5n)|(2\cdot 3\cdot 5) \end{eqnarray*}$

Du willst aber zeigen $\begin{eqnarray*} 30 | (n^5-n+5n^4+10n^3+10n^2+5n) \end{eqnarray*}$ bzw. nach obiger Überlegung nur noch $\begin{eqnarray*} 30 | (5n^4+10n^3+10n^2+5n) \end{eqnarray*}$ . Gezeigt hast du allerdings erst den Faktor 5! 2 und 3 fehlen immer noch

29.09.2008, 22:04

Musti

Auf diesen Beitrag antworten »

Hmm danke für die Verbesserung der Schreibweise, aber um ehrlich zu sein wüsste ich nicht wie ich das für 2 und 3 zeige unglücklich

unglücklich

29.09.2008, 22:18

kiste

Auf diesen Beitrag antworten »

Für 2 ist es einfach, da musst du nur faktorisieren, für 3 fällt mir gerade auch nichts elementares ein.

30.09.2008, 20:26

Musti

Auf diesen Beitrag antworten »

Für 3 habe ich es auch glaube ich?!

Es gilt ja: $\begin{eqnarray*} 30|n^5-n\Leftrightarrow 2|n^5-n \end{eqnarray*}$ , $\begin{eqnarray*} 3|n^5-n \end{eqnarray*}$ und $\begin{eqnarray*} 5|n^5-n \end{eqnarray*}$ .

Nun schreibe ich den Term $\begin{eqnarray*} n^5-n \end{eqnarray*}$ folgendermaßen um:

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

Nun gilt für den Induktionsschritt:
$\begin{eqnarray*} (n+1)^5-(n+1)=(n+1)\cdot (n+2)\cdot n\cdot (n^2+2) \end{eqnarray*}$

So jetzt gilt, da $\begin{eqnarray*} 2|(n\cdot (n+1))\Rightarrow 2|((n+1)^5-(n+1)) \end{eqnarray*}$ .

Weiter gilt, da $\begin{eqnarray*} 3|(n-1) \end{eqnarray*}$ und somit $\begin{eqnarray*} 3|(n^5-n)\Rightarrow 3|(n+2)\Rightarrow 3|((n+1)^5-(n+1)) \end{eqnarray*}$

Kann man das so machen?

30.09.2008, 20:37

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Musti
Es gilt ja: $\begin{eqnarray*} 30|n^5-n\Leftrightarrow 2|n^5-n \end{eqnarray*}$ , $\begin{eqnarray*} 3|n^5-n \end{eqnarray*}$ und $\begin{eqnarray*} 5|n^5-n \end{eqnarray*}$ .

Nun schreibe ich den Term $\begin{eqnarray*} n^5-n \end{eqnarray*}$ folgendermaßen um:

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

Ehrlich: Wenn du soweit bist, warum dann überhaupt noch Induktion? Die Teilbarkeit durch 2 und 3 ist der Produktdarstellung sofort anzusehen, und die durch 5 ist auch kein großes Problem: Entweder über Fallunterscheidung, oder noch etwas eleganter über

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

30.09.2008, 23:32

Musti

Auf diesen Beitrag antworten »

Ja das frage ich mich auch, aber die Aufgabe sollte dazu dienen Induktion zu üben.
Danke für den eleganten Weg

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »