Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Induktion
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Induktion
 
Autor Nachricht
Pat
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 26 Okt 2005 - 21:04:12    Titel: Induktion

Folgende Aufgabe:
Zu beweisen ist A(n): n! >= 2^(n-1)

Induktionsannahme: für natürliche Zahl k gilt A(k): k! >= 2^(k-1)
Induktionsschritt: Zeige dass A(k+1): (k+1)! >= 2^((k+1)-1) wahr ist

k! >= 2^(k-1) |*(k+1)

-> (k+1)*k! >= (k+1)*2^(k-1)

-> (k+1)! >= 2k^(k-1)+2^(k-1)

und weiter komm ich nicht! Wär super wenn jemand helfen könnte
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 26 Okt 2005 - 21:16:57    Titel:

Zitat:
k! >= 2^(k-1) |*(k+1)


Ein typischer Fehler. Bei Induktion ist im Induktionsschritt zunächst nach der Definition der vollständigen Induktion nicht vom Fall n auszugehen und den Fall von n+1 zu konstruieren! Es gilt den Fall für n+1 zu betrachten und den auf den Fall für n unter Beachtung der I.A. zu reduzieren.

Der von vielen begangene Fehler entsteht, indem man die Konstruktion des Falls mit n+1 aus n nicht vollständig durchführt. Z.b. kann man so "zeigen", dass jeder Graph einen Kreis enthält:

Basis: Einpünktige Graphen enthalten immer einen Kreis.

I.Annahme: Ein Graph mit n Knoten enthält einen Kreis.

I.Schritt: Nehmen wir einen Graphen mit n-Knoten. Der enthält nach I.A. einen Kreis und fügen einen Knoten hinzu. Egal, wie wir die Kanten dann setzten entsteht ein Graph mit n+1 Knoten, der einen Kreis hat. qed.

Typischer 0-Punkte-Beweis, wie der obige.
Pat
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 26 Okt 2005 - 21:22:42    Titel:

Könntest du mir das konkret an der Aufgabe erklären, ich weiß nämlich immer noch nich weiter
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 26 Okt 2005 - 21:29:35    Titel:

Was war daran unverständlich? Du sollst einen anderen Ansatz wählen und (n+1)! >= 2^((n+1)-1) zeigen unter Verwendung von n! >= 2^(n-1). Gehe dabei von (n+1)! und verkleinere so lange, bis Du 2^((n+1)-1) bekommst.

Wenn Du die Aufgabe vorgerechnet haben willst, so musst Du auf andere warten. Ich will Dir helfen - nicht Dir die Arbeit beim Lösen deiner Übungsblätter reduzieren.
brabe
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.10.2005
Beiträge: 2807
Wohnort: Lehrerzimmer

BeitragVerfasst am: 27 Okt 2005 - 10:00:57    Titel: Re: Induktion

Pat hat folgendes geschrieben:
Folgende Aufgabe:
Zu beweisen ist A(n): n! >= 2^(n-1)

Induktionsannahme: für natürliche Zahl k gilt A(k): k! >= 2^(k-1)
Induktionsschritt: Zeige dass A(k+1): (k+1)! >= 2^((k+1)-1) wahr ist

k! >= 2^(k-1) |*(k+1)
-> (k+1)*k! >= (k+1)*2^(k-1)
-> (k+1)! >= 2k^(k-1)+2^(k-1)

und weiter komm ich nicht! Wär super wenn jemand helfen könnte



n=1
1>=1

n->n+1
2^(n+1-1)
<=2*2^n-1
<=2*k!
<=(k+1)*k!
=(k+1)!

wobei ich algebrafreak zustimme, man hätte es auch selbst rechen können^^
tipp, immer <= abschätzen
denn nach oben ist meist viel platz
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Induktion
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum