Kapitel 3 Elementarmathenatik vom höheren Standpunkt PDF

Preview

Summary

Skript Kapitel 3 Elementarmathematik vom höheren Standpunkt Modul 1 fachdidaktische Grundlagen des Matheunterrichts Universität...

Description

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Inhaltsverzeichnis 3 Die 3.1 3.2 3.3 3.4

natürlichen Zahlen Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Das Pascalsche Dreieck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vollständige Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Varianten der vollständigen Induktion . . . . . . . . . . . . . . . . . . . . . . . .

42

43 44 49 53 58

Regula Krapf

3

Elementarmathematik, Uni Koblenz-Landau

Die natürlichen Zahlen Die natürlichen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.a (Leopold Kronecker) Helmut Hasse hat daher in seinem Buch Vorlesungen über Zahlentheorie im Autorenverzeichnis unter L den lieben Gott aufgeführt! a

Die Menge der natürlichen Zahlen ist die Menge definiert durch N = {0, 1, 2, 3, . . . }. Manche Mathematiker betrachten die Zahl 0 nicht als natürliche Zahl und benutzen die Notationen N = {1, 2, 3, . . . } und N0 = {0, 1, 2, 3, . . . }. Die natürlichen Zahlen lassen sich durch die sogenannten Peano-Axiome axiomatisieren: Peano-Axiome (1) 0 ist eine natürliche Zahl. (2) Jede natürliche Zahl n hat einen eindeutigen Nachfolger n+1, der ebenfalls eine natürliche Zahl ist. (3) Nachfolger natürlicher Zahlen sind ungleich 0, d.h. für jede natürliche Zahl n gilt n+1 ”= 0.

(4) Jede natürliche Zahl ist Nachfolger höchstens einer anderen natürlichen Zahl, d.h. falls n + 1 = m + 1, so folgt n = m. (5) Falls X eine Menge natürlicher Zahlen ist mit den Eigenschaften • 0 œ X und • für jedes n œ X gilt auch n + 1 œ X , so folgt X = N.

Peano-Axiom (5) wird auch als Induktionsaxiom bezeichnet. Auf ihm basiert eine wichtige Beweismethode, das sogenannte Prinzip der vollständigen Induktion (siehe Abschnitt 3.3). Bemerkung 3.1. Peano-Axiom (5) wird üblicherweise wie folgt verwendet: Falls B(n) eine Behauptung über natürliche Zahlen n œ N ist, so kann man die Menge X := {n œ N | B(n)}

betrachten. Um zu zeigen, dass B(n) für alle n œ N gilt, so reicht es zu zeigen: • B(0) ist wahr, d.h. 0 œ X, und

• Falls B(n) wahr ist, so ist auch B(n + 1) wahr für ein beliebiges n œ N, d.h. n œ X ∆ n + 1 œ X.

Aus Peano-Axiom (5), folgt dann, dass X = N, und damit gilt B(n) für jedes n œ N. Diese Beweismethode wird als vollständige Induktion bezeichnet und wird im Abschnitt 3.3 behandelt. Axiome sind Grundannahmen, die oft aus bereits vorhandenen Vorstellungen über den zu definierenden Begrif f resultieren, von deren Gültigkeit man ausgeht und die nicht bewiesen werden. Insbesondere sollen Axiome widerspruchsfrei sein und sich nicht gegenseitig implizieren. Aus den Peano-Axiomen kann man die meisten wichtigen Resultate über die natürlichen Zahlen beweisen, so beispielsweise das Distributivgesetz n(m + k) = nm + nk oder die Existenz einer eindeutigen Primfaktorzerlegung.1 1

Der österreichische Mathematiker Kurt Gödel hat 1931 bewiesen, dass es auch Eigenschaften der natürlichen Zahlen gibt, die nicht aus den Peano-Axiomen folgen, und dass dieses Problem durch Hinzufügen zusätzlicher Axiome nicht gelöst wird.

43

Regula Krapf

3.1

Elementarmathematik, Uni Koblenz-Landau

Rekursion Um Rekursion zu verstehen, muss man Rekursion verstehen. (Ursprung unbekannt)

