Kapitel 1 Vollständige Induktion. Kapitel 1 © Beutelspacher April 2004 Seite 2 Inhalt 1.1 Das Prinzip A(n) A(n+1) 1.2 Anwendungen 1 + 2 + 3 +... + n =

Kapitel 1

Vollständige Induktion

Kapitel 1

Vollständige Induktion

Kapitel 1 © Beutelspacher

April 2004Seite 2

InhaltInhalt

1.1 Das Prinzip

A(n) A(n+1)

1.2 Anwendungen

1 + 2 + 3 + ... + n = ?

1.3 Landkarten schwarz-weiß

1.4 Fibonacci-Zahlen

1, 1, 2, 3, 5, 8, 13, 21, ...

1.1 Das Prinzip

A(n) A(n+1)

1.2 Anwendungen

1 + 2 + 3 + ... + n = ?

1.3 Landkarten schwarz-weiß

1.4 Fibonacci-Zahlen

1, 1, 2, 3, 5, 8, 13, 21, ...


April 2004Seite 3

1.1 Das Prinzip1.1 Das Prinzip

• Ziel: In der Mathematik macht man in der Regel Aussagen über

unendlich viele Objekte (alle Zahlen, alle Dreiecke usw.)

• Solche Aussagen kann man prinzipiell nicht dadurch klären

(„beweisen“), dass man alle Fälle einzeln ausprobiert. Man muß die

Aissage sozusagen „auf einen Schlag“ erledigen. Dazu dient die

(vollständige, mathematische) Induktion.

