>>> Hast du diesen Monat weniger als 16 Bücher gelesen? - Dann klick hier! <<<


Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Induktion und direkter beweis ?

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Klassen 12/13 » Beweisführung » Induktion und direkter beweis ? « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Andy Treisch (Atreisch)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 26. Oktober, 2001 - 23:17:   Beitrag drucken

Hallo!!
ich hab hier zwei nette aufgaben, mit denen ich nicht zurechtkomme. die erste wäre:

für welche n element N gilt folgende aussage:
n! <= 2(n/2)^n

Ich nehme mal an, man kann das durch direkten beweis lösen, aber ich komm einfach nicht drauf.

Die nächste aufgabe wäre:

Führe einen induktionsbeweis um zu zeigen, dass eine n-elementige menge 2^n teilmengen besitzt.

bitte helft mir...

Andy
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Thomas
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 27. Oktober, 2001 - 14:21:   Beitrag drucken

Hallo Andy,

zum Beweis der zweiten Aussage:

Induktionsanfang: Einelementige Menge (a) hat die Teilmengen (a) und (), also 2 Stück.

Induktionsschritt: Wähle ein festes Element x aus der n+1-elementigen Menge aus. Die Menge der Teilmengen zerfällt in 2 Hälften. Einmal alle Teilmengen die x enthalten und die, welche x nicht enthalten. (Das sind jeweils gleich viele.) Die zweite Menge von Teilmengen hat nach Voraussetzung 2^n Elemente. Also sind es insgesamt 2*2^n=2^(n+1).

Grüße,
Thomas
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Rainer Karsch
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 27. Oktober, 2001 - 20:44:   Beitrag drucken

Hallo Andy,
zur ersten Aussage:
Induktionsanfang:
n=0 0!=1<=2(0/2)^0=1 wahre Aussage (0^0=1 nach dem Prinzip der stetigen Fortsetzung lim n^n = 0 für n gegen 0)
n=1 1!<=2(1/2)^1 wahre Aussage
Induktionsschritt: n!<=2(n/2)^n sei wahr für alle natürlichen Zahlen <= n. Dann gilt:
(n+1)!=n!(n+1)<= 2(n/2)^n*(n+1)=
2n^n *(n+1)/2^n<={siehe Nebenrechnung}
(n+1)^n*(n+1)/2^n=(n+1)^(n+1)/2^n=
2(n+1)^(n+1)/2^(n+1)=2((n+1)/2)^(n+1) q.e.d.
Nebenrechnung:
Für die höheren Binome gilt:
(a+b)^n=a^n+n*a^(n-1)*b+...+b^n
für a=n und b=1 ergibt dies:
(n+1)^n=n^n+n*n^(n-1)*1+...+1^n>=n^n+n^n=2n^n
Die Aussage gilt für alle natürlichen n>=0
Grüße,
Rainer
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Rainer Karsch
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 28. Oktober, 2001 - 11:46:   Beitrag drucken

Hallo Andy,
um die erste Aufgabe direkt zu beweisen, braucht man mehrere gute Ideen hintereinander:
Also
n!<=2(n/2)^n <=>
n!<=n^n/2^(n-1) <=>
2^(n-1)<=n^n/n!

Um die letzte Aussage zu beweisen, benötigen wir folgende Nebenrechnung:
Für n>=1 gilt die Bernullische Ungleichung:
(1+x)^n=1^n+n*1^(n-1)*x+...+x^n<=1+n*x
Für x=1/n erhält man:
(1+1/n)^n<=1+n*1/n <=>
(1+1/n)^n<=2

Nun beweist man 2^(n-1)<=n^n/n! wie folgt:
2^(n-1)=2*2*2*...*2<=
(1+1/1)^1*(1+1/2)^2*(1+1/3)^3*...*(1+1/(n-1))^(n-1)=
(2/1)^1*(3/2)^2*(4/3)^3*...*(n/^(n-1))^(n-1)=
{kürzen!}1/1*1/2*1/3*...*n^(n-1)/(n-1)=
n^(n-1)/(n-1)!=n^(n-1)/(n-1)!*n/n=
n^n/n!
q.e.d.

Da die Bernullische Ungleichung für n<=1 gilt, stimmt auch die zu beweisenden Aussage für n<=1.
Viel Spaß beim nachrechnen
Gruß,
Rainer

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.


Und wie gehts weiter? Klick hier!
Learn-in! Mathematik Soforthilfe. Klick jetzt! Hier könnte Ihre Werbung erscheinen. Kontakt: werbung@zahlreich.de Sprachreisen. Hier kostenlosen Katalog bestellen!

ad
>>> Willst du die besten Proben und Gutscheine? - Dann klick hier! <<<

Informationen: Induktion und direkter beweis ? |  Soforthilfe Mathematik |  Online Mathebuch |  Bronstein

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page