Beweis durch vollständige Induktion

Zahnkoloss

Mächtiger Krieger
Mitglied seit
17.10.2007
Beiträge
133
So ich hab auch mal nen Problem in Mathe.
Ich muss folgendes durch vollständige Induktion beweisen:
n³+(n+1)³+(1+2)³ ist durch 9 teilbar

Also erstmal der Induktionsanfang
IA: n=1 1³+(1+1)³+(1+2)³=36
36 => teilbar durch 9 w.A.

IV: n=k k³+(k+1)³+(k+2)³ ist durch 9 teilbar
bis hierher kein Problem, jedoch bin ich mir nicht sicher ob ich jetzt die Induktionsbehauptung richtig aufstelle

IB: n=k+1 (k+1)³+((k+1)+1)³+((k+1)+2)³

IBew.: (k+1)³+((k+1)+1)³+((k+1)+2)³
Jetzt habe ich versucht alle Klammern aufzulösen und komme auf:
k³+3k²+3k+1+k³+6k²+8k+8+k³+9k²+27k+27
Ich bin mir nicht sicher ob ich die Klammern richtig aufgelöst habe.
Hier hänge ich jetzt fest. Wenn ich das zusammenfasse komme ich auf 3k³+18k²+38k+36 was mir jedoch auch nicht weiter hilft. Ich denke das ich jetzt irgendwie etwas bei der oberen Gleichung ausklammern muss jedoch weiss ich nicht was und auch nicht wie da ich das mit dem Ausklammern noch nie verstanden hab(und sowas ist im Mathe LKXD)
Bin dankbar über jede Art von Hilfe
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Bis dahin ist das, bis auf einen Rechenfehler drin, alles korrekt. ((k+2)^3 = k^3 + 6k^2 + 12k + 8)
Nun musst du irgendwie deine IV benutzen.
In diesem Fall geht das noch recht einfach, denn du kannst ja schreiben:

(k+1)^3 + (k+2)^3 + (k+3)^3
= (k+1)^3 + (k+2)^3 + k^3 + 9k^2 + 27k + 27
= k^3 + (k+1)^3 + (k+2)^2 + 9k^2 + 27k + 27

Von dem roten Teil weißt du, dass er durch 9 teilbar ist, denn das ist deine IV.
Eine Summe von Zahlen ist durch 9 teilbar, wenn ihre einzelnen Summanden alle durch 9 teilbar sind.

Wir müssen also noch zeigen, dass der blaue Teil durch 9 teilbar ist:
9k^2 + 27k + 27
= 9*(k^2 + 3k + 3)

Wir können es also in ein Produkt aus 9 und einer anderen ganzen Zahl schreiben, und damit ist der blaue Teil durch 9 teilbar.

Damit ist die Behauptung bewiesen.

Wenn dir das zu schnell ging, oder du gern mehr zur Induktion erfahren möchtest, dann sag einfach Bescheid. :)
 
Zuletzt bearbeitet:
OP
OP
Zahnkoloss

Zahnkoloss

Mächtiger Krieger
Mitglied seit
17.10.2007
Beiträge
133
Erstmal vielen Dank. Den unteren Teil hab ich verstanden. Jetzt hab ich nur noch 2 Fragen:

Bis dahin ist das, bis auf einen Rechenfehler drin, alles korrekt. ((k+2)^3 = k^3 + 6k^2 + 12k + 8)
Woher kommt das = ?
Wie bist du auf diese Gleichung gekommen?
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Dafür braucht man Binomialkoeffizienten:

(a + b)^n = (n über 0) * a^n * b^0 + (n über 1) * a^(n-1) * b^1 + (n über 2) * a^(n-2) * b^2 + ... + (n über n-1) * a^(n-(n-1)) * b^(n-1) + (n über n) * a^0 * b^n

Dieser Teil ist auch als "höhere binomische Formel" bekannt.

Du kannst dir die auch mit dem Pascalschen Dreieck bauen:
Code:
         1
        1 1
       1 2 1
      1 3 3 1
     1 4 6 4 1