• Bemerkung: Unter „Induktion“ versteht man (im Gegensatz zur

„Deduktion“ eigentlich das – logisch unzulässige – Schließen von

Einzelfällen auf alle Fälle. Die mathematische Induktion ist ein

Werkzeug, mit dem man das sauber machen kann.

• Ziel: In der Mathematik macht man in der Regel Aussagen über

unendlich viele Objekte (alle Zahlen, alle Dreiecke usw.)

• Solche Aussagen kann man prinzipiell nicht dadurch klären

(„beweisen“), dass man alle Fälle einzeln ausprobiert. Man muß die

Aissage sozusagen „auf einen Schlag“ erledigen. Dazu dient die

(vollständige, mathematische) Induktion.

• Bemerkung: Unter „Induktion“ versteht man (im Gegensatz zur

„Deduktion“ eigentlich das – logisch unzulässige – Schließen von

Einzelfällen auf alle Fälle. Die mathematische Induktion ist ein

Werkzeug, mit dem man das sauber machen kann.


April 2004Seite 4

Das Prinzip der vollständigen InduktionDas Prinzip der vollständigen Induktion

Prinzip der vollständigen Induktion. Sei A eine Aussage oder

eine Eigenschaft, die von einer natürlichen Zahl n abhängt. Wir

schreiben auch A(n).

Wenn wir wissen, daß folgendes gilt:

(1) Induktionsbasis (Induktionsverankerung): Die Aussage A

gilt im Fall n = 1 (das heißt, es gilt A(1)),

(2) Induktionsschritt: Für jede natürliche Zahl n 1 folgt aus

A(n) die Aussage A(n+1),

dann gilt die Aussage A für alle natürlichen Zahlen 1.

Prinzip der vollständigen Induktion. Sei A eine Aussage oder

eine Eigenschaft, die von einer natürlichen Zahl n abhängt. Wir

schreiben auch A(n).

Wenn wir wissen, daß folgendes gilt:

(1) Induktionsbasis (Induktionsverankerung): Die Aussage A

gilt im Fall n = 1 (das heißt, es gilt A(1)),

(2) Induktionsschritt: Für jede natürliche Zahl n 1 folgt aus

A(n) die Aussage A(n+1),

dann gilt die Aussage A für alle natürlichen Zahlen 1.


April 2004Seite 5

ErläuterungErläuterung

Bedeutung der vollständigen Induktion: Um eine Aussage über

unendlich viele Objekte nachzuweisen, muss man nur zwei

Aussagen beweisen:

Induktionsbasis: A(1)

Induktionsschritt: A(n) A(n+1)

Man nennt A(n) auch die Induktionsvoraussetzung.

Die hinter diesem Prinzip stehende “Philosophie” ist die, dass man in

objektiv kontrollierbarer Weise über eine Unendlichkeit (“alle”

natürlichen Zahlen) sprechen kann. Die Bedeutung dieses Prinzips,

wurde zwischen 1860 und 1920 u.a. von Moritz Pasch (Professor in

Gießen) und Giuseppe Peano (Professor in Turin) entdeckt.

Bedeutung der vollständigen Induktion: Um eine Aussage über

unendlich viele Objekte nachzuweisen, muss man nur zwei

Aussagen beweisen:

Induktionsbasis: A(1)

Induktionsschritt: A(n) A(n+1)

Man nennt A(n) auch die Induktionsvoraussetzung.

Die hinter diesem Prinzip stehende “Philosophie” ist die, dass man in

objektiv kontrollierbarer Weise über eine Unendlichkeit (“alle”

natürlichen Zahlen) sprechen kann. Die Bedeutung dieses Prinzips,

wurde zwischen 1860 und 1920 u.a. von Moritz Pasch (Professor in

Gießen) und Giuseppe Peano (Professor in Turin) entdeckt.


April 2004Seite 6

AussagenAussagen

A(n): 4n ist eine gerade Zahl

A(n): n2 ist eine gerade Zahl

A(n): n ist eine Primzahl

A(n): Die Anzahl der Sitzordnungen von n Studierenden auf n

Stühlen ist n! (:= n(n–1)...21, sprich „n Fakultät”)

A(n): n geradlinige Straßen haben höchstens n Kreuzungen

A(n): Wenn n Computer zu je zweien durch eine Leitung

verbunden werden, so braucht man genau n(n–1)/2 Leitungen

A(n): 4n ist eine gerade Zahl

A(n): n2 ist eine gerade Zahl

A(n): n ist eine Primzahl

A(n): Die Anzahl der Sitzordnungen von n Studierenden auf n

Stühlen ist n! (:= n(n–1)...21, sprich „n Fakultät”)

A(n): n geradlinige Straßen haben höchstens n Kreuzungen

A(n): Wenn n Computer zu je zweien durch eine Leitung

verbunden werden, so braucht man genau n(n–1)/2 Leitungen


April 2004Seite 7

1.2 Anwendungen1.2 Anwendungen

Problem (C.F. Gauß): 1+2+3 +...+ 100 = ???

1.2.1 Satz. Für jede natürliche Zahl n 1 gilt:

1+2+... + n = n(n+1)/2.

In Worten: Die Summe der ersten n positiven ganzen Zahlen ist

gleich (n+1)n/2.

Konsequenz: Man kann die Summe 1+2+3+...+n ganz einfach

ausrechnen, und es passieren kaum Rechenfehler.

Problem (C.F. Gauß): 1+2+3 +...+ 100 = ???


1+2+... + n = n(n+1)/2.

In Worten: Die Summe der ersten n positiven ganzen Zahlen ist

gleich (n+1)n/2.

Konsequenz: Man kann die Summe 1+2+3+...+n ganz einfach

ausrechnen, und es passieren kaum Rechenfehler.


April 2004Seite 8

DreieckszahlenDreieckszahlen

Definition. Die Zahlen der Form (n+1)n/2, also die Zahlen 1, 3, 6,

10, 15, ... heißen Dreieckszahlen.

Man kann Satz 1.2.1 also auch so ausdrücken: Die Summe der

ersten n positiven ganzen Zahlen ist gleich der n-ten Dreieckszahl.

Definition. Die Zahlen der Form (n+1)n/2, also die Zahlen 1, 3, 6,

10, 15, ... heißen Dreieckszahlen.

Man kann Satz 1.2.1 also auch so ausdrücken: Die Summe der

ersten n positiven ganzen Zahlen ist gleich der n-ten Dreieckszahl.


April 2004Seite 9

Beweis (durch Induktion)Beweis (durch Induktion)

Beweis durch Induktion nach n.

Die Aussage A(n) sei die Aussage des Satzes, also:

A(n): 1+2+3 +...+ n = n(n+1)/2.

Sowohl bei der Induktionsbasis als auch beim Induktionsschritt

zeigen wir, dass in der entsprechenden Gleichung links und rechts

das Gleiche steht.

Induktionsbasis: Sei n = 1. Dann steht auf der linken Seite nur der

Summand 1, und auf der rechten Seite steht 21/2, also ebenfalls

1. Also gilt A(1)


Die Aussage A(n) sei die Aussage des Satzes, also:

A(n): 1+2+3 +...+ n = n(n+1)/2.

Sowohl bei der Induktionsbasis als auch beim Induktionsschritt

zeigen wir, dass in der entsprechenden Gleichung links und rechts

das Gleiche steht.


Summand 1, und auf der rechten Seite steht 21/2, also ebenfalls

1. Also gilt A(1)


April 2004Seite 10

InduktionsschrittInduktionsschritt

Induktionsschritt: Sei n eine natürliche Zahl 1, und sei die

Aussage richtig für n. Wir müssen A(n+1) beweisen, das heißt, die

Summe 1+2+3+... +(n–1) + n + (n+1) berechnen.

Wir spalten wir diese Summe auf:

1+2+3+... +(n–1) + n + (n+1)

= [1+2+3+... +(n–1) + n] + (n+1)

= n(n+1)/2 + (n+1) (nach Induktion)

= [n(n+1) + 2(n+1)]/2 = (n+2)(n+1)/2.

Insgesamt haben wir die Aussage A(n+1) bewiesen.

Somit gilt der Satz.

Induktionsschritt: Sei n eine natürliche Zahl 1, und sei die

Aussage richtig für n. Wir müssen A(n+1) beweisen, das heißt, die

Summe 1+2+3+... +(n–1) + n + (n+1) berechnen.

Wir spalten wir diese Summe auf:

1+2+3+... +(n–1) + n + (n+1)

= [1+2+3+... +(n–1) + n] + (n+1)

= n(n+1)/2 + (n+1) (nach Induktion)

= [n(n+1) + 2(n+1)]/2 = (n+2)(n+1)/2.

Insgesamt haben wir die Aussage A(n+1) bewiesen.

Somit gilt der Satz.


April 2004Seite 11

Der Trick von GaußDer Trick von Gauß

Gauß hat die Summe 1+2+3+...+100 nicht so bestimmt, sondern mit

folgendem genialen Trick:

1 + 2 + 3 + ... + n–2 + n–1 + n

+ n + n–1 + n–2 + ... + 3 + 2 + 1

= n+1 + n+1 + n+1 + ... + n+1 + n+1 + n+1

= n(n+1).

Also gilt 1+2+3+...+n = n(n+1)/2.

Gauß hat die Summe 1+2+3+...+100 nicht so bestimmt, sondern mit

folgendem genialen Trick:

1 + 2 + 3 + ... + n–2 + n–1 + n

+ n + n–1 + n–2 + ... + 3 + 2 + 1

= n+1 + n+1 + n+1 + ... + n+1 + n+1 + n+1

= n(n+1).

Also gilt 1+2+3+...+n = n(n+1)/2.


April 2004Seite 12

Summe der ungeraden ZahlenSumme der ungeraden Zahlen


1+3+5 + ... + (2n–1) = n2. In Worten: Die Summe der ersten n

ungeraden Zahlen ist gleich der n-ten Quadratzahl.

Beispiele: (a) 1 + 3 + 5 = 9

(b) 1 + 3 + 5 + ... + 1999 = 1.000.000


1+3+5 + ... + (2n–1) = n2. In Worten: Die Summe der ersten n

ungeraden Zahlen ist gleich der n-ten Quadratzahl.

Beispiele: (a) 1 + 3 + 5 = 9

(b) 1 + 3 + 5 + ... + 1999 = 1.000.000


April 2004Seite 13

BeweisBeweis



Summand 1, und auf der rechten Seite steht 12 = 1. Somit gilt A(1).

Induktionsschritt: Sei n eine natürliche Zahl mit n 1, und es gelte

A(n). Wir müssen A(n+1) nachweisen.

Wir beginnen mit der linken Seite von A(n+1) und formen diese so

lange um, bis wir die rechte Seite von A(n+1) erhalten:

1+3+5+ ... + (2n–1) + (2n+1) = [1+3+5+ ... + (2n–1)] + (2n+1)

= n2 + (2n+1) (nach Induktion)

= n2 + 2n + 1 = (n+1)2 .

Somit gilt A(n+1), und damit ist die Aussage bewiesen.



Summand 1, und auf der rechten Seite steht 12 = 1. Somit gilt A(1).

Induktionsschritt: Sei n eine natürliche Zahl mit n 1, und es gelte

A(n). Wir müssen A(n+1) nachweisen.

Wir beginnen mit der linken Seite von A(n+1) und formen diese so

lange um, bis wir die rechte Seite von A(n+1) erhalten:

1+3+5+ ... + (2n–1) + (2n+1) = [1+3+5+ ... + (2n–1)] + (2n+1)

= n2 + (2n+1) (nach Induktion)

= n2 + 2n + 1 = (n+1)2 .

Somit gilt A(n+1), und damit ist die Aussage bewiesen.


April 2004Seite 14

Die Bernoullische UngleichungDie Bernoullische Ungleichung

1.2.3 Satz. Für jede nat. Zahl n und für jede reelle Zahl x -1 gilt

(1+x)n 1 + nx.


Induktionsbasis: Sei n = 1. Dann ist linke Seite = 1+x = rechte Seite;

insbesondere ist linke Seite rechte Seite.

Induktionsschritt: Sei n eine natürliche Zahl mit n 1, und sei die

Behauptung richtig für n. Damit folgt

(1+x)n+1 = (1+x)n(1+x)

(1 + nx) (1+x) (nach Induktion)

= 1 + nx + x + nx2 1 + nx + x = 1 + (n+1)x.

Damit ist der Induktionsschritt bewiesen, und damit gilt der Satz.

1.2.3 Satz. Für jede nat. Zahl n und für jede reelle Zahl x -1 gilt

(1+x)n 1 + nx.


Induktionsbasis: Sei n = 1. Dann ist linke Seite = 1+x = rechte Seite;

insbesondere ist linke Seite rechte Seite.


Behauptung richtig für n. Damit folgt

(1+x)n+1 = (1+x)n(1+x)

(1 + nx) (1+x) (nach Induktion)

= 1 + nx + x + nx2 1 + nx + x = 1 + (n+1)x.

Damit ist der Induktionsschritt bewiesen, und damit gilt der Satz.


April 2004Seite 15

1.3 Landkarten schwarz - weiß1.3 Landkarten schwarz - weiß

Ein Gebiet, etwa ein Erdteil, durch geradlinige Grenzen in Länder

aufgeteilt ist. Die Grenzen sollen dabei so gezogen sein, dass sie

den ganzen Erdteil durchqueren.

Frage: Wieviel Farben braucht man, um die Länder so zu färben,

dass keine zwei Länder, die ein Stück Grenze gemeinsam haben,

gleich gefärbt sind?

Bemerkungen: 1. Länder, die nur einen Punkt gemeinsam haben,

dürfen sehr wohl gleich gefärbt sein.

2. Eine solche Färbung nennt man auch eine zulässige Färbung.

Ein Gebiet, etwa ein Erdteil, durch geradlinige Grenzen in Länder

aufgeteilt ist. Die Grenzen sollen dabei so gezogen sein, dass sie

den ganzen Erdteil durchqueren.

Frage: Wieviel Farben braucht man, um die Länder so zu färben,

dass keine zwei Länder, die ein Stück Grenze gemeinsam haben,

gleich gefärbt sind?

Bemerkungen: 1. Länder, die nur einen Punkt gemeinsam haben,

dürfen sehr wohl gleich gefärbt sein.

2. Eine solche Färbung nennt man auch eine zulässige Färbung.


April 2004Seite 16

Färbung von LandkartenFärbung von Landkarten

1.3.1 Satz. Jede Landkarte, die dadurch entsteht, dass man einen

Erdteil durch Geraden aufteilt, kann mit zwei Farben so gefärbt

werden, dass je zwei Länder, die eine gemeinsame Grenze haben,

verschieden gefärbt sind.

Beweis durch Induktion. Was ist n? Sei n die Anzahl der Geraden,

die den Erdteil aufteilen. Dann lautet A(n) so:

A(n): Jede Landkarte, die dadurch entsteht, dass man einen Erdteil

durch n Geraden aufteilt, kann mit den Farben schwarz und weiß

so gefärbt werden, dass je zwei Länder, die eine gemeinsame

Grenze haben, verschieden gefärbt sind.

1.3.1 Satz. Jede Landkarte, die dadurch entsteht, dass man einen

Erdteil durch Geraden aufteilt, kann mit zwei Farben so gefärbt

werden, dass je zwei Länder, die eine gemeinsame Grenze haben,

verschieden gefärbt sind.

Beweis durch Induktion. Was ist n? Sei n die Anzahl der Geraden,

die den Erdteil aufteilen. Dann lautet A(n) so:

A(n): Jede Landkarte, die dadurch entsteht, dass man einen Erdteil

durch n Geraden aufteilt, kann mit den Farben schwarz und weiß

so gefärbt werden, dass je zwei Länder, die eine gemeinsame

Grenze haben, verschieden gefärbt sind.


April 2004Seite 17

BeweisBeweis

Induktionsbasis: Sei n = 1. Jede Landkarte, die durch Aufteilung

durch nur eine Gerade entsteht, kann mit zwei Farben gefärbt

werden. Klar: Durch eine Gerade entstehen nur zwei Länder, die

man mit zwei Farben färben kann.


Aussage A(n) richtig. Wir müssen beweisen, dass auch A(n+1) gilt.

Dazu betrachten wir eine beliebige Landkarte, die durch Ziehen von

n+1 Geraden g1, g2, ..., gn+1 entstanden ist. Wir müssen zeigen,

dass diese Landkarte zulässig mit den Farben schwarz und weiß

gefärbt werden kann.

Induktionsbasis: Sei n = 1. Jede Landkarte, die durch Aufteilung

durch nur eine Gerade entsteht, kann mit zwei Farben gefärbt

werden. Klar: Durch eine Gerade entstehen nur zwei Länder, die

man mit zwei Farben färben kann.


Aussage A(n) richtig. Wir müssen beweisen, dass auch A(n+1) gilt.

Dazu betrachten wir eine beliebige Landkarte, die durch Ziehen von

n+1 Geraden g1, g2, ..., gn+1 entstanden ist. Wir müssen zeigen,

dass diese Landkarte zulässig mit den Farben schwarz und weiß

gefärbt werden kann.


April 2004Seite 18

Beweis (Der Trick)Beweis (Der Trick)

Sei die Gerade gn+1 waagrecht und betrachten diese Gerade

(vorerst) nicht.

Damit entsteht eine Landkarte, die durch die n Geraden g1,..., gn

entstanden ist. Nach Induktionsvoraussetzung ist diese Landkarte

also mit den Farben schwarz und weiß zulässig färbbar!

Wir müssen die Originallandkarte mit färben! Dazu fügen wir die

(n+1)-te Gerade wieder ein. Dabei entstehen neue Länder.

Wir müssen die Länder, oder jedenfalls einen Teil umfärben.

Trick: Wir färben die obere Hälfte der Karte um! Die Länder im

südlichen Teil der Karte behalten dagegen ihre Farbe.

Sei die Gerade gn+1 waagrecht und betrachten diese Gerade

(vorerst) nicht.

Damit entsteht eine Landkarte, die durch die n Geraden g1,..., gn

entstanden ist. Nach Induktionsvoraussetzung ist diese Landkarte

also mit den Farben schwarz und weiß zulässig färbbar!

Wir müssen die Originallandkarte mit färben! Dazu fügen wir die

(n+1)-te Gerade wieder ein. Dabei entstehen neue Länder.

Wir müssen die Länder, oder jedenfalls einen Teil umfärben.

Trick: Wir färben die obere Hälfte der Karte um! Die Länder im

südlichen Teil der Karte behalten dagegen ihre Farbe.


April 2004Seite 19

Beweis (Abschluss)Beweis (Abschluss)

Behauptung: Diese Färbung ist zulässig.

1. Fall: Die Grenze von L und L' liegt unterhalb von gn+1. Dann

hatten die Länder L, L' verschiedene Farbe. Da sich unten nichts

geändert hat, haben L und L' nach wie vor verschiedene Farbe.

2. Fall: Die Grenze von L und L' liegt oberhalb von gn+1. Oberhalb

von gn+1 hat sich alles geändert. Da L und L' vorher verschiedene

Farben hatten, haben sie auch jetzt verschiedene Farben.

3. Fall: Die Grenze von L und L' liegt auf gn+1. Dann sind L und

L' durch Aufteilung eines alten Landes L* entstanden. Wenn L*

weiß war, bleibt L weiß, während L' schwarz wird.

Behauptung: Diese Färbung ist zulässig.

1. Fall: Die Grenze von L und L' liegt unterhalb von gn+1. Dann

hatten die Länder L, L' verschiedene Farbe. Da sich unten nichts

geändert hat, haben L und L' nach wie vor verschiedene Farbe.

2. Fall: Die Grenze von L und L' liegt oberhalb von gn+1. Oberhalb

von gn+1 hat sich alles geändert. Da L und L' vorher verschiedene

Farben hatten, haben sie auch jetzt verschiedene Farben.

3. Fall: Die Grenze von L und L' liegt auf gn+1. Dann sind L und

L' durch Aufteilung eines alten Landes L* entstanden. Wenn L*

weiß war, bleibt L weiß, während L' schwarz wird.


April 2004Seite 20

Das VierfarbenproblemDas Vierfarbenproblem

Berühmtes Problem der Mathematik:

Wie viele Farben braucht man, um eine beliebige Landkarte, also

eine Landkarte, die nicht durch Ziehen von Geraden entsteht,

zulässig zu färben? Über 100 Jahre war die Vermutung, dass vier

Farben ausreichen, unbewiesen.

1976 haben die Amerikaner Apel und Haken mit massivem

Computereinsatz den “Vierfarbensatz” beweisen. Dabei bauten sie

entscheidend auf Vorarbeiten des Deutschen H. Heesch auf.

Berühmtes Problem der Mathematik:

Wie viele Farben braucht man, um eine beliebige Landkarte, also

eine Landkarte, die nicht durch Ziehen von Geraden entsteht,

zulässig zu färben? Über 100 Jahre war die Vermutung, dass vier

Farben ausreichen, unbewiesen.

1976 haben die Amerikaner Apel und Haken mit massivem

Computereinsatz den “Vierfarbensatz” beweisen. Dabei bauten sie

entscheidend auf Vorarbeiten des Deutschen H. Heesch auf.


April 2004Seite 21

1.4 Die Fibonacci-Zahlen1.4 Die Fibonacci-Zahlen

Fibonacci (= Leonardo von Pisa) um 1200

Definition der Fibonacci-Zahlen:

(a) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

(b) Jedes Folgenglied ist die Summe seiner beiden Vorgänger.

(c) Wir definieren die Folge f1, f2, f3, ... von natürlichen Zahlen mit

folgenden Eigenschaften:

fn = fn–1+ fn–2

und

f1 = 1, f2 = 1.

Fibonacci (= Leonardo von Pisa) um 1200

Definition der Fibonacci-Zahlen:

(a) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

(b) Jedes Folgenglied ist die Summe seiner beiden Vorgänger.

(c) Wir definieren die Folge f1, f2, f3, ... von natürlichen Zahlen mit

folgenden Eigenschaften:

fn = fn–1+ fn–2

und

f1 = 1, f2 = 1.


April 2004Seite 22

BeispieleBeispiele

• Kaninchen (jedenfalls mathematische Kaninchen) vermehren sich

nach folgenden Regeln:

– Jedes Kaninchenpaar braucht nach seiner Geburt zwei Monate, bis es geschlechtsreif ist.

– Von da an gebiert es in jedem Monat ein neues Paar

– Alle Kaninchen leben ewig.

Wenn fn die Anzahl der Kaninchen zu Beginn des n-ten Monats

bezeichnet. Dann sind die fn genau die Fibonacci-Zahlen.

• Ein Briefträger steigt eine lange Treppe hoch, indem er die erste

Stufe betritt und von da an jeweils eine oder genau zwei Stufen auf

einmal nimmt. Auf wie viele Arten kann er die n-te Stufe erreichen?

• Kaninchen (jedenfalls mathematische Kaninchen) vermehren sich

nach folgenden Regeln:

– Jedes Kaninchenpaar braucht nach seiner Geburt zwei Monate, bis es geschlechtsreif ist.

– Von da an gebiert es in jedem Monat ein neues Paar

– Alle Kaninchen leben ewig.

Wenn fn die Anzahl der Kaninchen zu Beginn des n-ten Monats

bezeichnet. Dann sind die fn genau die Fibonacci-Zahlen.

• Ein Briefträger steigt eine lange Treppe hoch, indem er die erste

Stufe betritt und von da an jeweils eine oder genau zwei Stufen auf

einmal nimmt. Auf wie viele Arten kann er die n-te Stufe erreichen?


April 2004Seite 23

Beispiele aus der BiologieBeispiele aus der Biologie

• Bei Pflanzen kommen Fibonacci-Zahlen häufig vor.

• Beispiele: Bei Sonnenblumen sind die Kerne in Spiralen

angeordnet, die nach links und nach rechts drehen. Die Anzahlen

der linksdrehenden und der rechtsdrehenden Spiralen sind

aufeinanderfolgende Fibonacci-Zahlen.

Ähnlich bei Gänseblümchen, Ananas, (manchen) Kakteen, ....

• Bei Pflanzen kommen Fibonacci-Zahlen häufig vor.

• Beispiele: Bei Sonnenblumen sind die Kerne in Spiralen

angeordnet, die nach links und nach rechts drehen. Die Anzahlen

der linksdrehenden und der rechtsdrehenden Spiralen sind

aufeinanderfolgende Fibonacci-Zahlen.

Ähnlich bei Gänseblümchen, Ananas, (manchen) Kakteen, ....


April 2004Seite 24

Wie kann man Fibonacci-Zahlen ausrechnen?Wie kann man Fibonacci-Zahlen ausrechnen?

1. Durch Anwenden der rekursiven Definition.

2. Durch Anwenden der folgenden expiziten Formel:

1.4.1 Satz (Binet-Formel). Für jede natürliche Zahl n 1 gilt

fn = [((1+5)/2)n – ((1–5)/2)n] / 5.

Bemerkung. Das Erstaunliche an dieser Formel ist, dass sich für

jedes n die Wurzelterme so weg heben, dass nur eine natürliche

Zahl, nämlich fn stehenbleibt.

1. Durch Anwenden der rekursiven Definition.

2. Durch Anwenden der folgenden expiziten Formel:

1.4.1 Satz (Binet-Formel). Für jede natürliche Zahl n 1 gilt

fn = [((1+5)/2)n – ((1–5)/2)n] / 5.

Bemerkung. Das Erstaunliche an dieser Formel ist, dass sich für

jedes n die Wurzelterme so weg heben, dass nur eine natürliche

Zahl, nämlich fn stehenbleibt.


April 2004Seite 25

Beweis (Induktionsbasis)Beweis (Induktionsbasis)

Beweis durch Induktion nach n. Die Aussage A(n) ist

A(n): fn = [((1+5)/2)n – ((1–5)/2)n] / 5.

Induktionsbasis: Sei n = 1. Wir müssen die Aussage A(1) beweisen.

Dazu rechnen wir einfach die Formel (also die rechte Seite) für den

Fall n = 1 aus:

[((1+5)/2)1 – ((1–5)/2)1] / 5 = [(1+5)/2 – (1–5)/2] / 5 =

[25)/2] / 5 = 1

Damit gilt A(1).

Beweisen Sie A(2): Übungsaufgabe.

Beweis durch Induktion nach n. Die Aussage A(n) ist

A(n): fn = [((1+5)/2)n – ((1–5)/2)n] / 5.

Induktionsbasis: Sei n = 1. Wir müssen die Aussage A(1) beweisen.

Dazu rechnen wir einfach die Formel (also die rechte Seite) für den

Fall n = 1 aus:

[((1+5)/2)1 – ((1–5)/2)1] / 5 = [(1+5)/2 – (1–5)/2] / 5 =

[25)/2] / 5 = 1