Eine rekursive Zahlenfolge a0 , a1 , a2 , . . . ist eine Zahlenfolge, bei der ein Folgenglied aus den vorangehenden Folgengliedern berechnet wird. Die Idee einer Rekursion ist es ein Problem der Größe n + 1 auf ein Problem der Größe n zu reduzieren. Damit die Rekursion auch tatsächlich endet, benötigt man also einen Anfangswert, z.B. für n = 0 oder n = 1. Beispiel 3.2. Auf wie viele Arten kann man n Kugeln anordnen? Um dieses Problem zu lösen, nummerieren wir die Kugeln mit Zahlen 1, . . . , n. Sei an die Anzahl Anordnungen von n Kugeln. n 0 1 2 3 4

Anordnungen

an

Wie kann man a3 aus a2 berechnen? Ganz einfach, für jede der beiden Anordnungen von 1 und 2 kann man die 3 auf drei Arten einordnen: 12

123

132

21

312

213

231

321

Um a4 explizit zu berechnen, wenden wir also die Rekursionsvorschrift an: Dazu benötigen wir einen Anfangswert, beispielsweise a0 oder a1 . Wenn wir mit a0 = 1 anfangen, so erhalten wir

44

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Die Rekursion aus Beispiel 3.2 lässt sich also wie folgt darstellen:

Diese Rekursion ist von großer Bedeutung in der Mathematik und hat einen eigenen Namen: Definition 3.3. Für n œ N definiert man rekursiv 0! = 1 (n + 1)! = n! · (n + 1) gesprochen „n Fakultät“. Man kann n! etwas informeller auch explizit darstellen als n! = 1 · 2 · . . . · n. Wenn man ein Zahlenfolge an für jedes n œ N rekursiv definieren möchte, genügt es (1) einen Anfangswert a0 zu definieren; und (2) falls an schon definiert ist, an+1 zu definieren (Rekursionsvorschrift). Eine solche Definition wird als rekursiv bezeichnet. Unter Voraussetzungen (1) und (2) kann man an für jedes n œ N bestimmen: • Nach Voraussetzung ist a0 bekannt. • Aus a0 kann man a1 berechnen. • Aus a1 kann man a2 berechnen. • Aus a2 kann man a3 berechnen. .. . Damit kann man an für jedes n œ N berechnen. Statt mit 0 kann man auch mit einer beliebigen anderen natürlichen Zahl anfangen. Rekursion außerhalb der Mathematik Rekursion ist auch außerhalb der Mathematik von großer Bedeutung. So stellt die Rekursion eines der Kernkonzepte der Programmierung in der Informatik dar. Aber auch in der Kunst und Grammatik sieht man oft Rekursion. Beispielsweise hat der holländische Künstler M.C. Escher oft paradoxe Bilder basierend auf einer Rekursion ohne Anfangswert gezeichnet. Zwei prominente Beispiele ist unten dargestellt.

M.C. Escher, Zeichnende Hände.

45

M.C. Escher, Bildgalerie

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Beispiel 3.4. Wie viele Teilmengen besitzt eine n-elementige Menge, beispielsweise die Menge {1, 2, . . . , n}? Wir setzen bn := |P({1, 2, . . . , n})|. Wir betrachten das Problem für kleine n œ N: n 0a 1 2 3

P({1, . . . , n})

bn

Die Vermutung ist also Wie kann man das beweisen? Was ändert sich beim Übergang von n zu n + 1? Für n = 2 ist dies leicht einzusehen: Für jedes X œ P({1, 2}) erhalten wir in P({1, 2, 3}) zusätzlich zu X auch X fi {3}, d.h. b3 = 2b2 . Dies lässt sich auch anschaulich anhand eines Entscheidungsbaums darstellen, hier am Beispiel n = 3: ÿ 1œX

1œ /X

{1}

ÿ 2œ /X

2œX

{2}

ÿ 3œ /X

ÿ

2œX

3œX

{3}

2œ /X

{1, 2}

3œ /X

3œX

{2}

{2, 3}

3œX

{1, 2, 3}

{1} 3œ /X

{1, 2}

3œX

3œ /X

{1, 3}

{1}

Für ein Element von P({1, . . . , n + 1}) gibt es zwei Möglichkeiten:

Somit gilt bn = 2 · bn≠1 = 2 · 2 · bn≠2 = . . . = ¸2 · .˚˙. . · 2˝ ·b1 = ¸2 · .˚˙. . · 2˝ ·b0 = 2n . (n≠1)-mal

a

n-mal

Die Menge {1, . . . , n} ist für n = 0 als ÿ definiert.

Was haben wir also gemacht? Wir haben die n-te Potenz von 2 rekursiv definiert. Dies kann

46

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

