Teilbarkeit durch 30 < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:43 Mi 15.05.2013 | | Autor: | M.Rex |
| Aufgabe | | Zeige, dass [mm] n^{5}-n [/mm] durch 30 teilbar ist. |
Hallo ihr
Der Induktionsanfang für n=1 und n=2 und die Ind-Voraussetzung sind schnell gemacht.
Aber im Induktionsschritt kann ich nur den Faktor 5 und den Faktor 2 "bestätigen", um die Teilbarkeit durch 30 zu zeigen, fehlt mir noch der Faktor 3.
[mm] (n+1)^{5}-(n+1)
[/mm]
[mm] =n^{5}+5n^{4}+10n^{3}+10n^{2}+5n+1-n-1
[/mm]
[mm] =[n^{5}-n]+ 5n^{4}+10n^{3}+10n^{2}+5n
[/mm]
Die Eckige Klammer ist nach Induktionsvoraussetzung durch 30 teilbar, ich betrachte nun noch den Restterm.
[mm] 5n^{4}+10n^{3}+10n^{2}+5n
[/mm]
[mm] =5n\cdot(n^{3}+2n^{2}+2n+1)
[/mm]
[mm] =5n\cdot(n+1)\cdot(n^{2}+n+1)
[/mm]
Da entweder n oder n+1 durch 2 teilbar sind, habe ich die 2 und die 5 ja sowieso.
Was ich nun nicht sehe, ist, warum [mm] n^2+n+1 [/mm] für alle [mm] n\in\IN [/mm] durch drei teilbar ist.
Selbst mit einem "neuen" Induktionsbeweis hänge ich da noch fest.
Nehme ich an, dass [mm] n^2+n+1 [/mm] durch drei teilbar ist, bekomme ich:
[mm] (n+1)^{2}+(n+1)+1
[/mm]
[mm] =n^{2}+2n+1+n+1+1
[/mm]
[mm] =n^{2}+3n+3
[/mm]
[mm] n^{2} [/mm] ist aber nicht zwingend durch 3 teilbar.
Selbst mit dem Trick von oben, also herausziehen, klappt das nicht.
Dann würde aus [mm] n^{2}+2n+1+n+1+1 [/mm] nach Umsortieren [mm] [n^{2}+n+1]+2n+2
[/mm]
Die eckige Klammer ist nach I.V wieder teilbar, und ich kann 2n+2 noch zu 2(n+1) zusammenfassen, aber damit habe ich die Teilbarkeit durch drei auch nicht erreicht.
Oder übersehe ich da etwas fundamentales?
Marius
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:04 Mi 15.05.2013 | | Autor: | chrisno |
> ... Aber im Induktionsschritt kann ich nur den Faktor 5 und den
> Faktor 2 "bestätigen", um die Teilbarkeit durch 30 zu
> zeigen, fehlt mir noch der Faktor 3.
>
> [mm](n+1)^{5}-(n+1)[/mm]
> [mm]=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n+1-n-1[/mm]
> [mm]=[n^{5}-n]+ 5n^{4}+10n^{3}+10n^{2}+5n[/mm]
>
> Die Eckige Klammer ist nach Induktionsvoraussetzung durch
> 30 teilbar, ich betrachte nun noch den Restterm.
>
> [mm]5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> [mm]=5n\cdot(n^{3}+2n^{2}+2n+1)[/mm]
> [mm]=5n\cdot(n+1)\cdot(n^{2}+n+1)[/mm]
>
> Da entweder n oder n+1 durch 2 teilbar sind, habe ich die 2
> und die 5 ja sowieso.
>
> Was ich nun nicht sehe, ist, warum [mm]n^2+n+1[/mm] für alle
> [mm]n\in\IN[/mm] durch drei teilbar ist.
Das ist es auch nicht. Probier mal für n=3.
Die Teilbarkeit durch 3 musst Du also aus $[mm]n^{4}+2n^{3}+2n^{2}+n[/mm]herausholen. Wie das geht, sehe ich auf die Schnelle nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:26 Mi 15.05.2013 | | Autor: | M.Rex |
Hallo chrisno
> > ... Aber im Induktionsschritt kann ich nur den Faktor 5 und
> den
> > Faktor 2 "bestätigen", um die Teilbarkeit durch 30 zu
> > zeigen, fehlt mir noch der Faktor 3.
> >
> > [mm](n+1)^{5}-(n+1)[/mm]
> > [mm]=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n+1-n-1[/mm]
> > [mm]=[n^{5}-n]+ 5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> >
> > Die Eckige Klammer ist nach Induktionsvoraussetzung durch
> > 30 teilbar, ich betrachte nun noch den Restterm.
> >
> > [mm]5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> > [mm]=5n\cdot(n^{3}+2n^{2}+2n+1)[/mm]
> > [mm]=5n\cdot(n+1)\cdot(n^{2}+n+1)[/mm]
> >
> > Da entweder n oder n+1 durch 2 teilbar sind, habe ich die 2
> > und die 5 ja sowieso.
> >
> > Was ich nun nicht sehe, ist, warum [mm]n^2+n+1[/mm] für alle
> > [mm]n\in\IN[/mm] durch drei teilbar ist.
> Das ist es auch nicht. Probier mal für n=3.
> Die Teilbarkeit durch 3 musst Du also aus
> $[mm]n^{4}+2n^{3}+2n^{2}+n[/mm]herausholen. Wie das geht, sehe ich
> auf die Schnelle nicht.
Danke für die Antwort, inzwischen haben sich ja Lösungen gefunden.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:31 Do 16.05.2013 | | Autor: | Marcel |
Hallo,
> Die Teilbarkeit durch 3 musst Du also aus
> $[mm]n^{4}+2n^{3}+2n^{2}+n[/mm]herausholen. Wie das geht, sehe ich
> auf die Schnelle nicht.
wer hindert uns daran, einen weiteren Induktionsbeweis einzubauen?
Für [mm] $n=0\,$ [/mm] oder [mm] $n=1\,$ [/mm] passt's.
$n [mm] \to [/mm] n+1$...
(Natürlich hat reverend da die elegantere Methode vorgestellt!)
Gruß,
Marcel
|
|
|
| |
|
Guten Abend,
ich würde das nicht mit Induktion versuchen, das ist meistens zu viel Schreibaufwand.
Die Teilbarkeit durch 5 folgt aus dem kleinen Satz von Fermat.
Für die Teilbarkeit durch 6:
Es ist
[mm] $n^5-n=n\cdot \left(n-1 \right)\cdot \left(n+1\right)\cdot \left(n^2+1\right).$
[/mm]
Warum ist nun [mm] $n\cdot \left(n-1 \right)\cdot \left(n+1\right)$ [/mm] für jedes $n [mm] \in \IN \setminus \lbrace [/mm] 0 [mm] \rbrace$ [/mm] durch 6 Teilbar?
Eine gute Nacht
Blasco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 Mi 15.05.2013 | | Autor: | M.Rex |
Hallo
> Guten Abend,
>
> ich würde das nicht mit Induktion versuchen, das ist
> meistens zu viel Schreibaufwand.
In der Tat ist das meistens so.
>
> Die Teilbarkeit durch 5 folgt aus dem kleinen Satz von
> Fermat.
Daran hatte ich mal gar nicht gedacht.
>
> Für die Teilbarkeit durch 6:
>
> Es ist
> [mm]n^5-n=n\cdot \left(n-1 \right)\cdot \left(n+1\right)\cdot \left(n^2+1\right).[/mm]
>
> Warum ist nun [mm]n\cdot \left(n-1 \right)\cdot \left(n+1\right)[/mm]
> für jedes [mm]n \in \IN \setminus \lbrace 0 \rbrace[/mm] durch 6
> Teilbar?
Weil du in drei aufeinanderfolgenden natürlichen Zahlen je mindestens ein Vielfaches von 2 und von drei hast, na logo 
Da hätte ich auch selber drauf kommen können.
>
> Eine gute Nacht
Danke für die Hilfe und dir auch ne gute Nacht.
> Blasco
Marius
|
|
|
| |
|
Hallo Marius,
der Ansatz von Blasco ist der kürzeste. Besser gehts nicht.
Trotzdem gibts zu Deinem Teilproblem noch eine andere mögliche Antwort:
> Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
>
> Der Induktionsanfang für n=1 und n=2 und die
> Ind-Voraussetzung sind schnell gemacht.
>
> Aber im Induktionsschritt kann ich nur den Faktor 5 und den
> Faktor 2 "bestätigen", um die Teilbarkeit durch 30 zu
> zeigen, fehlt mir noch der Faktor 3.
>
> [mm](n+1)^{5}-(n+1)[/mm]
> [mm]=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n+1-n-1[/mm]
> [mm]=[n^{5}-n]+ 5n^{4}+10n^{3}+10n^{2}+5n[/mm]
>
> Die Eckige Klammer ist nach Induktionsvoraussetzung durch
> 30 teilbar, ich betrachte nun noch den Restterm.
>
> [mm]5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> [mm]=5n\cdot(n^{3}+2n^{2}+2n+1)[/mm]
> [mm]=5n\cdot(n+1)\cdot(n^{2}+n+1)[/mm]
>
> Da entweder n oder n+1 durch 2 teilbar sind, habe ich die 2
> und die 5 ja sowieso.
>
> Was ich nun nicht sehe, ist, warum [mm]n^2+n+1[/mm] für alle
> [mm]n\in\IN[/mm] durch drei teilbar ist.
Andere Vorgehensweise:
[mm] n^4+2n^3+2n^2+n\equiv n^4-n^3-n^2+n=n(n-1)(n^2-1)=(n-1)^2*n*(n+1)\mod{3}
[/mm]
Einer der Faktoren ist also immer durch 3 teilbar.
Herzliche Grüße
reverend
> Selbst mit einem "neuen" Induktionsbeweis hänge ich da
> noch fest.
> Nehme ich an, dass [mm]n^2+n+1[/mm] durch drei teilbar ist, bekomme
> ich:
> [mm](n+1)^{2}+(n+1)+1[/mm]
> [mm]=n^{2}+2n+1+n+1+1[/mm]
> [mm]=n^{2}+3n+3[/mm]
>
> [mm]n^{2}[/mm] ist aber nicht zwingend durch 3 teilbar.
>
>
> Selbst mit dem Trick von oben, also herausziehen, klappt
> das nicht.
> Dann würde aus [mm]n^{2}+2n+1+n+1+1[/mm] nach Umsortieren
> [mm][n^{2}+n+1]+2n+2[/mm]
> Die eckige Klammer ist nach I.V wieder teilbar, und ich
> kann 2n+2 noch zu 2(n+1) zusammenfassen, aber damit habe
> ich die Teilbarkeit durch drei auch nicht erreicht.
>
> Oder übersehe ich da etwas fundamentales?
>
> Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:28 Mi 15.05.2013 | | Autor: | M.Rex |
Hallo reverend
> Hallo Marius,
>
> der Ansatz von Blasco ist der kürzeste. Besser gehts
> nicht.
>
> Trotzdem gibts zu Deinem Teilproblem noch eine andere
> mögliche Antwort:
>
> > Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
> >
> > Der Induktionsanfang für n=1 und n=2 und die
> > Ind-Voraussetzung sind schnell gemacht.
> >
> > Aber im Induktionsschritt kann ich nur den Faktor 5 und
> den
> > Faktor 2 "bestätigen", um die Teilbarkeit durch 30 zu
> > zeigen, fehlt mir noch der Faktor 3.
> >
> > [mm](n+1)^{5}-(n+1)[/mm]
> > [mm]=n^{5}+5n^{4}+10n^{3}+10n^{2}+5n+1-n-1[/mm]
> > [mm]=[n^{5}-n]+ 5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> >
> > Die Eckige Klammer ist nach Induktionsvoraussetzung
> durch
> > 30 teilbar, ich betrachte nun noch den Restterm.
> >
> > [mm]5n^{4}+10n^{3}+10n^{2}+5n[/mm]
> > [mm]=5n\cdot(n^{3}+2n^{2}+2n+1)[/mm]
> > [mm]=5n\cdot(n+1)\cdot(n^{2}+n+1)[/mm]
> >
> > Da entweder n oder n+1 durch 2 teilbar sind, habe ich
> die 2
> > und die 5 ja sowieso.
> >
> > Was ich nun nicht sehe, ist, warum [mm]n^2+n+1[/mm] für alle
> > [mm]n\in\IN[/mm] durch drei teilbar ist.
>
> Andere Vorgehensweise:
> [mm]n^4+2n^3+2n^2+n\equiv n^4-n^3-n^2+n=n(n-1)(n^2-1)=(n-1)^2*n*(n+1)\mod{3}[/mm]
>
> Einer der Faktoren ist also immer durch 3 teilbar.
>
> Herzliche Grüße
> reverend
Danke, irgendwie habe ich Restklassen nie auf dem Zettel, wenn es um Teilbarkeitsbeweise per Induktion gilt.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:36 Mi 15.05.2013 | | Autor: | reverend |
Hallo Marius,
> irgendwie habe ich Restklassen nie auf dem Zettel,
> wenn es um Teilbarkeitsbeweise per Induktion gilt.
Für die Beweistaktik ist es bei solchen Aufgaben fast immer am besten, als erstes Modulrechnung zu versuchen und die Induktion frühestens auf Platz zwei zu verschieben.
Der Vorteil dabei ist oft nicht nur der, dass man etwas "direkt" zeigen kann, sondern dass man zu allgemeine Vermutungen so begrenzen kann, dass sie dann eben nur noch für bestimmte Fälle gelten - aber die kann man dann identifizieren. Das gelingt mit Induktion nur mit viel viel mehr Mühe.
Liebe Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:05 Do 16.05.2013 | | Autor: | Marcel |
Hallo,
hier noch ein anderer Weg (eine kleine Variante von Blasco - bzw. ein
Zusammenwurf, damit das alles elementar bleibt):
> Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
es gilt (wie Blasco schon schrieb)
[mm] $$n^5-n=n*(n^4-1)=n*(n+1)*(n-1)*(n^2+1)\,.$$
[/mm]
Die Teilbarkeit durch [mm] $6\,$ [/mm] ist damit gesichert.
Zur Teilbarkeit durch [mm] $5\,:$
[/mm]
Für [mm] $n=0\,$ [/mm] resp. [mm] $n=1\,$ [/mm] ist alles klar. Im Induktionsschritt $n [mm] \to [/mm] n+1$ nehmen wir
an, dass [mm] $5|n^5-n\,.$
[/mm]
In trivialer Weise gilt
[mm] $$(n+1)^5-(n+1)=(n+1)^5-(n+1)-(n^5-n)+n^5-n\,.$$
[/mm]
Wegen der I.V. müssen wir also nur nachrechnen, dass auch
[mm] $$5\;|\;(n+1)^5-(n+1)-(n^5-n)$$
[/mm]
gilt:
Mit
[mm] $$(n+1)^5-(n+1)-(n^5-n)=(n+1)^5-n-1-n^5+n=\sum_{k=0}^5 [/mm] {5 [mm] \choose k}n^k-n-1-n^5+n$$
[/mm]
[mm] $$=\sum_{k=1}^4 [/mm] {5 [mm] \choose k}n^k$$
[/mm]
ist das aber offensichtlich.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:10 Do 16.05.2013 | | Autor: | M.Rex |
Hallo Marcel
> Hallo,
>
> hier noch ein anderer Weg (eine kleine Variante von Blasco
> - bzw. ein
> Zusammenwurf, damit das alles elementar bleibt):
> > Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
>
> es gilt (wie Blasco schon schrieb)
> [mm]n^5-n=n*(n^4-1)=n*(n+1)*(n-1)*(n^2+1)\,.[/mm]
>
> Die Teilbarkeit durch [mm]6\,[/mm] ist damit gesichert.
>
> Zur Teilbarkeit durch [mm]5\,:[/mm]
> Für [mm]n=0\,[/mm] resp. [mm]n=1\,[/mm] ist alles klar. Im
> Induktionsschritt [mm]n \to n+1[/mm] nehmen wir
> an, dass [mm]5|n^5-n\,.[/mm]
>
> In trivialer Weise gilt
> [mm](n+1)^5-(n+1)=(n+1)^5-(n+1)-(n^5-n)+n^5-n\,.[/mm]
>
> Wegen der I.V. müssen wir also nur nachrechnen, dass auch
> [mm]5\;|\;(n+1)^5-(n+1)-(n^5-n)[/mm]
> gilt:
> Mit
> [mm](n+1)^5-(n+1)-(n^5-n)=(n+1)^5-n-1-n^5+n=\sum_{k=0}^5 {5 \choose k}n^k-n-1-n^5+n[/mm]
>
> [mm]=\sum_{k=1}^4 {5 \choose k}n^k[/mm]
> ist das aber
> offensichtlich.
>
> Gruß,
> Marcel
Danke, die Lösung werde ich mir morgen mal in Ruhe anschauen, wie die anderen Lösungen dann auch.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:16 Do 16.05.2013 | | Autor: | Marcel |
Hallo Marius,
> Hallo Marcel
> > Hallo,
> >
> > hier noch ein anderer Weg (eine kleine Variante von
> Blasco
> > - bzw. ein
> > Zusammenwurf, damit das alles elementar bleibt):
> > > Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
> >
> > es gilt (wie Blasco schon schrieb)
> > [mm]n^5-n=n*(n^4-1)=n*(n+1)*(n-1)*(n^2+1)\,.[/mm]
> >
> > Die Teilbarkeit durch [mm]6\,[/mm] ist damit gesichert.
> >
> > Zur Teilbarkeit durch [mm]5\,:[/mm]
> > Für [mm]n=0\,[/mm] resp. [mm]n=1\,[/mm] ist alles klar. Im
> > Induktionsschritt [mm]n \to n+1[/mm] nehmen wir
> > an, dass [mm]5|n^5-n\,.[/mm]
> >
> > In trivialer Weise gilt
> > [mm](n+1)^5-(n+1)=(n+1)^5-(n+1)-(n^5-n)+n^5-n\,.[/mm]
> >
> > Wegen der I.V. müssen wir also nur nachrechnen, dass
> auch
> > [mm]5\;|\;(n+1)^5-(n+1)-(n^5-n)[/mm]
> > gilt:
> > Mit
> > [mm](n+1)^5-(n+1)-(n^5-n)=(n+1)^5-n-1-n^5+n=\sum_{k=0}^5 {5 \choose k}n^k-n-1-n^5+n[/mm]
>
> >
> > [mm]=\sum_{k=1}^4 {5 \choose k}n^k[/mm]
> > ist das aber
> > offensichtlich.
> >
> > Gruß,
> > Marcel
>
> Danke, die Lösung werde ich mir morgen mal in Ruhe
> anschauen, wie die anderen Lösungen dann auch.
gerne - mit dem "offensichtlich" war ich etwas zu schnell, aber schreibe halt
mal
$${5 [mm] \choose [/mm] 2}={5 [mm] \choose [/mm] 3}$$
aus, dann wird's offensichtlich. (Denn dass in ${5 [mm] \choose [/mm] 1}={5 [mm] \choose [/mm] 4}$ der
Faktor 5 drinsteckt, ist klar!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:21 Do 16.05.2013 | | Autor: | M.Rex |
Hallo Marcel
>
> gerne - mit dem "offensichtlich" war ich etwas zu schnell,
> aber schreibe halt
> mal
> [mm]{5 \choose 2}={5 \choose 3}[/mm]
> aus, dann wird's
> offensichtlich. (Denn dass in [mm]{5 \choose 1}={5 \choose 4}[/mm]
> der
> Faktor 5 drinsteckt, ist klar!)
Das ist in der Tat offensichtlich.
>
> Gruß,
> Marcel
Marius
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:13 Do 16.05.2013 | | Autor: | Marcel |
Hallo nochmal,
> Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
"schlimmste" Induktionsvariante:
Zeige in drei Induktionsbeweisen:
1.Induktionsbeweis: [mm] $2\;\,|\;\,n^5-n$
[/mm]
2.Induktionsbeweis: [mm] $3\;\,|\;\,n^5-n$
[/mm]
3.Induktionsbeweis: [mm] $5\;\,|\;\,n^5-n$
[/mm]
für alle natürlichen [mm] $n\,.$ [/mm] "Aufwändig", aber elementar.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:56 Do 16.05.2013 | | Autor: | Marcel |
Hallo Marius,
> Zeige, dass [mm]n^{5}-n[/mm] durch 30 teilbar ist.
auch nochmal als Hinweis dafür, dass Du Dir solche Aufgaben nicht
zu unübersichtlich gestaltest:
Ich habe ja schon in etwas übertriebener Weise gesagt, dass Du auch einfach
drei Induktionsbeweise hier führen könntest:
1. für die Teilbarkeit durch 2
2. für die Teilbarkeit durch 3
3. für die Teilbarkeit durch 5
Prinzipiell kann man sich, wenn man einen kurzen Blick auf den obigen
Term wirft, auch direkt schon sagen, dass [mm] $n^5-n\,$ [/mm] stets gerade sein wird:
Ist [mm] $n\,$ [/mm] gerade, so ist alles klar, andernfalls ist [mm] $n^5-n$ [/mm] als Differenz zweier
ungerader Zahlen gerade.
Der 1. Induktionsbeweis wäre zwar auch möglich, brauchst Du aber schon
gar nicht. Mit solchen kleinen Überlegungen kannst Du also hier Erkenntnisse
gewinnen, die helfen können, den Induktionsbeweis ein wenig übersichtlicher
zu gestalten.
Die eigentliche Aufgabe oben wäre also, (noch) zu zeigen:
[mm] $$n^5-n\,$$
[/mm]
ist auch (sowohl) durch [mm] $3\,$ [/mm] als auch durch [mm] $5\,$ [/mm] teilbar. Wenn man gar keine Idee
hat, wie gesagt: Beides per Induktion beweisen. Du hast aber eh schon mit
der "Faktorzerlegung" gesehen, dass man sich bei der Aufgabe, wenn einem
nichts besseres einfällt, insgesamt darauf zurückziehen kann, einen Induktionsbeweis
für die Teilbarkeit durch 5 zu führen.
Gruß,
Marcel
|
|
|
|