Damit gilt A(1).

Beweisen Sie A(2): Übungsaufgabe.


April 2004Seite 26

Beweis (Induktionsschritt)Beweis (Induktionsschritt)

Induktionsschritt: Sei n eine natürliche Zahl mit n 2, und es

mögen die Aussagen A(n) und A(n–1) gelten.

Wir müssen zeigen, dass dann auch A(n+1) gilt. Dazu verwenden

wir die Rekursionsformel fn+1 = fn + fn–1, und wenden sowohl auf fn

also auch auf fn–1 die Induktionsvoraussetzung an:

fn+1 = fn + fn–1 =

[((1+5)/2)n – ((1–5)/2)n] / 5 + [((1+5)/2)n–1 – ((1–5)/2)n–1] / 5

= [((1+5)/2)n–1[(1+ 5)/2 + 1] – ((1–5)/2)n–1[(1– 5)/2 + 1]] / 5 ...

Wie kann man diese monströse Formel auflösen ???

Induktionsschritt: Sei n eine natürliche Zahl mit n 2, und es

mögen die Aussagen A(n) und A(n–1) gelten.

Wir müssen zeigen, dass dann auch A(n+1) gilt. Dazu verwenden

wir die Rekursionsformel fn+1 = fn + fn–1, und wenden sowohl auf fn

