Induktion

28.10.2009, 12:38

Tarsuinn

Induktion

Hi, habe eine Frage zur voll. Induktion.

Aufgabe ist folgende:

Zeigen Sie mit der voll. Induktion die Gültigkeit der Ungleichung:

$\begin{eqnarray*} \begin{pmatrix} 2n \\ n \end{pmatrix} < 4^n \end{eqnarray*}$

So den Anfang hab ich alles, beim einsetzten der Induktionsannahme bin ich jetzt soweit:

$\begin{eqnarray*} 4^{n+1}=4^n*4 > \begin{pmatrix} 2n \\ n \end{pmatrix}*4 \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} 2n \\ n \end{pmatrix}*4 > \begin{pmatrix} 2(n+1) \\ (n+1) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \frac{8}{n!}>\frac{(2n+2)!}{(n+1)!(n+1)!} \end{eqnarray*}$

So ab jetzt komm ich da nicht mehr weiter, ist das bis hier überhaupt korrekt?

28.10.2009, 12:45

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion
Es ist $\begin{eqnarray*} \binom{2n}{n} \neq \frac{8}{n!} \end{eqnarray*}$ . Sieht man schon, wenn man n=1 einsetzt. smile

28.10.2009, 12:51

Tarsuinn

Auf diesen Beitrag antworten »

RE: Induktion

Zitat:

Original von klarsoweit
Es ist $\begin{eqnarray*} \binom{2n}{n} \neq \frac{8}{n!} \end{eqnarray*}$ . Sieht man schon, wenn man n=1 einsetzt. smile

Dann liegt da wohl mein Fehler und es müsste:

$\begin{eqnarray*} \left(\frac{4(2n)!}{n!*(2n-n)!} \right) \end{eqnarray*}$

sein.

28.10.2009, 12:58

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktion
Richtig. Freude

28.10.2009, 13:09

Tarsuinn

Auf diesen Beitrag antworten »

Hab jetzt die n! gekürzt, die Relation stimmt aber wie kann man noch besser zeigen?

$\begin{eqnarray*} 4(2n)!>\frac{(2n+2)!}{(n+1)(n+1)} \end{eqnarray*}$

Wollte die (2n+2)! aufspalten aber das führte zu nix verwirrt

Edit: ich denk ich habs:

$\begin{eqnarray*} \frac{(2n+2)!}{(2n)!} = 2(n+1)(2n+1) \end{eqnarray*}$

$\begin{eqnarray*} 4(n+1)(n+1)>2(n+1)(2n+1) \end{eqnarray*}$

4>2 OK

?

28.10.2009, 13:19

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Tarsuinn
4>2 OK

Ich weiß jetzt nicht, wie du darauf kommst, aber prinzipiell bist du auf dem richtigen Weg.

28.10.2009, 13:57

Tarsuinn

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

Zitat:

Original von Tarsuinn
4>2 OK

Ich weiß jetzt nicht, wie du darauf kommst, aber prinzipiell bist du auf dem richtigen Weg.

$\begin{eqnarray*} 4(n+1)(n+1)>2(n+1)(2n+2) \end{eqnarray*}$

$\begin{eqnarray*} 4(n+1)>2(2n+1) \end{eqnarray*}$

$\begin{eqnarray*} 4n+4>4n+2 \end{eqnarray*}$

$\begin{eqnarray*} 4>2 \end{eqnarray*}$

28.10.2009, 14:05

klarsoweit

Auf diesen Beitrag antworten »

OK. Da habe ich vorhin irgendwo geschielt. Also dann ist jetzt alles in Butter. Freude

28.10.2009, 14:17

Auf diesen Beitrag antworten »

Ergänzend lässt sich anmerken, dass man die Behauptung auch ganz gut ohne Induktion, dafür unter Benutzung des Binomischen Satzes beweisen kann:

$\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ ist nur einer der durchweg positiven Summanden der Summe $\begin{eqnarray*} \sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n} = 4^n \end{eqnarray*}$ . Augenzwinkern

28.10.2009, 14:50

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ergänzend lässt sich anmerken, dass man die Behauptung auch ganz gut ohne Induktion, dafür unter Benutzung des Binomischen Satzes beweisen kann:

$\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ ist nur einer der durchweg positiven Summanden der Summe $\begin{eqnarray*} \sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n} = 4^n \end{eqnarray*}$ . Augenzwinkern

Unter diesen Summanden sticht er allerdings gewaltiglich heraus, denn immerhin ist sein asymptotischer Anteil an der Summe nicht weniger als $\begin{eqnarray*} 1/\sqrt{\pi n} \end{eqnarray*}$ , wie man mit Hilfe der Stirlinglingschen Formel leicht sieht... Augenzwinkern

Neue Frage »

Antworten »

Induktion

Verwandte Themen