Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis n! <= (n/2)^n durch vollständige Induktion

Beweis n! <= (n/2)^n durch vollständige Induktion

Universität / Fachhochschule

Tags: Vollständig Induktion

Dennis113 aktiv_icon

22:01 Uhr, 01.11.2022

Hallo, ich hänge beim Induktionsschritt des Beweises für

n! \leq {(\frac{n}{2})}^{n}

durch vollständige Induktion.
Mein Ansatz wäre

(n + 1)! = n! \cdot (n + 1) \leq

(nach Induktionsvoraussetzung)

(n + 1) \cdot {(\frac{n}{2})}^{n} = {(\frac{n + 1}{2 \cdot (1 + \frac{1}{n})})}^{n} \cdot (n + 1) = {(\frac{n + 1}{2})}^{n} \cdot (n + 1) \cdot {(\frac{1}{1 + \frac{1}{n}})}^{n} =

{(\frac{n + 1}{2})}^{n} \cdot (n + 1) \cdot \frac{1}{2} \cdot 2 \cdot {(\frac{1}{1 + \frac{1}{n}})}^{n} = {(\frac{n + 1}{2})}^{n + 1} \cdot 2 \cdot {(\frac{1}{1 + \frac{1}{n}})}^{n} \leq

{(\frac{n + 1}{2})}^{n + 1} \cdot 2

(da

{(\frac{1}{1 + \frac{1}{n}})}^{n} <

1(entsprechende Ungleichung möchte ich hier nicht explizit aufführen))
Und an der Stelle hänge ich fest. Der Term, den ich habe ist

{(\frac{n + 1}{2})}^{n + 1} \cdot 2,

obwohl ich nur

{(\frac{n + 1}{2})}^{n + 1}

bräuchte. Die 2 kann ich nicht einfach weglassen, wie den Faktor

{(\frac{n + 1}{2})}^{n + 1},

da diese nicht

< 1

ist und somit das Entfernen dieser nicht

\leq

wäre.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

michaL aktiv_icon

22:18 Uhr, 01.11.2022

Hallo,

du brauchst doch nur

(n + 1) \frac{n^{n}}{2^{n}} \leq \frac{(n + 1)^{n}}{2^{n + 1}} \overset{}{\Leftrightarrow} 2 \leq \frac{(n + 1)^{n}}{n^{n}} = {(1 + \frac{1}{n})}^{n}

.

Dass die Folge

{({(1 + \frac{1}{n})}^{n})}_{n \in ℕ^{*}}

monoton steigend ist, kann evtl. in der Vorlesung behandelt worden sein.

Wenn ja, dann ist wegen

2 = {(1 + \frac{1}{1})}^{1}

die Ungleichung

2 \leq ({(1 + \frac{1}{n})}^{n})

deswegen gültig, womit sich der Induktionsschritt meistern lässt.

Mfg Michael

Dennis113 aktiv_icon

22:37 Uhr, 01.11.2022

Hey,

könntest du bitte deine Äquivalenz erklären? Verstehe nämlich nicht ganz, wie du gerade auf den rechten Teil dieser Äquivalenz kommst. Ist das der Induktionsschritt von ganz Anfang an, oder ab da, wo ich nicht mehr weiterkomme? Denn falls Zweites wahr ist, müsste ich beweisen, dass die Folge

\frac{1}{{(1 + \frac{1}{n})}^{n}}

stetig ist und nicht

{(1 + \frac{1}{n})}^{n}

.
Übrigens: wir haben solche Stetigkeitsbeweise noch nicht in den Vorlesungen behandelt.

MfG

michaL aktiv_icon

08:07 Uhr, 02.11.2022

Hallo,

(n + 1)! = (n + 1) \cdot n! \overset{I.Behauptung}{\leq} (n + 1) {(\frac{n}{2})}^{n} = (n + 1) \frac{n^{n}}{2^{n}} \overset{das ist zu zeigen}{\leq} {(\frac{n + 1}{2})}^{n + 1} = \frac{(n + 1)^{n + 1}}{2^{n + 1}}

Wir wollen uns um die letzte Ungleichung kümmern und wählen dafür rechts die Version ohne Klammern. (Wie die nach Potenzgesetzen zustande kommt, sollte klar sein, oder?)

Es geht also um

(n + 1) \frac{n^{n}}{2^{n}} \leq \frac{(n + 1)^{n + 1}}{2^{n + 1}} \overset{erstmal kürzen}{\overset{}{\Leftrightarrow}} \frac{n^{n}}{2^{n}} \leq \frac{(n + 1)^{n}}{2^{n + 1}} \overset{n und 2en trennen}{\overset{}{\Leftrightarrow}} \frac{2^{n + 1}}{2^{n}} = 2 \leq \frac{(n + 1)^{n}}{n^{n}} = {(1 + \frac{1}{n})}^{n}

Klar soweit?

Mfg Michael

PS: Es geht nicht um Stetigkeit, sondern um Monotonie. Wenn ihr das noch nicht hattet speziell bei dieser Folge, dann ist das hier ein wenig nutzlos.
Es gibt aber Beweise dieser Art im Netz, die letztlich darauf führen, dass

{({(1 + \frac{1}{n})}^{n})}_{n \in ℕ^{*}}

konvergieren. Auf diese Weise wird die eulersche Zahl e als dieser Grenzwert definiert.

Mfg Michael

Dennis113 aktiv_icon

08:52 Uhr, 02.11.2022