also auch auf fn–1 die Induktionsvoraussetzung an:

fn+1 = fn + fn–1 =

[((1+5)/2)n – ((1–5)/2)n] / 5 + [((1+5)/2)n–1 – ((1–5)/2)n–1] / 5

= [((1+5)/2)n–1[(1+ 5)/2 + 1] – ((1–5)/2)n–1[(1– 5)/2 + 1]] / 5 ...

Wie kann man diese monströse Formel auflösen ???


April 2004Seite 27

Beweis (das Wunder)Beweis (das Wunder)

Wir können die kleinen eckigen Klammern günstig umformen:

[(1+5)/2 + 1] = [(1+5)/2]2 = [(1–5)/2 + 1] = [(1–5)/2]2 .

Man sieht beide Formeln sofort ein, wenn man die jeweiligen rechten

Seiten ausrechnet.

Nun kann uns aber nichts mehr hindern, weiterzurechnen:

... = [((1+5)/2)n–1 [(1+5)/2]2 – ((1–5)/2)n–1 [(1–5)/2]2 ] / 5

= [((1+5)/2)n+1 – ((1–5)/2)n+1] / 5.

... und damit ist die Aussage A(n+1) bewiesen.

Nach dem Prinzip der vollständigen Induktion gilt also die Aussage.

