Vollständige Induktion mit Binomialkoeffizient

14.02.2011, 20:52

Das_Mathekänguruh

Auf diesen Beitrag antworten »

Vollständige Induktion mit Binomialkoeffizient

Hallo zusammen,

ich muss jetzt seit mehreren Tagen folgende Ungleichung für die Uni beweisen, aber ich hab nichtmal einen Ansatz dafür, wo ich anfangen soll beim Induktionsschritt.
Induktionsanfang und -Hypothese sind schon klar, aber danach hörts bei mir auf.
Hoff jemand kann mir helfen wär echt wahnsinnig nett, weil ich schon seit Tagen an der Aufgabe hock und nicht annähernd auf ein Ergebnis komme.

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

Vielen Dank schonmal smile

smile

14.02.2011, 21:02

tmo

Auf diesen Beitrag antworten »

Das geht ohne Induktion. Es ist nur eine Folgerung aus (vielleicht) bekannten Tatsachen:

Verwende $\begin{eqnarray*} \sum_{k=0}^{m}\binom{m}{k} = 2^m \end{eqnarray*}$ .

Überlege dir ferner, für welches k $\begin{eqnarray*} \binom{2n}{k} \end{eqnarray*}$ am größten wird.

14.02.2011, 21:03

HAL 9000

Auf diesen Beitrag antworten »

Alternative: Der Beweis über Vollständige Induktion, sogar das viel schärfere

$\begin{eqnarray*} \binom{2n}{n} \geq \frac{4^n}{2\sqrt{n}} \end{eqnarray*}$

klappt damit ohne nennenswerten Mehraufwand.

14.02.2011, 21:11

Das_Mathekänguruh

Auf diesen Beitrag antworten »

Ich versteh das trotzdem nicht verwirrt

verwirrt

Meint ihr damit, dass ich das (2n über n) als Summe umschreiben soll und dann die Summe mit n+1 beweisen soll, dass sie größer als 4^n/2n ist !?

Wir müssen es nämlich unbedingt mit vollständiger Induktion beweisen und sollen es nicht anders machen ...

14.02.2011, 21:18

HAL 9000

Auf diesen Beitrag antworten »

Überleg dir erstmal für den Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ , wie man von $\begin{eqnarray*} \binom{2(n+1)}{n+1} = \binom{2n+2}{n+1} \end{eqnarray*}$ das aus der Induktionsvoraussetzung bekannte $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ faktoriell abspalten kann! Das ist der entscheidende Schritt für diesen Induktionsschritt.

14.02.2011, 21:29

Das_Mathekänguruh

Auf diesen Beitrag antworten »

geht das vielleicht so!?

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

Anzeige

14.02.2011, 21:30

HAL 9000

Auf diesen Beitrag antworten »

Fast - aber denk nochmal über den Nenner nach.

14.02.2011, 21:42

Das_Mathekänguruh

Auf diesen Beitrag antworten »

was?? über den Nenner nachdenken?? Bei dem war ich mir als erstes sicher Big Laugh

Big Laugh

musst mir nochmal en denkanstoß geben, ich komm da echt (noch) nicht drauf ... traurig

traurig

14.02.2011, 21:55

Das_Mathekänguruh

Auf diesen Beitrag antworten »

also ich hab jetz meine Lösung nochmal überdacht,

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

ich find da echt keinen Fehler auch wenn ich Zahlen einsetz kommt immer das Richtige raus ... auch für große n verwirrt

verwirrt

14.02.2011, 21:59

Nimm 2

Auf diesen Beitrag antworten »

Wie bist du auf die Formel gekommen?

14.02.2011, 22:04

Das_Mathekänguruh

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$

heißt ja einfach dass man (2n) n-mal mit sich selber multipliziert und dann durch n-Fakultät teilt.

14.02.2011, 22:11

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Das_Mathekänguruh
$\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$

heißt ja einfach dass man (2n) n-mal mit sich selber multipliziert und dann durch n-Fakultät teilt.

Wie kommst du auf diese Formel?
Etwas ausführlichere Zwischenschritte sind hier durchaus hilfreich

14.02.2011, 22:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Das_Mathekänguruh
$\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ heißt ja einfach dass man (2n) n-mal mit sich selber multipliziert und dann durch n-Fakultät teilt.

Wie überaus schade, dass man "falsch" nicht steigern kann... geschockt

geschockt

Tatsächlich ist $\begin{eqnarray*} \binom{2n}{n} = \frac{(2n)!}{n!^2} \end{eqnarray*}$ und die darauf aufbauende und von mir oben gemeinte Rekursion ist

$\begin{eqnarray*} \binom{2n+2}{n+1} = \frac{(2n+2)(2n+1)}{(n+1)^2} \cdot \binom{2n}{n} = \frac{2(2n+1)}{n+1} \cdot \binom{2n}{n} \end{eqnarray*}$ .

