Teilbarkeit beweisen - vollständige Induktion

Wissenschaft Mathematik
1

Hallo zusammen,

ich befasse mich grad mit der vollständigen Induktion. Für Summen und Produkte habe ich das soweit auch verstanden und kann es anwenden.

Beweise von Teilbarkeit laufen aber noch etwsa holprig. Wäre nett, wenn ihr mal einen Blick werfen würdet, ob mein Beweis so richtig ist.

Behauptung: 2^3n-1 ist durch 7 teilbar für alle n Element N

Induktionsanfang:
n0=1
2^3-1=7 (7 ist durch 7 teilbar, Induktionsanfang ist gültig)

Induktionsannahme:
2^3n-1 ist für ein n>=n0 durch 7 teilbar. Dann gibt es m Element Z für das gilt: 2^3n-1 = 7m 2^3 = 7m+1

Induktionsschritt:
Zu zeigen ist, wenn 2^3n-1=7m mit m Element Z, dann gibt es ein m’ Element Z mit 2^3(n+1) - 1 = 7m’

Dann gilt:
2^(3n+1)-1 = 2^3n * 2^3 -1 = (7m + 1) * 2^3 - 1 = 7m * 2^3 + 2^3 - 1 = 7 * (2^3m + 1)

Es gibt also ein m’ = 2^3m + 1 Element Z mit 2^3(n+1) - 1 = 3m’
Mit dem Prinzip der vollständigen Induktion gilt die Behauptung.

Ist das so ok? Oder habe ich noch was vergessen?

2

Hallo,

ich würde das so machen:

  1. Schritt: wie bei Dir
  2. Schritt:
    Induktions voraussetzung : 2^3n-1 ist durch 7 teilbar
    Induktions behauptung : 2^3(n+1)-1 ist durch 7 teilbar
    Induktions beweis :

2^3(n+1)-1 = 2^3n * 2^3 -1
= 2^3n *(7+1) -1
= 2^3n * 7 + 2^3n -1
Der 1. Summand ist durch 7 teilbar, der 2. und 3. zusammen ist nach Ind.-voraussetzung durch 7 teilbar, also ist die linke Seite durch 7 teilbar, q.e.d.

3

Hallo Haubenmeise,

danke für die Antwort.

Deinen Lösungsweg finde ich auch übersichtlicher. Das entspricht auch dem, was ich beim googlen bisher gefunden haben.

Die Sache mit dem m und m’ scheint wohl nicht so verbreitet zu sein. Steht aber so bei mir im Skript und ich habe mir gedacht, das wenigstens für die Klausur so zu übernehmen.

4

Hallo power_blue,
abgesehen von einem kleinen Schreibfehler ist Dein Beweis nicht anders als meiner. Ich finde nur, wenn man zeigt, dass man von einem Ausdruck einen Faktor F (hier 7) abspalten kann, dann ist der Ausdruck durch F teilbar. Deine Suche nach m und m’ macht das Ganze unübersichtlich.

Viele Grüße von
Haubenmeise

5

Hi,

Du kannst natürlich auch, wenn nicht explizit nach Induktion verlangt ist, verwenden, dass 2^3=8 gilt und 8^n-1^n immer durch 8-1=7 teilbar ist, weil allgemein, in Verallgemeinerung der dritten binomischen Formel, sich von A^n-B^n ein Faktor A-B abspalten lässt.

Gruß Lutz

PS: Und ich finde, dass beide Induktionsbeweise, schön aufgeschrieben, in etwa gleich lang und gleich verständlich sind.

6

Hi Lutz,

der Beweis soll mit vollständiger Induktion geführt werden.

Wenn es (bis auf den Tippfehler) soweit korrekt ist, werde ich wohl für’s erste die m und m’-Variante aus meinem Skript beibehalten.

7

Hallo,

[…] die m und m’-Variante aus meinem Skript beibehalten.

auch wenn der Beweis damit formal genauso korrekt ist – irgendwie kann ich in diesen Variablen keinen rechten Sinn erkennen. „Simple is beautiful“! Mein Favorit unter den vielen möglichen Varianten wäre:

Ind.anfang:
\frac{2^{3\cdot 0}-1}{7} = 0 = \textnormal{eine ganze Zahl}

Ind.annahme:
\frac{2^{3n}-1}{7} = \textnormal{eine ganze Zahl}

