TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 2

Man bestätige die Richtigkeit der folgenden Behauptungen:

a) Für alle $n\in \mathbb {N}$ ist $n^{3}-n$ stets durch 3 teilbar - mittels eines direkten Beweises.

b) Ist die Summe $m+n$ zweier Zahlen $m,n\in \mathbb {Z}$ ungerade, dann ist genau einer der beiden Summanden ungerade - mittels eines indirekten Beweises.

c) Ist das Quadrat $n^{2}$ einer ganzen Zahl $n\in \mathbb {N}$ gerade, dann ist auch $n$ gerade - mittels eines Beweises durch Kontraposition.

d) Die Aussage von (1) mittels eines Beweises durch vollständige Induktion.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

SS08 Beispiel 14

WS16 Beispiel 86 (teilweise)

Lösungsvorschlag von mnemetz

Beispiel (a)

Für alle $n\in \mathbb {N}$ ist $n^{3}-n$ stets durch 3 teilbar - mittels eines direkten Beweises.

Beim direkten Beweis wird die Behauptung durch Anwenden von bewiesenen Aussagen und durch logische Folgerungen bewiesen.

Es soll gelten: $x={\frac {n^{3}-n}{3}}\qquad \forall n\in \mathbb {N} :x\in \mathbb {N}$!

Einige Werte für n berechnen:

  n     Ergebnis
  1     0
  2     6
  3     24
  4     60

Den Term können wir weiter zerlegen:

$n^{3}-n=n*(n^{2}-1)=(n-1)*n*(n+1)$

Betrachten wir das Ergebnis:

$\underbrace {(n-1)} _{1.Zahl,z.B.4}*\underbrace {n} _{2.Zahl,z.B.5}*\underbrace {(n+1)} _{3.Zahl,z.B.6}$

Der Term liefert also als Teilergebnisse drei aufeinanderfolgende Zahlen - und eine dieser Zahlen muss dann durch Drei teilbar sein!

Wenn eine Zahl mit einer Zahl welche durch 3 teilbar ist multipliziert wird ist das Ergebnis durch 3 teilbar.

Beispiel (b)

Ist die Summe $m+n$ zweier Zahlen $m,n\in \mathbb {Z}$ ungerade, dann ist genau einer der beiden Summanden ungerade - mittels eines indirekten Beweises.

Beim indirekten Beweis zeigt man, dass ein Widerspruch entstehen würde, wenn die zu beweisende Behauptung falsch wäre (deshalb nennt man diese Methode auch Beweis durch Widerspruch oder reductio ad absurdum). Dazu verwendet man die gleichen Methoden, wie beim direkten Beweis. Wenn nun die Behauptung nicht falsch sein kann, muss sie richtig sein. Wichtige (und keinesfalls selbverständliche!) Voraussetzung für die Gültigkeit eines Widerspruchbeweises ist, dass im zugrundeliegenden System die Aussage nicht gleichzeitig wahr und falsch sein kann (Widerspruchsfreiheit).

Wenn als Grundannahme gelten soll: $\underbrace {m} _{ungerade}+\underbrace {n} _{gerade}=\underbrace {o} _{ungerade}\qquad \forall m,n,o\in \mathbb {N}$, so müssen wir als Gegenteil annehmen:

$\underbrace {m} _{ungerade}+\underbrace {n} _{gerade}=\underbrace {o} _{gerade}\qquad \forall m,n,o\in \mathbb {N}$

Ich spalte daher den Term $m+n$ auf in die Komponenten:

$\underbrace {(m_{\text{gerade}}+\underbrace {m_{\text{ungerade}})} _{0}} _{m}+\underbrace {(n_{\text{gerade}}+\underbrace {n_{\text{ungerade}})} _{0}} _{n}=\underbrace {(o_{\text{ungerade}}+\underbrace {0_{\text{gerade}})} _{0}} _{o}$

Widerspruch! Zwei gerade Zahlen miteinander addiert ergeben wieder eine gerade Zahl!!

(Anmerkung: Man könnte auch argumentieren, dass die Menge der geraden Zahlen auf die Operation "+" hin abgeschlossen ist, aber das gehört nicht hierher. ;-) )

Alternativer Lösungsansatz

Gegebehauptung: Ist die Summe n+m ungerade, so sind entweder beide gerade, oder beide ungerade.

Wenn m und n gerade sind, dann gilt 2 teilt m und 2 teilt n. Wenn die Summe ungerade ist, dann teilt 2 m+n+1. Also müsste gelten n+m=m+n+1 modulo 2, was falsch ist. Wenn beide ungerade sind, dann teilt 2 m+1 und n+1, also auch m+n+2, also auch m+n, also müsste gelten m+n=m+n+1 module 2, was falsch ist.

Quelle: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?57186-1.10b%29-%28Buch%29

Beispiel (c)

Ist das Quadrat $n^{2}$ einer ganzen Zahl $n\in \mathbb {N}$ gerade, dann ist auch $n$ gerade - mittels eines Beweises durch Kontradiktion.

Der Beweis durch Kontraposition erfolgt folgendermaßen:

Aus der Angabe: A -> B (aus n² gerade folgt n gerade)

Die Kontradiktion: ¬B -> ¬A

Will man dieses Beispiel also mittels Kontradiktion beweisen so muss man zeigen dass eine ungerade Zahl ² wieder eine ungerade Zahl als Ergebnis hat!

Wir nehmen an: $\exists k:\qquad n=2*k+1$ - das ist die Umschreibung für eine ungerade Zahl.

Nun sagen wir:$n^{2}=(2*k+1)^{2}=4*k^{2}+4*k+1=2*(2*k^{2}+2*k)+1$

Aus dem umgeformten Ergebnis geht hervor, dass das Ergebnis ungerade ist => Korrekt!

Beispiel (d)

Die Aussage von (a) mittels eines Beweises durch vollständige Induktion.

Wir erinnern uns an die Umformung in (a):

$n^{3}-n=n*(n^{2}-1)=(n-1)*n*(n+1)$

Selbstverständlich werden wir nicht den Term $n^{3}-n$ für die Ausführung der vollständigen Induktion verwenden, sondern den gleichwertigen, umgeformten: $(n-1)*n*(n+1)$!

Somit ist $(n-1)*n*(n+1)$ die Induktionsvorraussetzung.

Die Induktionsbehauptung ist nun: $(n{\mathit {+1}}-1)*(n{\mathit {+1}})*(n{\mathit {+1}}+1)$

Und diese Induktionsbehauptung vereinfacht heißt: $(n)*(n+1)*(n+2)$ - wiederum gilt, was wir in (a) gesagt haben:

$\underbrace {(n)} _{1.Zahl,z.B.4}*\underbrace {n+1} _{2.Zahl,z.B.5}*\underbrace {(n+2)} _{3.Zahl,z.B.6}$

Der Term liefert also als Teilergebnisse drei aufeinanderfolgende Zahlen - und eine dieser Zahlen muss dann durch Drei teilbar sein! Damit ist der Induktionsbeweis erfolgt!

Siehe auch

• https://web.archive.org/web/20180730213905/http://www.uni-protokolle.de/foren/viewt/90268,0.html