Beweis einer Ungleichung durch Induktion

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Nach Induktionsvoraussetzung gilt: (n+1)! =(n+1) * n! <= 4 * (n/2)^(n+1).

Es ist also zu beweisen 4 * (n/2)^(n+1) <= 4 * (( n+1)/2)^(n+2) [*]

Nun ist die letztere Ungleichung äquivalent zu 1 <= ((n+1)/n)^(n+1) * 1/2; äquivalent zu
1<= (1+1/n)^(n+1) * 1/2; äquivalent zu 2 <=(1+1/n)^(n+1)

Letztere Ungleichung ist aber offensichtlich richtig für n>=1 und damit frolgt die Ungleichung [*] und damit die Beh.

Noch eine Bemerkung hierzu: Die Ungleichung ist gar nicht so schlecht, denn die richtige Größenordnung für das Wachstum der Fakultät ist nach der Stirlingschen Formel (n/e)^n * wurzel(n).

Noch eine Anmerkung: Die Ungleichung 2 <=(1+1/n)^(n+1) ist nur offensichtlich richtig, wenn man die Bernoullische Ungleichung kennt: also (1+x)^n >=1+nx (Voraussetzung x>=-1, n natürlich). Setzt man hier nämlich x=1/n ein so hat man (1+1/n)^n>= 2 und damit erst recht (1+1/n)^(n+1) >= 2. Die Bernoulische Ungleichung erhält man aber einfach aus der binomischen Formel für (1+x)^n , wenn man alle höheren Potenzen von x als 1 wegläßt.

0
@Rowal

Aber eigentlich ist die Induktionsannahme doch nur n! <= 4 * (n/2)^(n+1). Das mit n+1 muss man doch noch bewesien oder??

0

Nach Induktionvaoraussetzung gilt doch eig nur: n! <= 4 * (n/2)^(n+1). Das mit dem n+1 gilt es doch noch zu beweisen oder habe ich irgendwas falsch verstanden??

0
@fcb321

Schon richtig, aber die Behauptung für n+1 lautet:

(n+1)! <= 4 * ((n+1)/2)^(n+2) . Und dies folgt aus den ersten beiden Zeilen meiner Antwort
(n+1)! =(n+1) * n! <= 4 * (n/2)^(n+1) <= 4 * (( n+1)/2)^(n+2)

Und den letzteren Teil [*] dieser Ungleichung habe ich bewiesen. Der erste ist die Induktionsvoraussetzung.

0
@Rowal

Ok vielen Dank für deine Hilfe!!

0

Deine abgeleitete Ungleichung ist nicht ganz richtig, Du musst alle n durch n+1 ersetzen.

Ansatz für linke Seite als Hilfestellung:

(n+1)! = n! * (n+1)

Ja stimmt, aber deswegen hab ich ja auch dann die rechte Seite mit (n+1) multipliziert und kann annehmen das obige Gleichung richtig ist oder?

0
@fcb321

Du kannst annehmen, dass die Ungleichung für n richtig ist, musst aber beweisen, dass sie für (n+1) stimmt.

Mit dem Ansatz kannst Du (denke ich) die Ungleichung durch den Faktor (n+1) teilen, so dass Du aus der zu beweisenden Ungleichung die anzunehmende Ungleichung hergeleitet hast.

0

Was möchtest Du wissen?