Hi zusammen,

ich würde gerne wissen, ob folgender Beweis für Teilbarkeit in N formal korrekt ist:

Beh.: n^3 + 2n ist durch 3 teilbar.

Bew.:

1.) Induktionsanfang: Beh. wahr für n = 1

1^3 + 2 = 3 und 3 teilt 3 ist wahr.


2.) Induktionsvoraussetzung: Beh. sei wahr für n € N.


3.) Induktionsschritt: Beh. wahr für n + 1.

Zu zeigen: a_n+1 = (n+1)^3 + 2(n+1) ist durch 3 teilbar.

= (n+1)*(n+1)^2 + 2n + 2
= n^3 + 3n^2 + 3n + 1 + 2n + 2
mit a_n = n^3 + 2n nach Voraussetzung folgt dann:
a_n+1 = a_n + 3n^2 + 3n + 3
und mit a_n = k * 3 folgt dann:
a_n+1 = 3*k + 3n^2 + 3n + 3

Alle Summanden haben einen Faktor, der durch 3 teilbar ist, also ist a_n+1 auch durch 3 teilbar.


Vielen Dank schon mal für Kommentare / Verbesserungsvorschläge!

Ja, das sieht doch gut aus (nur a_n Notation ist ungewöhnlich)

Ich würde so rechnen:
[img]http://mokrates.de/cgi-bin/texstring?$n%5E3%20+%202n%20=%20n(n%5E2%20+%202)%20=%20n(n%5E2-1)%20+%203n%20=%5C%5C%0A(n-1)%5Ccdot%20n%20%5Ccdot%20(n+1)%20+3n$[/img]
mit zwei Summanden, die durch 3 teilbar sind…

also keine Induktion nötig.
was ist schöner???

gegen profs kann man doch nur verlieren [img]http://www.fb18.de/gfx/24.gif[/img]

Ich würd das mal nicht als Verlust, sondern als Gewinn sehen…

was mache ich denn, wenn ich am ende einen term herausbekomme, dessen summanden alle faktoren haben, die kleiner als der teiler sind?

hat das was mit dieser Aufgabe zu tun?
wenn man etwas falsches rausbekommt muss man seine Rechnung oder seinen Ansatz revidieren,

für genauere Antworten musst du wohl genauere Fragen stellen..

nein, diese aufgabe ist mir vom prinzip her klar.. wenn ich allerdings folgendes beispiel nehme:

Beh.: 9 teilt 4^n + 15n - 1

Dann ist im Induktionsschritt zu zeigen:
9 teilt auch 4^(n+1) + 15(n+1) - 1
= 4 * 4^n + 15n + 15 - 1
= 4^n + 15n - 1 + 3*4^n + 15

Mit der Induktionsvoraussetzung a_n = 4^n + 15n - 1 folgt dann:

a_n+1 = a_n + 3*4^n + 15

bisher richtig? An dieser Stelle weiss ich jetzt nicht mehr weiter..

(ach ja, das hat jetzt auch nix mit der "größerer Summanden" Sache zu tun.. vielleicht erledigt sich meine Frage nach der Lösung dieser Aufgabe… bzw. nachdem ich verstanden habe, wie man sie löst ;-))

nein, diese aufgabe ist mir vom prinzip her klar.. wenn ich allerdings folgendes beispiel nehme:

Beh.: 9 teilt 4^n + 15n - 1

Dann ist im Induktionsschritt zu zeigen:
9 teilt auch 4^(n+1) + 15(n+1) - 1
= 4 * 4^n + 15n + 15 - 1
= 4^n + 15n - 1 + 3*4^n + 15

Mit der Induktionsvoraussetzung a_n = 4^n + 15n - 1 folgt dann:

a_n+1 = a_n + 3*4^n + 15

bisher richtig? An dieser Stelle weiss ich jetzt nicht mehr weiter..

(ach ja, das hat jetzt auch nix mit der "größerer Summanden" Sache zu tun.. vielleicht erledigt sich meine Frage nach der Lösung dieser Aufgabe… bzw. nachdem ich verstanden habe, wie man sie löst ;-))

Diese Aussage
"[img]http://mokrates.de/cgi-bin/texstring?$4%5En+15n-1%5Cequiv%200%20%7B%5Crm%5C%20%20mod%5C%20%7D%209$[/img]"
kann ja nicht bewiesen werden, denn sie stimmt für n=3 schon nicht!

Sorry

Diese Aussage
"[img]http://mokrates.de/cgi-bin/texstring?%244%5En%2B15n-1%5Cequiv%200%20%7B%5Crm%5C%20%20mod%5C%20%7D%209%24[/img]"
kann ja nicht bewiesen werden, denn sie stimmt für n=3 schon nicht!

Sorry

4^3 = 64
15*3 = 45

64+45-1 = 108 = 12*9?

a_n+1 = a_n + 3*4^n + 15

bisher richtig? An dieser Stelle weiss ich jetzt nicht mehr weiter..

einfach weiterrechnen,
nun muss ja 3*4^n+15 durch 9 teilbar sein,
da kannst du ähnlch dem 2. Posting des Threads geschickt addieren und subtrahieren,
so dass die einzelnen Summenanden dann durch 9 teilbar sind

Bsp

n^2 -3 = (n^2 +17 + 4n) -20 - 4n
usw., nach diesem Schema,

ein Teilziel wäre zum Beispiel diese 4^n wegzubekommen,
also vielleicht irgendwoher ein +15 n - 1 reinbauen

Diese Aussage
"[img]http://mokrates.de/cgi-bin/texstring?%244%5En%2B15n-1%5Cequiv%200%20%7B%5Crm%5C%20%20mod%5C%20%7D%209%24[/img]"
kann ja nicht bewiesen werden, denn sie stimmt für n=3 schon nicht!

Sorry

4^3 = 64
15*3 = 45

64+45-1 = 108 = 12*9?

Oh weia, pardon, am Taschenrechner falsch getippt….
Asche auf mein Haupt…
(per Hand nachrechnen wäre besser gewesen…)

ahh jetzt hab ich´s verstanden… vielen dank slater ! !