man ganz allgemein für beliebige Zahlen machen: Beispiel 3.5. Man kann Potenzen einer Zahl q œ R rekursiv definieren: q0 = 1 q n+1 = q n · q. Beispiel 3.5 zeigt, dass man die Potenzierung rekursiv aus der Multiplikation definieren kann. Ähnlich kann man die Multiplikation rekursiv mit Hilfe der Addition definieren. Eine wichtige Anwendung von Rekursion ist die Definition des Summen- und Produktzeichens. Definition 3.6. Sei a0 , a1 , a2 , . . . eine Zahlenfolge. Wir definieren endliche Summen durch 0 ÿ

k=0 n+1 ÿ

ak = a0 ak =

k=0

und endliche Produkte durch

0 Ÿ

k=0 n+1 Ÿ k=0

3ÿ n

4

ak + an+1

k=0

ak = a0 ak =

3Ÿ n

k=0

4

ak · an+1

Beispiel 3.7. Die Summe der ersten 100 Zahlen kann dargestellt werden als

Die Summe der ersten 50 Quadratzahlen ist

Die Fakultät n! = 1 · 2 · . . . · n einer natürlichen Zahl n lässt sich auch mit Hilfe des Produktzeichens darstellen als

Viele Rechenregeln für Summen und Produkte aus zwei Summanden bzw. Faktoren lassen sich verallgemeinern: Beispiel 3.8. Seien (an ) und (bn ) Zahlenfolgen. Dann gilt folgende Verallgemeinerung des Kommutativgesetzes: n ÿ

(ak + bk ) =

k=0

47

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Alle bisherigen Beispiele gehören zum einfachsten Fall von Rekursion, nämlich der eingliedrigen Rekursion. Dabei verwendet man einen Anfangswert a0 oder a1 und verwendet zur Berechnung von an+1 nur ein Vorgängerglied, nämlich an . Es gibt aber auch kompliziertere Formen von Rekursion: Beispiel 3.9. Wir betrachten folgendes Problem: Gegeben sind Eisenbahnwagen der Länge 1 und 2. Aus diesen lassen sich Züge zusammenstellen, beispielsweise folgender Zug der Länge 5, mit 3 Wagen der Länge 1 und einem Wagen der Länge 2; die Lokomotive wird dabei nicht mitgezählt.

Wie viele Möglichkeiten Fn gibt es, einen Zug der Länge n aus Wagen der Längen 1 und 2 zusammenzustellen? Um das Problem zu lösen, berechnen wir zunächst Fn für n œ {0, 1, 2, 3, 4}: n 0

Züge

Fn

1 2 3 4 Die Vermutung für die Rekursionsformel lautet daher: F0 = F1 = Fn+1 = Für einen Zug der Länge n + 1 gibt es zwei Möglichkeiten: 1. Fall:

2. Fall:

Also folgt aus der Summenformel: Die Folge (Fn ) wird als Fibonacci-Folge bezeichnet. Zu beachten ist: Um beispielsweise F2 zu berechnen, müssen zwei Anfangswerte, nämlich F0 und F1 bekannt sein.

48

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Allgemein kann man an für jedes n œ N rekursiv definieren, indem man (1) Anfangswerte a0 , . . . , a k≠1 definiert, und

(2) angibt, wie man an+1 aus an , an≠1 , . . . , an≠k+1 definiert. Im Fall der Fibonacci-Folge gilt k = 2. Allgemein gilt: Man braucht k Anfangswerte, wenn die k vorangehenden Folgenglieder in der Rekursionsvorschrift vorkommen. Statt bei 0 kann man auch bei 1 anfangen, wie im Beispiel der Fibonacci-Folge.

3.2

Das Pascalsche Dreieck

Seien n, k œ N mit k Æ n. Wie viele k-elementige Teilmengen besitzt eine n-elementige Menge? Wir lösen dieses Problem rekursiv und setzen dazu Pk ({1, . . . , n}) := {X œ P({1, . . . , n}) | |X| = k} A B n := |Pk ({1, . . . , n})|. k 1 2

Man bezeichnet nk als Binomialkoeffizient (ausgesprochen „n tief k“ oder „n über k“). Wir betrachten zunächst zwei Spezialfälle: P0 ({1, . . . , n}) = Pn ({1, . . . , n}) = 12

1 2

Also gilt 0n = nn = 1 für jedes n œ N. Wir betrachten nun ein X œ Pk ({1, . . . , n, n + 1}). Es gibt zwei Möglichkeiten: 1. Fall: 2. Fall: Insgesamt ergibt sich aus der Summenregel also