Hallo,

Danke für deine Erklärung, ich verstehe nun deine Rechenschritte. Jedoch hast du mit dem zu zeigenden Term gerechnet (also praktisch die rechte Seite der Ungleichung). Uns wurde erzählt, wir sollen nur durch Umformung auf diesen rechten Teil kommen und dürfen nicht direkt damit rechnen (also mit dem

{(\frac{n + 1}{2})}^{n})

. Ich nehme an, hier geht das nur, weil es eine Ungleichung ist?

MfG

michaL aktiv_icon

09:14 Uhr, 02.11.2022

Hallo,

nein, das ginge auch mit einer Gleichung.

Beispiel: Zeige, dass

\sum_{k = 0}^{n} k = \frac{n (n + 1)}{2}

für alle

n \in ℕ

(Gaußsche Summenformel, ein Klassiker für Induktionsbeweise)

Anfang und Behauptung spare ich mir mal und schreite direkt zum Schritt:

\sum_{k = 0}^{n + 1} k = (\sum_{k = 0}^{n} k) + (n + 1) \overset{Ibehauptung}{=} \frac{n (n + 1)}{2} + (n + 1) \overset{zu beweisen}{=} \frac{(n + 1) (n + 2)}{2}

Ich schaue nun, ob die letzte Gleichung wahr ist (also durch alle

n \in ℕ

erfüllt):

\frac{n (n + 1)}{2} + (n + 1) = \frac{(n + 1) (n + 2)}{2} ∣ \cdot 2

n (n + 1) + 2 (n + 1) = (n + 1) (n + 2) ∣ \div (n + 1)

n + 2 = n + 2

offenbar stets eine wahre Aussage

Damit meine ich, die Gültigkeit gezeigt zu haben.
1. Ja, es geht auch anders, direkter, also ohne diesen merkwürdig anmutenden Umweg.
2. Beim Teilen durch

n + 1

muss man sich Gedanken machen, dass man nicht durch Null teilt. Da aber

n \in ℕ \overset{}{\Leftrightarrow} n \geq 0 \overset{}{\Leftrightarrow} n + 1 \geq 1 > 0

gilt, kann da nichts schiefgehen.

Es geht ja nur darum, von einem Term zum anderen zu kommen.
Natürlich könnte ich vom Term

\frac{n (n + 1)}{2} + (n + 1)

durch Ausklammern von

n + 1

direkt um Term

\frac{(n + 1) (n + 2)}{2}

gelangen.
Wenn ich das aber aus irgendwelchen Gründen nicht "sehe", ist doch an diesem Wege nichts falsch.
Alternativ hätte ich doch sowohl links als auch recht alles ausmultiplizieren können, damit ich erkennen kann, dass die Terme schon äquivalent sind.
Nein, ich darf diesen Weg schon gehen.
Was ich nicht darf, ist

\sum_{k = 0}^{n + 1} k = \frac{(n + 1) (n + 2)}{2}

schon zu verwenden um dann diese Gleichung erst zu beweisen. Das wäre ein logischer Zirkel.

Alles klar?

Zum Thema: Habt ihr schon bewiesen, dass die Folge

{({(1 + \frac{1}{n})}^{n})}_{n \in ℕ^{*}}

monoton wachsen ist?

Wenn nicht, ist diese Unterhaltung nämlich relativ nutzlos.

Mfg Michael

HAL9000

16:33 Uhr, 02.11.2022

Anmerkung: Bei der Behauptung

n! \leq {(\frac{n}{2})}^{n}

sollte man dazu sagen, dass die erst für

n \geq 6

gilt.

P.S.: Bei der ganz ähnlichen Behauptung

n! \leq 2 {(\frac{n}{2})}^{n}

im Thread

www.onlinemathe.de/forum/vollstaendige-Induktion-n-2n2n

verläuft der Induktionsschritt exakt so wie hier der von michaL. Nur dass diese Behauptung für alle

n \geq 1

gilt, was in einem anderen Induktionsanfang resultiert.

Dennis113 aktiv_icon

18:14 Uhr, 02.11.2022

Hallo,

entschuldige die späte Antwort, ich verstehe deinen Weg jetzt. Wir haben übrigens nicht behandelt/bewiesen, dass die Folge

({(1 + 1 n)}^{n})

für n∈ℕ\

{

0} monoton wachsend ist.
Weißt du aus diesem Grund zufällig auch, wie der Beweis auf direktem Wege geht?

MfG

HAL9000

09:13 Uhr, 03.11.2022

Für den Beweis von

{(1 + \frac{1}{n})}^{n} \geq 2

gibt es einfachere Alternativen, als die Monotonie der Folge nachweisen zu müssen, hier seien gleich zwei genannt:

1) (Wieder) Bernoulli-Ungleichung

{(1 + x)}^{n} \geq 1 + n x

, schlicht auf

x = \frac{1}{n}

angewandt.

2) Den Binomischen Satz angewandt ergibt sich

{(1 + \frac{1}{n})}^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) {(\frac{1}{n})}^{k}

. Wirft man nun alle Glieder

k > 1

weg (die sämtlich positiv sind), dann ergibt sich die Abschätzung nach unten

{(1 + \frac{1}{n})}^{n} \geq 1 + (\begin{array}{c} n \\ 1 \end{array}) \frac{1}{n} = 1 + 1 = 2

1562324

1562265

	Status: nicht eingeloggt	Noch nicht registriert?