usw..
Immer die beiden Zahlen diagonal darüber addieren.
Die erste Zeile hast du als Koeffizienten für (a + b)^0 = 1*1
Die zweite Zeile für (a + b)^1 = 1*a + 1*b
Die dritte Zeile für (a + b)^2 = 1*a^2 + 2*a*b + 1*b^2
Die vierte Zeile für (a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3
usw.

Den Trick bzw. die Formel würde ich mir so merken.
Wenn du die mal ausrechnen sollst:
Am TR ist (n über k) getippt:
"n" "nCr" "k"

Damit sollte es klappen.
 
Zuletzt bearbeitet:
OP
OP
Zahnkoloss

Zahnkoloss

Mächtiger Krieger
Mitglied seit
17.10.2007
Beiträge
133
Wir müssen also noch zeigen, dass der blaue Teil durch 3 teilbar ist:
9k^2 + 27k + k
= 3*(3k^2 + 9k + 9)

Wir können es also in ein Produkt aus 3 und einer anderen ganzen Zahl schreiben, und damit ist der blaue Teil durch 3 teilbar.
Ich muss aber eigentlich beweisen das es durch 9 teilbar ist :p
Kann ich dann stattdessen
9*(k²+3k+3)
schreiben?
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Ah, entschuldige. Das hatte ich nicht richtig gelesen, ich hab da eine 3 gesehen.
Aber ja, die 9 ausklammern ist korrekt.
Dann hast du ein Produkt aus zwei ganzen Zahlen, von denen eine die 9 ist. Damit ist der Term durch 9 teilbar, und deine Aussage bewiesen.
Ich editiere grad mal meine bisherigen Posts, damit andere das nachher besser nachvollziehen können.
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Mit Sicherheit.
Mit (1+2)^2 funktioniert es nicht, darum bin ich einfach mal davon ausgegangen. ;)
 
OP
OP
Zahnkoloss

Zahnkoloss

Mächtiger Krieger
Mitglied seit
17.10.2007
Beiträge
133
Ok wie ich das auf teilbarkeit prüfe bekomm ich jetzt hin.
Aber wie mach ich das bei sowas:
1²+2²+3³+...+n²=1/6*n(n+1)(2n+1) ?

Den IA bekomm ich noch hin:
n=1 1²= 1/6*1(1+1)(2*1+1)
1=1 w.A.

Ab hier bin ich mir nicht mehr sicher
IV: n=k 1²= 1/6*k(k+1)(2k+1)

IB: n=k+1 1²= 1/6*(k+1)((k+1)+1)(2(k+1)+1)

IBew.:
1²= 1/6*(k+1)((k+1)+1)(2(k+1)+1)
1²= 1/6k+1/6*(k+2)(2k+3)

Wär toll wenn mir jemand sagen könnte wie es weitergeht und ob ich irgendwo einen Fehler gemacht habe. Mir kommt die Induktionsvoraussetzung nen bisschen komisch vor.
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Dein Induktionsanfang ist korrekt.
Deine Induktionsvoraussetzung ist ebenfalls prima so.

Also:
IV: n=k: 1^2 + 2^2 + 3^2 + ... + k^2 = 1/6 * k * (k+1) * (2k+1)

Nun musst du zeigen:
IS: n=k+1:
1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = 1/6 * (k+1) * (k+2) * (2*(k+1) + 1)

Du weißt bereits, dass:
1^2 + 2^2 + 3^2 + ... + k^2 = 1/6 * k * (k+1) * (2k+1) ist.
Also würde ich in deinem IS genau das auch schreiben.

1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = 1/6 * k * (k+1) * (2k+1) + (k+1)^2

Wir haben hier also die IV genutzt.

Jetzt müssen wir noch zeigen, dass:
1/6 * k * (k+1) * (2k+1) + (k+1)^2 = 1/6 * (k+1) * (k+2) * (2*(k+1) + 1) ist (ich nenne das hier mal Gleichung I).
Ausmultiplizieren rechts gibt:
1/6*(k^2 + 3k + 2)*(2k + 3) = 1/6 * (2k^3 + 6k^2 + 4k + 3k^2 + 9k + 6) = 1/6*(2k^3 + 9k^2 + 13k + 6)

Ausmultiplizieren links gibt:
1/6 * k * (k+1) * (2k+1) + (k+1)^2 = 1/6*(k^2 + k)*(2k+1) + (k^2 + 2k + 1) = 1/6*(2k^3 + 2k^2 + k^2 + k) + (k^2 + 2k + 1)
Jetzt in der rechten Klammer 1/6 ausklammern:
=1/6*(2k^3 + 2k^2 + k^2 + k) + 1/6*(6k^2 + 12k + 6) = 1/6*(2k^3 + 2k^2 + k^2 + k + 6k^2 + 12k + 6) = 1/6*(2k^3 + 9k^2 + 13k + 6)

Damit sind die linke und rechte Seite von Gleichung I sind also gleich, und damit ist die Behauptung bewiesen.


Die Grundidee ist immer, im Induktionsschritt die Induktionsvoraussetzung zu benutzen, und dann den einen zusätzlichen Summanden noch der Aufgabenstellung entsprechend zu verarzten.


*edit: Ich seh grad, dass das, was du Induktionsbeweis nennst, bei mir Induktionsschritt heißt. Beide Namen sind in Ordnung, solltest du mal über den Begriff Induktionsschritt stolpern. ;)
 
Zuletzt bearbeitet:
OP
OP
Zahnkoloss