P.S.: Bin für heute dann weg. Wink

Wink

14.02.2011, 22:12

Nimm 2

Auf diesen Beitrag antworten »

Du mußt dir die Definition des Binomialkoeffizienten anschauen und dann einsetzen

14.02.2011, 22:20

Das_Mathekänguruh

Auf diesen Beitrag antworten »

hä jetz werd ich ja in meinen grundfesten erschüttert geschockt

geschockt

beim lotto braucht man doch z.B. unter anderem auch den Bin-Koeff. $\begin{eqnarray*} \binom{49}{6} \end{eqnarray*}$ was wir als $\begin{eqnarray*} \frac{49*48*47*46*45*44}{6!} \end{eqnarray*}$ definiert haben

P.S. hab natürlich vergessen dass man immer 1 abziehen muss im Zähler, aber das is ja trotzdem was anderes als $\begin{eqnarray*} \binom{2n}{n} = \frac{(2n)!}{n!^2} \end{eqnarray*}$

14.02.2011, 22:23

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Das_Mathekänguruh
P.S. hab natürlich vergessen dass man immer 1 abziehen muss im Zähler, aber das is ja trotzdem was anderes als $\begin{eqnarray*} \binom{2n}{n} = \frac{(2n)!}{n!^2} \end{eqnarray*}$

Natürlich ist deine Variante was anderes, deswegen ist sie ja auch so falsch.

Welchen Teil von

Zitat:

Du mußt dir die Definition des Binomialkoeffizienten anschauen

hast du denn nicht verstanden?
Siehe auch Definitionen nachschlagen

14.02.2011, 22:32

Das_Mathekänguruh

Auf diesen Beitrag antworten »

ok jetz versteh ich wie man dadrauf kommt:

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

richtig oder?

un ich weiß jetz glaub auch wo mein fehler war: ich hab immer mit nPr in meinem GTR überprüft aber das geht jetzt mit nCr. Aber nen Unterschied zwischen den beiden kenn ich gar nich, deswegen dachte ich, dass ist egal in der Schule haben wir immer nPr genommen ...

naja aber wir schweifen ab Big Laugh

Big Laugh

wenn man das dann jetz so umschreiben kann, wie kann man es beweisen mit der Induktion was ja mein Ausgangsproblem war?

14.02.2011, 22:39

Nimm 2

Auf diesen Beitrag antworten »

Du fuchtelst mit mathematische Ausdrücken herum wie ein Physiker

14.02.2011, 22:43

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Das_Mathekänguruh
ok jetz versteh ich wie man dadrauf kommt:

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

richtig oder?

ja, richtig

Zitat:

Original von Das_Mathekänguruh
un ich weiß jetz glaub auch wo mein fehler war: ich hab immer mit nPr in meinem GTR überprüft aber das geht jetzt mit nCr. Aber nen Unterschied zwischen den beiden kenn ich gar nich, deswegen dachte ich, dass ist egal in der Schule haben wir immer nPr genommen ...

Nein, dein Fehler ist der, dass du, nachdem 3 Leute dir gesagt haben dass du die Definition nochmal nachschlagen sollst, diese gut gemeinten Ratschläge ignoriert hast, weiterhin auf deiner falschen Lösung bestanden hast, und dann auch noch verwundert darüber warst, dass deine falsche Lösung etwas ganz anderes ist als die richtige Lösung - das nun auf den Taschenrechner zu schieben ist ein schlechter Vorwand, wenn solch grundlegende Definitionen nicht sitzen, sollte man zumindest so viel Eigeninitiative zeigen und diese selbstständig nachschlagen...

Zitat:

Original von Das_Mathekänguruh
wenn man das dann jetz so umschreiben kann, wie kann man es beweisen mit der Induktion was ja mein Ausgangsproblem war?

Nun kannst du auf $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ deine Induktionsannahme anwenden und etwas umformen, vorrechnen werde ich dir das nicht, erst Recht nicht nach dieser Nummer mit dem Binomialkoeffizienten

14.02.2011, 22:51

Das_Mathekänguruh

Auf diesen Beitrag antworten »

ja hast recht hät ich eher mal nachschlagen sollen.
aber das mit dem nPr un nCr versteh ich immernoch nicht, weil wenn ich Zahlen einsetz in meine falsche Lösung stimmt es mit nPr ...
soll aber nich heißen dass ich eure Lösung nicht akzeptiert hab Big Laugh

Big Laugh

un wenn man eure Lösung nimmt kommt das richtige mit nCr raus ...

ok ich werds mal probieren, will auch gar nich dass mir das jemand vorrechnet, wenn man selber draufkommt lernt man eh am meisten Augenzwinkern

Augenzwinkern

Big Laugh

ich brauch halt meistens immer nur en denkanstoß, weil ich auf die meisten sachen nicht selber komme (noch nicht vlt)

