Autor |
Beitrag |
Andy Treisch (Atreisch)
| Veröffentlicht am Freitag, den 26. Oktober, 2001 - 23:17: |
|
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 |
Thomas
| Veröffentlicht am Samstag, den 27. Oktober, 2001 - 14:21: |
|
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 |
Rainer Karsch
| Veröffentlicht am Samstag, den 27. Oktober, 2001 - 20:44: |
|
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 |
Rainer Karsch
| Veröffentlicht am Sonntag, den 28. Oktober, 2001 - 11:46: |
|
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 |
|