Rekursion und Induktion
Rekursion und Induktion
Vorsemesterkurs InformatikTheoretischer Teil
Wintersemester 2012/13
4. Oktober 2012
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Definition der Rekursion fur Funktionen
Definition
Eine rekursive Funktion ist eine Funktion, die durch sich selbstdefiniert ist.(Salopp: eine Funktion, die sich im Rumpf selbst aufruft)
Ein offenes Problem aus der Mathematik:
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Collatz-Problem: Kommt es fur jeden naturlichen Startwert nirgendwann zu einer c(4)-c(2)-c(1)-Endlosschleife?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Definition der Rekursion fur Funktionen
Definition
Eine rekursive Funktion ist eine Funktion, die durch sich selbstdefiniert ist.(Salopp: eine Funktion, die sich im Rumpf selbst aufruft)
Ein offenes Problem aus der Mathematik:
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Collatz-Problem: Kommt es fur jeden naturlichen Startwert nirgendwann zu einer c(4)-c(2)-c(1)-Endlosschleife?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Definition der Rekursion fur Funktionen
Definition
Eine rekursive Funktion ist eine Funktion, die durch sich selbstdefiniert ist.(Salopp: eine Funktion, die sich im Rumpf selbst aufruft)
Ein offenes Problem aus der Mathematik:
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Collatz-Problem: Kommt es fur jeden naturlichen Startwert nirgendwann zu einer c(4)-c(2)-c(1)-Endlosschleife?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5)
= c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Wir testen es fur den Startwert n = 5:
c(5) = c(5 · 3 + 1) = c(16)
= c(16/2) = c(8)
= c(4)
= c(2)
= c(1)
= c(3 · 1 + 1) = c(4) = . . .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Was ist Rekursion?
Auswertung der Funktion
Beispiel
c(n) :=
{c(n/2), falls n gerade ist
c(3n + 1), falls n ungerade ist
Mit anderen Startwerten:
c(n) n-Folge bis zur ersten 1
c(3) 3, 10, 5, 16, 8, 4, 2, 1c(5) 5, 16, 8, 4, 2, 1c(15) 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
c(16) 16, 8, 4, 2, 1c(128) 128, 64, 32, 16, 8, 4, 2, 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Anwendungen in der Informatik
Wieso interessiert uns sowas uberhaupt in der Informatik?
Rekursionen tauchen sehr haufig auf:
Laufzeitanalyse
Algorithmenentwurf und Programmiertechnik
Datenstrukturen
funktionale Programmierung → Haskell (PRG-2)
Syntax von (Programmier-)Sprachen
Ubersetzer (Compiler)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Basis- und Rekursionsfall
wieder ein bisschen Fachchinesisch
Definition (Basisfall)
Als Basisfall in einer Rekursion bezeichnet man einen Fall, in dem dieFunktion nicht noch einmal aufgerufen wird.
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Quizfrage der Folie
Wo ist hier der Basisfall ??
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Basis- und Rekursionsfall
wieder ein bisschen Fachchinesisch
Definition (Basisfall)
Als Basisfall in einer Rekursion bezeichnet man einen Fall, in dem dieFunktion nicht noch einmal aufgerufen wird.
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Quizfrage der Folie
Wo ist hier der Basisfall ??
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Basis- und Rekursionsfall
. . . und noch mehr Fachchinesisch :-P
Definition (Rekursionsfall)
Als Rekursionsfall in einer Rekursion beschreibt man einen Fall, in demdie Funktion noch einmal aufgerufen wird.
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Quizfrage der Folie
Wo ist hier der Rekursionsfall ??
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Basis- und Rekursionsfall
. . . und noch mehr Fachchinesisch :-P
Definition (Rekursionsfall)
Als Rekursionsfall in einer Rekursion beschreibt man einen Fall, in demdie Funktion noch einmal aufgerufen wird.
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Quizfrage der Folie
Wo ist hier der Rekursionsfall ??
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Rekursionsturmchen
Turmchen bauen
Einfache Rekursionen sind wie Turmchen:
f(n) Dach
f(n-1) Stockwerkef(n-2)...f(1)
f(0) Erdgeschoss
(Animation siehe nachste Folie)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Rekursionsturmchen
...zur Animation
zur Animation
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Rekursionsturmchen
...und als Sequenzdiagramm
zur Animation
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Rekursionsturmchen
Achtung!
Es gibt noch andere Formen der Rekursion:
verzweigte Baumchen statt Turmchen(die Funktion ruft sich mehrfach selbst auf)
verschrankte Rekursion(zwei Funktionen rufen sich gegenseitig auf)
verschachtelte Rekursion(das Argument ist selbst wieder eine rekursive Funktion)
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Rekursion > Rekursionsturmchen
noch Fragen???
Quelle Bild: http://www.citycampus.eu/cms/images/comic fragezeichen.png
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Nochmal zuruck zur Funktion
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Was berechnet f ?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Nochmal zuruck zur Funktion
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Was berechnet f ?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Nochmal zuruck zur Funktion
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Was berechnet f ?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Wir vermuten, dass f die Fakultatsfunktion ist. Doch lasst sich dasbeweisen? Auch dafur gibt es eine Beweistechnik: Die vollstandigeInduktion. Sie besteht aus zwei Teilen:
Induktionsanfang: Wir uberprufen, ob die Aussagen fur dieRekursionsbasis gilt.
Induktionsschritt: Wir nehmen an, dass im rekursiven Aufrufunsere Aussage stimmt. Dann weisen wir das nur noch fur denRest nach!
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Wir vermuten, dass f die Fakultatsfunktion ist. Doch lasst sich dasbeweisen?
Auch dafur gibt es eine Beweistechnik: Die vollstandigeInduktion. Sie besteht aus zwei Teilen:
Induktionsanfang: Wir uberprufen, ob die Aussagen fur dieRekursionsbasis gilt.
Induktionsschritt: Wir nehmen an, dass im rekursiven Aufrufunsere Aussage stimmt. Dann weisen wir das nur noch fur denRest nach!
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Wir vermuten, dass f die Fakultatsfunktion ist. Doch lasst sich dasbeweisen? Auch dafur gibt es eine Beweistechnik: Die vollstandigeInduktion. Sie besteht aus zwei Teilen:
Induktionsanfang: Wir uberprufen, ob die Aussagen fur dieRekursionsbasis gilt.
Induktionsschritt: Wir nehmen an, dass im rekursiven Aufrufunsere Aussage stimmt. Dann weisen wir das nur noch fur denRest nach!
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Wir vermuten, dass f die Fakultatsfunktion ist. Doch lasst sich dasbeweisen? Auch dafur gibt es eine Beweistechnik: Die vollstandigeInduktion. Sie besteht aus zwei Teilen:
Induktionsanfang: Wir uberprufen, ob die Aussagen fur dieRekursionsbasis gilt.
Induktionsschritt: Wir nehmen an, dass im rekursiven Aufrufunsere Aussage stimmt. Dann weisen wir das nur noch fur denRest nach!
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Einleitung
Vollstandige Induktion
Wir vermuten, dass f die Fakultatsfunktion ist. Doch lasst sich dasbeweisen? Auch dafur gibt es eine Beweistechnik: Die vollstandigeInduktion. Sie besteht aus zwei Teilen:
Induktionsanfang: Wir uberprufen, ob die Aussagen fur dieRekursionsbasis gilt.
Induktionsschritt: Wir nehmen an, dass im rekursiven Aufrufunsere Aussage stimmt. Dann weisen wir das nur noch fur denRest nach!
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Behauptung
f (n) = n! fur jede beliebige Eingabe n ∈ N
Beweis durch vollstandige Induktion nach n:
Induktionsanfang: n = 0
f (0) = 1 und 0! = 1, also f (0) = 0! .
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Anwendungsbeispiel
Korrektheitsbeweis fur rekursive Funktionen
f : N→ Nf (0) = 1
f (n) = f (n − 1) · n, falls n > 0
Induktionsschritt: n→ n + 1
Angenommen, fur festes n gilt f (n) = n!. Wir wollen zeigen, dassdann auch f (n + 1) = (n + 1)! gilt.
f (n + 1)Def. von f
= (n + 1) ∗ f (n)IA= (n + 1) ∗ n! = (n + 1)!
Also berechnet f fur jede Eingabe deren Fakultat. �
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Induktion auf N
Vollstandige Induktion auf N
Analog besteht auch die Induktion auf N aus zwei Schritten:
Der Induktionsanfang : Die Aussage ist fur n = 0 zu prufen.(Fur Mengen wie N≥2 nehmen wir n = 2 als Induktionsanfang)
Der Induktionsschritt: Wir nehmen an, dass die Aussage fur einfestes n ∈ N gilt, und weisen dann nach, dass sie fur n + 1 gilt.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Induktion auf N
Vollstandige Induktion auf N
Analog besteht auch die Induktion auf N aus zwei Schritten:
Der Induktionsanfang : Die Aussage ist fur n = 0 zu prufen.(Fur Mengen wie N≥2 nehmen wir n = 2 als Induktionsanfang)
Der Induktionsschritt: Wir nehmen an, dass die Aussage fur einfestes n ∈ N gilt, und weisen dann nach, dass sie fur n + 1 gilt.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Induktion auf N
Vollstandige Induktion auf N
Analog besteht auch die Induktion auf N aus zwei Schritten:
Der Induktionsanfang : Die Aussage ist fur n = 0 zu prufen.
(Fur Mengen wie N≥2 nehmen wir n = 2 als Induktionsanfang)
Der Induktionsschritt: Wir nehmen an, dass die Aussage fur einfestes n ∈ N gilt, und weisen dann nach, dass sie fur n + 1 gilt.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Induktion auf N
Vollstandige Induktion auf N
Analog besteht auch die Induktion auf N aus zwei Schritten:
Der Induktionsanfang : Die Aussage ist fur n = 0 zu prufen.(Fur Mengen wie N≥2 nehmen wir n = 2 als Induktionsanfang)
Der Induktionsschritt: Wir nehmen an, dass die Aussage fur einfestes n ∈ N gilt, und weisen dann nach, dass sie fur n + 1 gilt.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Induktion auf N
Vollstandige Induktion auf N
Analog besteht auch die Induktion auf N aus zwei Schritten:
Der Induktionsanfang : Die Aussage ist fur n = 0 zu prufen.(Fur Mengen wie N≥2 nehmen wir n = 2 als Induktionsanfang)
Der Induktionsschritt: Wir nehmen an, dass die Aussage fur einfestes n ∈ N gilt, und weisen dann nach, dass sie fur n + 1 gilt.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Korrektheit
Das Prinzip der Induktion
Gilt eine Aussage fur n = 0 und gilt sie unter der Annahme, dass siefur n gilt, auch fur n + 1, dann gilt sie fur alle naturlichen Zahlen.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Korrektheit
Das Prinzip der Induktion
Gilt eine Aussage fur n = 0 und gilt sie unter der Annahme, dass siefur n gilt, auch fur n + 1, dann gilt sie fur alle naturlichen Zahlen.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Korrektheit
Das Prinzip der Induktion
Gilt eine Aussage fur n = 0 und gilt sie unter der Annahme, dass siefur n gilt, auch fur n + 1, dann gilt sie fur alle naturlichen Zahlen.
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Summen- und Produktzeichen
Ein paar Kleinigkeiten...
Definition (Summen- und Produktzeichen)
Sei n ∈ N. Seien a1, ..., an beliebige Zahlen. Dann ist:
n∑i=1
ai = a1 + · · ·+ an
n∏i=1
ai = a1 · · · · · an
Spezialfalle:
0∑i=1
ai = 0,0∏
i=1
ai = 1
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
Beispiel einer vollstandigen Induktion auf N
Wir wollen im Folgenden zeigen:
Satz
Fur alle n ∈ N gilt:n∑
i=0
i =n · (n + 1)
2
Wie sieht der Induktionsanfang aus?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
Beispiel einer vollstandigen Induktion auf N
Wir wollen im Folgenden zeigen:
Satz
Fur alle n ∈ N gilt:n∑
i=0
i =n · (n + 1)
2
Wie sieht der Induktionsanfang aus?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
Beispiel einer vollstandigen Induktion auf N
Wir wollen im Folgenden zeigen:
Satz
Fur alle n ∈ N gilt:
n∑i=0
i =n · (n + 1)
2
Wie sieht der Induktionsanfang aus?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
Beispiel einer vollstandigen Induktion auf N
Wir wollen im Folgenden zeigen:
Satz
Fur alle n ∈ N gilt:n∑
i=0
i =n · (n + 1)
2
Wie sieht der Induktionsanfang aus?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
Beispiel einer vollstandigen Induktion auf N
Wir wollen im Folgenden zeigen:
Satz
Fur alle n ∈ N gilt:n∑
i=0
i =n · (n + 1)
2
Wie sieht der Induktionsanfang aus?
Vorsemesterkurs WS 2012/13
Rekursion und Induktion > Induktion > Beispiel
noch Fragen???
Quelle Bild: http://www.citycampus.eu/cms/images/comic fragezeichen.png
Vorsemesterkurs WS 2012/13