Nun hängt diese Rekursion nicht nur von n, sondern 1auch 2 von 1 2 k ab. Wieso kann man 1aus 2 n dieser Rekursionsvorschrift und unseren Anfangswerten 0 = nn = 1 alle Werte der Form nk berechnen? Wir stellen die Werte in1einem Dreieck, dem sogenannten Pascalschen Dreieck dar: Dabei 2 1 2 steht an der Spitze der Wert 00 = 1, an den linken Rändern stehen die Einträge der Form n0 = 1,

an den rechten Rändern die Einträge der Form Summe der beiden darüberstehenden Einträge:

2

0

. . .17

1 2 6 0

1 2 5 0

1 2 7 1

...

1 2 4 0

12 6 1

12 3 0

12 5 1

12 7 2

.. .

1 2 2 0

1 2 4 1

1 2 6 2

1 2 1 0

1 2 3 1

1 2 5 2

1 2 7 3

1 2

1 2 0 0

12 2 1

12 4 2

12 6 3

n n

= 1. Die anderen Einträge ergeben sich als

12 1 1

12 3 2

12 5 3

12 7 4

...

.. .

49

1 2 2 2

1 2 4 3

1 2 6 4

12 3 3

12 5 4

12 7 5

.. .

12 4 4

12 6 5

1 2 5 5

1 2 7 6

...

1 2 6 6

1 2 7 7

..

.

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Nun lassen sich alle Einträge berechnen, da jeder Eintrag entweder am Rand ist oder zwei diagonal darüberstehende Einträge besitzt. Das Pascalsche Dreieck sieht also wie folgt aus: 1 1 1

2

1

3

1 1 1 ...

1

4

1 3

6

5

10

6 7 .. .

1

15 21 ...

1 4

1

10 20

35 .. .

5 15

35 .. .

1 6

21 ...

1 7 .. .

1

..

.

1 2

Wenn wir aber beispielsweise 12 berechnen möchten, so müssen wir 13 Zeilen (Zeilen 0 bis 5 12) des Pascalschen Dreiecks berechnen,1 2was ziemlich viel Rechenaufwand bedeutet. Können wir auch eine explizite Darstellung von kn angeben?

Lemma 3.10. Seien n, k œ N mit k Æ n. Dann gilt A B

n n! = . k k!(n ≠ k)!

Beweis. Wir zeigen mittels doppeltem Abzählen die äquivalente Aussage n! =

A B

n · k! · (n ≠ k)!, k

indem wir die Anzahl Anordnungen an von n Kugeln abzählen.

Das Pascalsche Dreieck hat viele weitere schöne Eigenschaften, beispielsweise kann daraus eine Verallgemeinerung der Binomischen Formeln ablesen. Aus der Schule sind die folgenden drei Binomischen Formeln für a, b œ R bekannt: (a + b)2 = a2 + 2ab + b2 (a ≠ b)2 = a2 ≠ 2ab + b2 (a + b)(a ≠ b) = a2 ≠ b2 . Die 2. Binomische Formel ist dabei eigentlich nur ein Spezialfall der 1. Binomischen Formel: (a ≠ b)2 = 50

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Wir möchten nun die Binomischen Formeln verallgemeinern und eine Formel für (a + b)n finden für a, b œ R und n œ N. Dazu berechnen die ersten paar Terme: (a + b)0 = (a + b)1 = (a + b)2 = (a + b)3 =

.. . Wenn wir also eine Formel für (a + b)n kennen, so erhalten wir eine Formel für (a + b)n+1, indem wir jeden Term in (a + b)n einmal mit a und einmal mit b multiplizieren, denn es gilt (a + b)n+1 = (a + b)(a + b)n = a(a + b)n + b(a + b)n . D.h. man muss jeden Summanden in der ausmultiplizierten Darstellung von (a + b)n einmal mit a und einmal mit b multiplizieren. Die Koeffizienten der Summanden erfüllen also dieselbe Rekursion wie die Binomialkoeffizienten. Für n Æ 3 lässt sich dies wie folgt veranschaulichen: 1a0 b 0 ·a

z

z

·a

z

z 1a5 b 0

·a

$

·b

1a4 b 0 ·b

+

$

z 5a4 b 1

z

·a

·b

+

z

$

z

·a

$

·b

·b

$

1a0 b 3 ·a

z

z

10a2 b 3

·a

1a0 b 4

+ ·b

+

$

·b

4a1 b 3

+

+

$

·b

+

·a

z 6a2 b 2

10a3 b 2

·a

3a1 b 2

$

·b

+

1a0 b 2

$

·b

+

·a

z

$

·b

+

·a

3a2 b 1

4a3 b 1

+

z 2a1 b 1

$

·b

+

·a

$

·b

+

·a

1a3 b 0

1a0 b 1

+

·a

z 1a2 b 0

$

·b

1a1 b 0

$

z 5a1 b 4

·a

·b

+

$ 1a0 b 5

Das Dreieck entspricht genau dem Pascalschen Dreieck! In Zeile n steht die ausmultiplizierte Darstellung von (a + b)n ; wenn bei einem Summanden der 1 2Exponent von b gleich k ist, so ist der Exponent von a genau n ≠ k, und der Koeffizient ist kn . Also erhalten wir allgemein

bzw. kurz gefasst: Theorem 3.11 (Der Binomische Lehrsatz, Pascal 1654). Für a, b œ R und n œ N gilt n

(a + b) =

n ÿ

k=0

51

A B

n n≠k k a b . k

Regula Krapf

Elementarmathematik, Uni Koblenz-Landau

Alternativ lässt sich der Binomische Lehrsatz auch mit dem Prinzip der vol lständigen Induktion beweisen, siehe dazu Abschnitt 3.2. Der Binomische Lehrsatz ist hilfreich beim Berechnen von Potenzen: Beispiel 3.12. Wir verwenden den Binomischen Lehrsatz, um 1, 014 ohne Taschenrechner zu berechnen. Es gilt 1, 014 = (1 + 0, 01)4 = =

A B 4 ÿ 4

k=0 k A B 4 ÿ

k=0

A B

1n≠k 0, 01k

4 10≠2k k A B

A B

A B

A B

4 4 4 4 4 = 10≠8 10≠6 + 10≠4 + 10≠2 + + 4 3 2 1 0 = 1 + 0, 04 + 0, 0006 + 0, 000004 + 0, 00000001 = 1, 04060401.

52

Regula Krapf

3.3

Elementarmathematik, Uni Koblenz-Landau

Vollständige Induktion Wenn man von einem Haufen ein Sandkorn entfernt, so bilden die restlichen Sandkörner immer noch ein Haufen. Oder andersrum: Ein Sandkorn ist kein Haufen. Ein Haufen entsteht nicht durch Hinzufügen eines Sandkorns. Was ist ein Haufen? (Paradoxie des Haufens)

Wir führen nun eine Beweismethode ein, mit Hilfe derer man viele Aussagen über natürliche Zahlen beweisen kann, die sogenannte vollständige Induktion; diese basiert auf Peano-Axiom (5), welches auch als Induktionsaxiom bezeichnet wird. Die Beweismethode basiert auf der Idee, dass man eine Aussage B(n) für alle n œ N beweisen kann, indem man sie für n = 0 beweist und aus B(n) die Aussage B(n + 1) folgert. Beweisführung: Vollständige Induktion Um eine Behauptung B(n) für alle n œ N zu beweisen, gehen wir wie folgt vor: (1) Induktionsanfang:

Die Behauptung stimmt für n = 0; das heißt, B(0) ist wahr.

(2) Wenn B(0) bewiesen ist, zeigen wir ’n œ N : B(n) ∆ B(n + 1). Dazu treffen wir zuerst eine Annahme: Induktionsannahme:

Wir nehmen an, dass für ein beliebiges, aber festes n die Behauptung B(n) richtig ist.

Mit Hilfe dieser Annahme beweisen wir B(n + 1): Induktionsschluss:

Wir folgern aus B(n), dass auch B(n + 1) wahr ist.

Daraus folgt, dass die Aussage B(n) für jedes n œ N gilt. Etwas vereinfacht: Man zeigt • B(0) ist wahr (Induktionsanfang), • Wenn B(n) wahr ist (Induktionsannahme), so ist auch B(n+1) wahr (Induktionsschluss). Dann ist B(n) für jedes n œ N wahr. Wieso macht das Sinn? • Gemäß dem Induktionsanfang ist B(0) wahr.

• Da B(0) wahr ist, ist auch B(0 + 1), also B(1) wahr. • Da B(1) wahr ist, ist auch B(1 + 1), also B(2) wahr. • Da B(2) wahr ist, ist auch B(2 + 1), also B(3) wahr. ....