Ind.schluss (Zwischenschritte „…“ der Rechnung selbst ergänzen):
\begin{eqnarray}
\frac{2^{3(n+1)}-1}{7} =: …
&=& 2^{3n} + \frac{2^{3n}-1}{7} \nonumber\
&=& \textnormal{eine ganze Zahl}

  • \textnormal{eine ganze Zahl} \nonumber\
    &=& \textnormal{eine ganze Zahl} \nonumber
    \end{eqnarray}

Gruß
Martin

8

Hallo Martin,

ich hatte es in meinem Beitrag schon durch Fettdruck hervorgehoben:
Ich meine, es muss Induktions- Voraussetzung heißen, und nicht Induktions- Annahme. Habe ich so gelernt…

Viele Grüße von
Haubenmeise

9

Hallo Haubenmeise,

…womit Du auf der Seite der Mehrheit zu stehen scheinst: Eine Testanfrage bei web.de (die eine Suche über Google gestartet hat) lieferte 4500 Ergebnisse für „Induktionsvoraussetzung“, aber nur 2680 für „Induktionsannahme“. Dessen ungeachtet sehe ich aber im Moment nicht, was an der „Annahme“ so falsch sein soll. Man könnte sogar Induktionshypothese dazu sagen, aber das habe ich noch nie gelesen. Ich mag die „Annahme“ lieber, weil das Wort kürzer ist.

Gruß
Martin

Sehr erstaunt hat mich allerdings, was ich in Wikipedia fand: „…mit Hilfe der Induktionsvoraussetzung (auch: Induktionsbehauptung)…“. Das halte ich tatsächlich für einen Fehler. Die Induktionsbehauptung ist ja die zu beweisende Aussage, also salopp gesagt „die mit dem n + 1“.

10

Hi,

Sehr erstaunt hat mich allerdings, was ich in Wikipedia fand:
„…mit Hilfe der Induktionsvoraussetzung (auch:
Induktionsbehauptung)…“. Das halte ich tatsächlich für einen
Fehler. Die Induktionsbehauptung ist ja die zu beweisende
Aussage, also salopp gesagt „die mit dem n + 1“.

das sehe ich etwas anders. Das, was zu beweisen ist, ist die ursprüngliche Behauptung (also die mit n). Auch wenn ich das noch nicht gesehen habe, kann man das sicher auch Induktionsbehauptung nennen.

Ob Induktionsannahme oder Induktionsvoraussetzung ist denke ich egal, weil beides passt. Das hängt wohl nur vom Autor ab.

Was im Induktionsschritt gezeigt wird, ist dass der Term mit (n+1) gültig ist, wenn auch der mit n gültig ist - also eine Implikation. Wenn man das zusammen mit dem Induktionsanfang (mit n0) ingekommt, ist folglich die Behauptung (mit n) gültig.

11

Hallo Martin,

Hallo Haubenmeise,

…womit Du auf der Seite der Mehrheit zu stehen scheinst:
Eine Testanfrage bei web.de (die eine Suche über Google
gestartet hat) lieferte 4500 Ergebnisse für
„Induktionsvoraussetzung“, aber nur 2680 für
„Induktionsannahme“. Dessen ungeachtet sehe ich aber im Moment
nicht, was an der „Annahme“ so falsch sein soll. Man könnte
sogar Induktionshypothese dazu sagen, aber das habe ich noch
nie gelesen. Ich mag die „Annahme“ lieber, weil das Wort
kürzer ist.

Die „Annahme“ kenne ich nur beim indirekten Beweis. Man nimmt etwas an und leitet dazu einen Widerspruch her: Damit ist dann die Annahme zu verwerfen, und das Gegenteil ist richtig (bewiesen).
Ich halte mich lieber an das Beweisgerüst (beim direkten Beweis):
-Voraussetzung
-Behauptung
-Beweis

Gruß
Martin

Sehr erstaunt hat mich allerdings, was ich in Wikipedia fand:
„…mit Hilfe der Induktionsvoraussetzung (auch:
Induktionsbehauptung)…“. Das halte ich tatsächlich für einen
Fehler. Die Induktionsbehauptung ist ja die zu beweisende
Aussage, also salopp gesagt „die mit dem n + 1“.

Dein Erstaunen findet meine vollste Zustimmung.

Viele Grüße von
Haubenmeise