Wir können die kleinen eckigen Klammern günstig umformen:

[(1+5)/2 + 1] = [(1+5)/2]2 = [(1–5)/2 + 1] = [(1–5)/2]2 .

Man sieht beide Formeln sofort ein, wenn man die jeweiligen rechten

Seiten ausrechnet.

Nun kann uns aber nichts mehr hindern, weiterzurechnen:

... = [((1+5)/2)n–1 [(1+5)/2]2 – ((1–5)/2)n–1 [(1–5)/2]2 ] / 5

= [((1+5)/2)n+1 – ((1–5)/2)n+1] / 5.

... und damit ist die Aussage A(n+1) bewiesen.

Nach dem Prinzip der vollständigen Induktion gilt also die Aussage.


April 2004Seite 28

Ein ZaubertrickEin Zaubertrick

8

5

13

13

8 8

8

5

5

8


April 2004Seite 29

Simpson-IdentitätSimpson-Identität

1.4.2 Satz. Für jede natürliche Zahl n 2 gilt

fn+1fn–1 – fn2 = (–1)n.

In Worten: fn+1fn–1 und fn2 unterscheiden sich nur um 1, mal um

+1, mal um –1.


Die Aussage A(n) sei die Aussage des Satzes.

Induktionsbasis. Sei n = 2. Wir müssen die Aussage A(2) zeigen.

