TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 32

Angabe

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 (a) mittels eines Beweises durch vollständige Induktion.

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!

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 {o_{\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. ;-) )

Beispiel (c)

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

Der Beweis durch Kontradiktion 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!