Zahnkoloss

Mächtiger Krieger
Mitglied seit
17.10.2007
Beiträge
133
Dein Induktionsanfang ist korrekt.
Deine Induktionsvoraussetzung ist ebenfalls prima so.

Also:
IV: n=k: 1^2 + 2^2 + 3^2 + ... + k^2 = 1/6 * k * (k+1) * (2k+1)

Nun musst du zeigen:
IS: n=k+1:
1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = 1/6 * (k+1) * (k+2) * (2*(k+1) + 1)

Du weißt bereits, dass:
1^2 + 2^2 + 3^2 + ... + k^2 = 1/6 * k * (k+1) * (2k+1) ist.
Also würde ich in deinem IS genau das auch schreiben.

1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = 1/6 * k * (k+1) * (2k+1) + (k+1)^2

Wir haben hier also die IV genutzt.

Jetzt müssen wir noch zeigen, dass:
1/6 * k * (k+1) * (2k+1) + (k+1)^2 = 1/6 * (k+1) * (k+2) * (2*(k+1) + 1)
ist (ich nenne das hier mal Gleichung I).
Also bis hierhin komm ich mit.
Ausmultiplizieren rechts gibt:
1/6*(k^2 + 3k + 2)*(2k + 3) = 1/6 * (2k^3 + 6k^2 + 4k + 3k^2 + 9k + 6) = 1/6*(2k^3 + 9k^2 + 13k + 6)

Ausmultiplizieren links gibt:
1/6 * k * (k+1) * (2k+1) + (k+1)^2 = 1/6*(k^2 + k)*(2k+1) + (k^2 + 2k + 1) = 1/6*(2k^3 + 2k^2 + k^2 + k) + (k^2 + 2k + 1)
Und ab hier versteh ich gar nix mehr. Von welcher Gleichung multiplizierst du links bzw. rechts aus?
Jetzt in der rechten Klammer 1/6 ausklammern:
=1/6*(2k^3 + 2k^2 + k^2 + k) + 1/6*(6k^2 + 12k + 6) = 1/6*(2k^3 + 2k^2 + k^2 + k + 6k^2 + 12k + 6) = 1/6*(2k^3 + 9k^2 + 13k + 6)

Damit sind die linke und rechte Seite von Gleichung I sind also gleich, und damit ist die Behauptung bewiesen.
Welche rechte Klammer? Da gibts einige die rechts sind :p
Und was ist der dritte Teil der nicht farblich markiert ist? Da wurde zwar bewiesen das der erste und der zweite gleich sind aber was der dritte da macht ist mir schleierhaft. Zudem finde ich da nirgendswo 1^2 + 2^2 + 3^2 + ... + k^2 = 1/6 * k * (k+1) * (2k+1) wieder. Ich dachte am Ende muss ich auf ne Gleichung kommen in der die IV drinne steht:?:
 

Kirika1987

Legende
Mitglied seit
30.03.2008
Beiträge
1.167
Eieiei, also nochmal langsam.

Die linke und rechte Seite, von der ich spreche, beziehen sich auf die Gleichung direkt darüber, also Gleichung I.

Von der betrachte ich die linke und rechte Seite getrennt, und multipliziere sie jeweils aus, um zu zeigen, dass sie identisch sind.

Die rechte Klammer, von der ich danach spreche, ist die ganz rechts in der Gleichgung direkt über meinem Satz, also
1/6 * k * (k+1) * (2k+1) + (k+1)^2 = 1/6*(k^2 + k)*(2k+1) + (k^2 + 2k + 1) = 1/6*(2k^3 + 2k^2 + k^2 + k) + (k^2 + 2k + 1) der grüne Teil hier.

Was danach, in deiner letzten Frage, nicht mehr farblich markiert ist, sind entweder Rechenzeichen, oder Terme, in denen sowohl Summanden aus dem roten als auch aus dem blauen Teil stecken. Da ich nicht abwechselnd jedes Symbol mal blau und mal rot färben wollte, dachte ich, das sei so nachvollziehbar.

Deine lange Summe 1^2 + 2^2 + ... + (k+1)^2 haben wir zu Beginn genutzt, und zwar in der vierten Gleichung meines vorangegangen Beitrags, also der ersten, in der ich etwas rot gefärbt habe.

Und die von mir bewiesenen Gleichungen in Kombination ergeben gerade den Beweis deines Induktionsschrittes, da fehlt also nichts.
Setz die von mir gezeigten Dinge mal ineinander ein, dann solltest du es sehen.
Die IV muss ganz am Ende nicht im IS stehen, sondern nur im IS genutzt werden, an irgendeiner Stelle, wo sie dir nützt. Das haben wir hier direkt zu Beginn getan.
 
Oben