Dazu rechnen wir einfach die linke Seite aus:

L.S. = f3f1 – f22 = 21 – 12 = 1 = (–1)2 = R.S.

1.4.2 Satz. Für jede natürliche Zahl n 2 gilt

fn+1fn–1 – fn2 = (–1)n.

In Worten: fn+1fn–1 und fn2 unterscheiden sich nur um 1, mal um

+1, mal um –1.


Die Aussage A(n) sei die Aussage des Satzes.

Induktionsbasis. Sei n = 2. Wir müssen die Aussage A(2) zeigen.

Dazu rechnen wir einfach die linke Seite aus:

L.S. = f3f1 – f22 = 21 – 12 = 1 = (–1)2 = R.S.


April 2004Seite 30

Beweis (Induktionsschritt)Beweis (Induktionsschritt)

Induktionsschritt. Sei n eine natürliche Zahl 2, und es gelte die

Aussage A(n). Wir müssen A(n+1) zeigen. Auch dazu rechnen wir

einfach die entsprechende linke Seite aus:

fn+2fn – fn+12 = (fn+1 + fn) fn – fn+1

2

= fn+1(fn - fn+1) + fn2

= fn+1(fn - fn+1) + fn+1fn–1 – (–1)n (nach Induktion)

= fn+1(fn + fn-1 – fn+1) + (–1)n+1

= fn+10 + (–1)n+1 = (–1)n+1.

Somit gilt die Aussage A(n+1).

Induktionsschritt. Sei n eine natürliche Zahl 2, und es gelte die

Aussage A(n). Wir müssen A(n+1) zeigen. Auch dazu rechnen wir

einfach die entsprechende linke Seite aus:

fn+2fn – fn+12 = (fn+1 + fn) fn – fn+1

2

= fn+1(fn - fn+1) + fn2

= fn+1(fn - fn+1) + fn+1fn–1 – (–1)n (nach Induktion)

= fn+1(fn + fn-1 – fn+1) + (–1)n+1

= fn+10 + (–1)n+1 = (–1)n+1.

Somit gilt die Aussage A(n+1).

Documents

Kapitel 1 Vollständige Induktion. Kapitel 1 © Beutelspacher April 2004 Seite 2 Inhalt 1.1 Das Prinzip A(n) A(n+1) 1.2 Anwendungen 1 + 2 + 3 +... + n =