aber vielen dank schonmal für alles smile

smile

14.02.2011, 22:59

Nimm 2

Auf diesen Beitrag antworten »

Weißst du wie´s weitergeht?

14.02.2011, 23:07

Das_Mathekänguruh

Auf diesen Beitrag antworten »

nein ich weiß es leider nicht
aber wie ihr merkt steh ich ja eh schon die ganze zeit auf dem schlauch Big Laugh

Big Laugh

$\begin{eqnarray*} \binom{2n}{n}*\frac{2*(2n+1)}{(n+1)} \end{eqnarray*}$
hab ich jetz aber ich kann das ja nich einfach mit

$\begin{eqnarray*} \frac{4^{n+1}}{2(n+1)} \end{eqnarray*}$
gleichsetzen oder?

14.02.2011, 23:16

Nimm 2

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \binom{2n}{n}*\frac{2*(2n+1)}{(n+1)}\geq \end{eqnarray*}$

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

Jetzt unten mit 4 erweitern

14.02.2011, 23:27

Das_Mathekänguruh

Auf diesen Beitrag antworten »

also jetzt hab ichs fast (sieht zumindest mal besser aus als die letzten tage)
linke seite bleibt unverändert un auf der rechten seite hab ich jetzt:

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

aber weiter komm ich wieder nicht ... unglücklich

unglücklich

14.02.2011, 23:31

Nimm 2

Auf diesen Beitrag antworten »

Die Zeit drängt etwas

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

Das ist der Beweis

Schönen Abend noch!

14.02.2011, 23:34

Das_Mathekänguruh

Auf diesen Beitrag antworten »

ok vielen dank an alle und besonderen dank an die lösung!!
werds mir nochmal anschauen, hoff dass ich dann irgendwann mal selber sowas lösen kann Big Laugh

Big Laugh

14.02.2011, 23:57

Das_Mathekänguruh

Auf diesen Beitrag antworten »

so jetzt bin ich auch auf die Lösung gekommen smile

smile

nur begreif ich jetzt nicht mehr warum

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

ein beweis sein soll verwirrt

verwirrt

weil eigentlich hatten wir das bis jetz zumindest immer so, dass nach der Induktion genau das gleiche überall stand wie davor nur statt n dann n+1
die linke seite ist klar das ist ja genau das wie vorher nur für n jetzt n+1
aber auf der rechten seite haben wir n+1 wie es sein sollte aber dann noch zusätzlich einen faktor!?

argumentiert man dann so, dass der limes von $\begin{eqnarray*} \frac{2n+1}{2n} \end{eqnarray*}$ gegen 1 geht was das neutrale element der multiplikation ist?
was dann wiederum bedeuten würden dass wir überall statt n nun n+1 stehen hätten und der Faktor nicht ins gewicht fällt??

15.02.2011, 01:56

Merlinius

Auf diesen Beitrag antworten »

Du wirst doch wohl noch schließen können, dass aus:

Zitat:

Original von Das_Mathekänguruh
$\begin{eqnarray*} \frac{2(2n+1)}{n+1} \cdot \binom{2n}{n}>\frac{4^{n+1}}{2(n+1)}*\frac{2n+1}{2n} \end{eqnarray*}$

folgt, dass

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

gilt, oder nicht?

15.02.2011, 10:58

Das_Mathekänguruh

Auf diesen Beitrag antworten »

ja das kann ich schon folgern, aber kann ich den term auf der rechten seite dann einfach weglassen??
ich hab noch nicht sooo die übung mit vollständiger induktion, wie sicher jeder schon gemerkt hat ...

oder ist das so, weil ich jetzt herausgefunden habe, dass die behauptung für eine größere rechte seite gilt un deswegen auch für eine kleinere gelten muss??

15.02.2011, 11:07

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Das_Mathekänguruh
oder ist das so, weil ich jetzt herausgefunden habe, dass die behauptung für eine größere rechte seite gilt un deswegen auch für eine kleinere gelten muss??

Ja, und genau die Behauptung war ja zu zeigen

15.02.2011, 11:16

Das_Mathekänguruh

Auf diesen Beitrag antworten »

wow ok endlich geschafft und verstanden Big Laugh

Big Laugh

vielen vielen dank an alle die geholfen haben smile

smile

15.02.2011, 11:39

Bowman

Auf diesen Beitrag antworten »

Jetzt das lösen

$\begin{eqnarray*} \binom{2n}{n} \geq \frac{4^n}{2\sqrt{n}} \end{eqnarray*}$

Das war das Beispiel von Supercomputer HAL

Dessen höhrere Funktionen habe ich abgeschaltet

15.02.2011, 18:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bowman
Dessen höhrere Funktionen habe ich abgeschaltet

Nur im Film, Dave, nur im Film. Big Laugh

Big Laugh

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »