Zum Inhalt springen

Aufgabensammlung Mathematik: Teilbarkeit durch 23

Aus Wikibooks

Teilbarkeit durch 23

Beweise, dass für durch 23 teilbar ist.

Verfahren mit direktem Vergleich

Lösungsweg 1

Frage: Über welche Variable kann die Induktion geführt werden?

Frage: Wie lautet der Induktionsanfang? Welches ist die kleinste mögliche Zahl, für die die Teilbarkeit gilt?

Der Induktionsanfang ist für zu führen. Die Formel ergibt dann:

0 ist durch 23 teilbar (generell ist jede natürliche Zahl Teiler von 0).

Hinweis: Der Induktionsanfang könnte theoretische auch für geführt werden. Dann hätte man aber die Aussage „ ist durch 23 teilbar“ nur für natürliche bewiesen. Jedoch gilt die Aussage „ ist durch 23 teilbar“ auch für . Damit auch dieser Fall vom Beweis abgedeckt wird, wählt man als Induktionsanfang .

Frage: Wie lautet die Induktionsvoraussetzung, und wie lautet die Induktionsbehauptung?

Induktionsvoraussetzung: durch 23 teilbar.

Induktionsbehauptung: ist 23 teilbar.

Frage: Über welchen Weg kannst du die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung beweisen?

Der Term der Induktionsbehauptung wird so lange umgeformt, bis wir einen Term erhalten, bei der wir die Teilbarkeit einzelner Teilterme durch 23 beweisen können (So wissen wir aus der Induktionsvoraussetzung, dass ein Teilterm der Form durch 23 teilbar ist). Durch Sätze wie „Die Summe zweier durch 23 teilbarer Terme ist wieder durch 23 teilbar“, können wir dann aus der Teilbarkeit der Teilterme durch 23 auf die Teilbarkeit des gesamten Terms durch 23 schließen.

Aufgabe: Finde Termumformungen, um die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung zu beweisen.

Die Termumformungen lauten:

Der Term in der ersten Klammer ist nach Induktionsvoraussetzung durch 23 teilbar. Somit ist auch der erste Summand durch 23 teilbar (das Produkt einer durch 23 teilbaren Zahl mit einer beliebigen anderen natürlichen Zahl ist wieder durch 23 teilbar). Auch der zweite Summand ist durch 23 teilbar. Damit ist die gesamte Summe durch 23 teilbar, weil beide Summanden dieser Summe durch 23 teilbar sind.

Beweis 1

Aussageform, deren Allgemeingültigkeit in bewiesen werden soll:
1. Induktionsanfang:

ist erfüllt:

ist durch 23 teilbar.

2. Induktionsschritt:
2a. Induktionsvoraussetzung:
ist durch 23 teilbar.
2b. Induktionsbehauptung:
ist durch 23 teilbar.
2c. Beweis des Induktionsschritts:

Verfahren mit Kongruenzen

Die Aufgabe kann mit Hilfe von Kongruenzen so formuliert werden:

Beweise: Für alle ist .

Lösungsweg 2

Frage: Über welche Variable kann die Induktion geführt werden?

Frage: Wie lautet der Induktionsanfang? Welches ist die kleinste mögliche Zahl, für die die Teilbarkeit gilt?

Der Induktionsanfang ist für zu führen. Die Formel ergibt dann:

Also ist die behauptete Kongruenz für gegeben.

Frage: Wie lautet die Induktionsvoraussetzung, und wie lautet die Induktionsbehauptung?

Induktionsvoraussetzung:

Induktionsbehauptung:

Aufgabe: Finde Termumformungen, um die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung zu beweisen.

Die Termumformungen lauten:

Beweis 2

Aussageform, deren Allgemeingültigkeit in bewiesen werden soll:
1. Induktionsanfang:

ist erfüllt:

2. Induktionsschritt:
2a. Induktionsvoraussetzung:
2b. Induktionsbehauptung:
2c. Beweis des Induktionsschritts:

Woher kommt die Idee der geschickten Termumformung?

Auch dieser Beweis ist nicht „vom Himmel gefallen“, sondern entspringt systematischem Nachdenken. Der „Trick“ bei den Termumformungen liegt darin, dass von Zeile 2 zu Zeile 3 eine Null eingeschoben wird, nämlich der Term nacheinander subtrahiert und addiert wird. Dass es gerade dieser Term sein musste, ergibt sich aus folgenden Gedanken:

  • Am Anfang haben wir einen Term, der zur Induktionsbehauptung gehört, also benutzt.
  • Um die Induktionsvoraussetzung zu benutzen, benötigen wir einen gleichartigen Term mit .
  • Wir müssen also so umformen, dass irgendwo steht.
  • Die ersten beiden Umformungen ergeben sich sozusagen automatisch, damit im Exponenten statt steht.
  • Die Induktionsvoraussetzung besagt, dass von jeweils abzuziehen ist. Also fügen wir diese Subtraktion ein unter Berücksichtigung des Faktors . Damit die Gleichheit erhalten bleibt, muss dieser Term gleichzeitig addiert werden.

Damit kann für den ersten Teil die Induktionsvoraussetzung angewendet werden. Für den Rest des Terms in Zeile 3 ergibt sich die eigentliche Behauptung durch einfache Rechnung.

Allgemeine Hinweise, wie man einen solchen Schritt findet, stehen bei Beispielen zur vollständigen Induktion.