Beweis per vollständiger Induktion mit mehr als einer Variablen. Produkt aus zwei geraden Zahlen ist durch 4 teilbar.

Question

vor langer Zeit gab es die folgende Aufgabe von Thilo hier im Forum. Dazu meine Lösung weiter unten. Ob meine Lösung richtig ist, würde ich gerne von euch erfahren :)

Aufgabe von Thilo:

Beweise, dass das Produkt aus zwei geraden natürlichen Zahlen m, n immer durch 4 teilbar ist.

Meine Lösung:

$$m = 2x$$

$$n = 2y$$

$$m \cdot n = 2x \cdot 2y = 4 \cdot(xy)$$

 Also ist $$4 \cdot (xy)$$ offensichtlich durch $$4$$ teilbar. Deshalb gilt die Aussage.

Beweis per vollständiger Induktion:

Wenn wir die Aussage per vollständiger Induktion beweisen wollen, müssen wir doch den Beweis zwei mal ausführen, einmal für $$m$$ und einmal für $$n$$, denn die beiden Variablen sind ja unabhängig voneinander, oder?

Mein Versuch zu vollständiger Induktion für die Variable m:

Induktionsanfang:

Induktionsvoraussetzung:

Seien $$m := 2x$$ und $$n:= 2y$$ mit $$x, y \in \mathbb{N}$$

Für eine gerade Zahl $$m >= 0$$ gelte: $$4 | m \cdot n$$.

Behauptung: Die Aussage gilt für $$m = 0$$

Beweis: $$m \cdot n = 0 \cdot n = 0$$

$$0$$ teilt jede Zahl, insbesondere auch die $$4$$. Deshalb gilt die Aussage für $$m = 0$$.

Induktionsschritt:

Induktionsbehauptung:

Dann gilt die Aussage auch für $$m + 2$$.

Beweis:

$$(m + 2) \cdot n = (2x + 2) \cdot n = 2x \cdot n + 2 \cdot n = 2x \cdot 2y + 2 \cdot 2y = 4xy + 4y = 4 \cdot (xy+y)$$

Die Gleichung ist offensichtlich durch $$4$$ teilbar. Also gilt die Aussage auch für $$m+2$$.

Ist der Beweis so richtig?

Ich habe aber nirgends die Induktionsvoraussetzung in meinem Beweis verwendet – geht das?

Liebe Grüße

Asg

PS: $$ bewirkt unnötigen Zeilenumbruch. Kann man es denn irgendwie abstellen?

Comments

@PS. Vgl. Punkt 1 zu TeX-Tipps hier https://www.matheretter.de/rechner/latex

---

Wer verlangt von dir, dass du einen Induktionsbeweis machen musst?

---

Danke für den Tip mit Tex, werde es probieren.

Aus reiner Interesse und zur Übungszwecken möchte ich die Aussage per vollständiger Induktion beweisen ;)

Answer 1

Deine Beweise sind korrekt.

Da du die Induktionsvoraussetzung nicht verwendet hast, ist der zweite Beweis aber kein Beweis durch vollständige Induktion. Er sieht lediglich so aus wie einer. Korrekt ist er trotzdem.

Comments

Danke erstmal für die ermutigende Antwort :)

Dann bleiben noch zwei Fragen:

1. Ist es richtig, wie ich oben geschrieben habe, dass man die Induktion für \( m \) und \( n \) einzeln, also insgesamt zwei mal, ausführen muss, da die Variablen ja von einander unabhängig sind?

2. Wie könnte ich denn die Induktionsvoraussetzung verwenden, damit aus dem Beweis doch noch eine vollständige Induktion wird, denn das ist ja mein Ziel, die vollständige Induktion zu üben.

Danke nochmals.

---

> dass man die Induktion für m und n einzeln, also insgesamt zwei mal, ausführen muss

Man kann den Beweis über volländige Induktion auch dadurch führen, dass man im Induktionsanfang zeigt, dass m·n für m=0, n=0 durch 4 teilbar ist, in der Induktionsvoraussetzung fordert, dass m·n für bestimmte m, n durch 4 teilbar ist und im Induktionsschluss die Induktionsvoraussetzung verwendet um zu zeigen, dass dann

         (m+2)·n durch 4 teilbar ist und m·n = n·m ist

oder

        (m+2)·n und m·(n+2) durch 4 teilbar sind.

> Wie könnte ich denn die Induktionsvoraussetzung verwenden

(m+2)·n = m·n + 2·n = m·n + 2·2·x = m·n + 4x für ein x∈ ℕ, weil n gerade ist.

m·n ist laut IV durch 4 teilbar. 4x ist durch 4 teilbar, weil es 4 als Faktor hat. Also ist die Summe durch 4 teilbar.

---

danke für die Erklärung.

[...](m+2)·n = m·n + 2·n = m·n + 2·2·x = m·n + 4x für ein x∈ ℕ, weil n gerade ist.[...]

Ah! ok, so macht es Sinn ...

Wenn man es ganz genau nimmt, müsste hier statt \( x \) jeweils \( y \) stehen, da ich oben \( n:= 2y \) definiert hatte.

Dankeschön nochmals und viele Grüße

Asg