Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige: für alle n [mm] \in \IN [/mm] gilt [mm] 3|n^{3}+2n. [/mm] |
Hallöchen,
die obige Aufgabe schreit ja gerade zu nach einer vollständigen Induktion.
induktionsanfang für n=1: [mm] 3|1^{3}+2n
[/mm]
3|3 ist wahre Aussage und somit ist der Induktionsanfang erfüllt.
Induktionsvorrausetzung: [mm] 3|n^{3}+2n [/mm] gilt für alle n [mm] \in \IN.
[/mm]
Induktionsschritt (n [mm] \to [/mm] n+1): [mm] 3|(n+1)^{3}+2(n+1)
[/mm]
[mm] 3|(n^{3}+3n^{2}+3n+1)+(2n+2)
[/mm]
[mm] 3|(n^{3}+2n) [/mm] + [mm] 3(n^{2}+n+1)
[/mm]
nun hatten wir in der Vorlesung die Implikation: a|b und a|c [mm] \Rightarrow [/mm] a|b+c
[mm] 3|(n^{3}+2n) [/mm] stimmt nun nach Vorrausetzung und offensichtlich stimmt auch
[mm] 3|3(n^{2}+n+1) [/mm] da die rechte Seite ein vielfaches von 3 ist.
Ist meine Beweisführung so richtig oder muss ich das anders machen? Über eine Rückmeldung wäre ich sehr dankbar.
LG Schmetterfee
|
|
| |
|
Hallo Schmetterfee,
> Zeige: für alle n [mm]\in \IN[/mm] gilt [mm]3|n^{3}+2n.[/mm]
> Hallöchen,
>
> die obige Aufgabe schreit ja gerade zu nach einer
> vollständigen Induktion.
Aber nicht so laut. Ich wäre da mit Restklassen herangegangen. [mm] n^3+2n\equiv n(n^2+2)\equiv n(n^2\blue{+3n}+2)\equiv [/mm] n(n+1)(n+2) [mm] \mod{3}.
[/mm]
Einer der drei Faktoren n, n+1, n+2 muss [mm] \equiv 0\mod{3} [/mm] sein, und damit auch das Produkt.
> induktionsanfang für n=1: [mm]3|1^{3}+2n[/mm]
> 3|3 ist wahre Aussage und somit ist der Induktionsanfang
> erfüllt.
>
> Induktionsvorrausetzung: [mm]3|n^{3}+2n[/mm] gilt für alle n [mm]\in \IN.[/mm]
Hier ist ein "r" zuviel - Voraussetzung von "voraus", wie daraus, heraus...
> Induktionsschritt (n [mm]\to[/mm] n+1): [mm]3|(n+1)^{3}+2(n+1)[/mm]
> [mm]3|(n^{3}+3n^{2}+3n+1)+(2n+2)[/mm]
> [mm]3|(n^{3}+2n)[/mm] + [mm]3(n^{2}+n+1)[/mm]
>
> nun hatten wir in der Vorlesung die Implikation: a|b und
> a|c [mm]\Rightarrow[/mm] a|b+c
> [mm]3|(n^{3}+2n)[/mm] stimmt nun nach Vorrausetzung und
> offensichtlich stimmt auch
> [mm]3|3(n^{2}+n+1)[/mm] da die rechte Seite ein vielfaches von 3
> ist.
>
> Ist meine Beweisführung so richtig oder muss ich das
> anders machen? Über eine Rückmeldung wäre ich sehr
> dankbar.
Ja, so stimmts. Bis auf die falsche "Voraussetzung".
Grüße
reverend
|
|
|
| |
|
Hallöchen
über Restklassen sieht es wirklich schöner aus. Habe es mittels Induktion gemacht, weil wir Restklassen in der Vorlesung noch nicht definiert haben. Sie sind aus der Linearen Algebra bekannt aber noch nicht in der aktuellen Vorlesung definiert. Deswegen bin ich auf die "umständliche" Induktion ausgewichen.
LG Schmetterfee
|
|
|
| |
|
Hallöchen
Nun soll ich auch noch zeigen, dass [mm] 7|2^{3n}-1 [/mm] für alle n [mm] \in \IN [/mm] gilt.
Ich habe dies mit induktion versucht, lande dann aber an einer Stelle bei
[mm] 7|2^{3n}*2^{3}-1 [/mm] und weiß nun nicht wie ich das umformen kann um zu begründen das das geht. Denn ich weiß ja dass [mm] 7|2^{3n}-1 [/mm] nach Induktionsvoraussetzung gilt. HAt jemand einen Tip für eine Umformung oder muss ich versuchen dies anders zu beweisen?
LG Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> Hallöchen
>
> Nun soll ich auch noch zeigen, dass [mm]7|2^{3n}-1[/mm] für alle n
> [mm]\in \IN[/mm] gilt.
>
> Ich habe dies mit induktion versucht, lande dann aber an
> einer Stelle bei
> [mm]7|2^{3n}*2^{3}-1[/mm] und weiß nun nicht wie ich das umformen
> kann um zu begründen das das geht. Denn ich weiß ja dass
> [mm]7|2^{3n}-1[/mm] nach Induktionsvoraussetzung gilt. HAt jemand
> einen Tip für eine Umformung oder muss ich versuchen dies
> anders zu beweisen?
Nach IV gilt doch für festes [mm]n\in\IN[/mm], dass [mm]7\mid\left(2^{3n}-1\right)[/mm]
Nach der Regel [mm]a\mid b\Rightarrow a\mid(c\cdot{}b)[/mm] folgt mit [mm]c=2^3[/mm]:
[mm]7\mid\left(2^3\cdot{}\left[2^{3n}-1\right]\right)=2^{3(n+1)}-8[/mm]
Weiter mit [mm]a\mid b[/mm] und [mm]a\mid c[/mm] folgt [mm]a\mid(b+c)[/mm] und wegen [mm]7\mid 7[/mm] also
[mm]7\mid\left[\left(2^{3(n+1)}-8\right)+7\right][/mm], dh. [mm]7\mid\left(2^{3(n+1)}-1\right)[/mm]
>
> LG Schmetterfee
Gruß
schachuzipus
|
|
|
| |
|
Hallo nochmal,
schade mit den Restklassen... Es wäre auch bei dieser Aufgabe viel einfacher.
> Nun soll ich auch noch zeigen, dass [mm]7|2^{3n}-1[/mm] für alle n
> [mm]\in \IN[/mm] gilt.
>
> ... [mm]7|2^{3n}*2^{3}-1[/mm] und weiß nun nicht wie ich das umformen
> kann um zu begründen das das geht.
[mm] (x^{3n}*x^3-1) [/mm] ist durch [mm] (x^3-1) [/mm] teilbar. Das gilt für alle [mm] n\in\IN [/mm] und natürlich für alle [mm] x\in\IR, [/mm] z.B. x=2. 
Mach doch mal eine Polynomdivision.
Grüße
reverend
|
|
|
| |
|
Hi rev,
> Hallo nochmal,
>
> schade mit den Restklassen... Es wäre auch bei dieser
> Aufgabe viel einfacher.
Naja, "viel einfacher" halte ich für arg übertrieben. Es werden doch auch im Induktionsbeweis lediglich zwei sehr sehr elementare Teilbarkeitsregeln benutzt ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:27 Do 20.10.2011 | | Autor: | reverend |
Hallo schachuzipus
[mm] 2^{3n}-1\equiv \left(2^3\right)^n-1\equiv 1^n-1\equiv 0\mod{7}
[/mm]
Grüße
reverend
|
|
|
| |
|
Ja, aber "viel einfacher" ist das doch nicht!?
Egal, "schön" ist es auch über die (endl.) geometr. Reihe - wenn ich gerade nicht irre:
Es ist [mm]\sum\limits_{k=0}^{n-1}q^k=\frac{q^n-1}{q-1}[/mm] für alle [mm]n\in\IN[/mm].
Mit [mm]q=2^3[/mm] also [mm]\sum\limits_{k=0}^{n-1}\left(2^3\right)^n=\frac{\left(2^3\right)^n-1}{2^3-1}=\frac{2^{3n}-1}{7}[/mm]
Also [mm]7\cdot{}\underbrace{\sum\limits_{k=0}^{n-1}2^{3n}}_{\in\IN} \ = \ 2^{3n}-1[/mm]
Also [mm]7\mid\left(2^{3n}-1\right)[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:03 Do 20.10.2011 | | Autor: | reverend |
Hallo schachuzipus,
ja, das mit der geometrischen Reihe gefällt mir auch gut!
Und mir kam die Restklassenrechnung schon viel einfacher vor, obwohl Du natürlich Recht hast, dass man da eigentlich nichts anderes tut als auch im Induktionsbeweis. Es ist nur viel weniger Schreib- und Denkarbeit, finde ich.
Herzliche Grüße
reverend
|
|
|
|
