Binomialkoeffizienten

23.10.2006, 14:21

Kolibri

Auf diesen Beitrag antworten »

Binomialkoeffizienten

Hallo,
ich hab da eine neue Aufgabe in der Uni bekommen und versteh sie nicht so wirklich...

Die Binomialkoeffizienten sind durch folgende Formel definiert:
$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!} \end{eqnarray*}$

Sei $\begin{eqnarray*} f(n)=\begin{pmatrix} n \\ [\frac{n}{2}] \end{pmatrix} \end{eqnarray*}$
(Hinweis [-] bedeutet, die nächstkleinere ganze Zahl), also
$\begin{eqnarray*} f(n)= \begin{pmatrix} n \\ \frac{n}{2} \end{pmatrix} \end{eqnarray*}$ falls n gerade
$\begin{eqnarray*} f(n)= \begin{pmatrix} n \\ \frac{n-1}{2} \end{pmatrix} \end{eqnarray*}$ falls n ungerade

a) Berechne $\begin{eqnarray*} \frac{f(n+1)}{f(n)} \end{eqnarray*}$ für gerades und ungerades n.
b) Eine Funktion f wächst exponentiell, wenn eine konstante Zahl a > 1 existiert mit $\begin{eqnarray*} f(n)=\lambda(a^n) \end{eqnarray*}$ . Wächst unser f exponential?

Also nun zu meinen Ansätzen...

a)
gerades n:
$\begin{eqnarray*} f(n)=\frac{n!}{\frac{n}{2}!(n-\frac{n}{2})!} \end{eqnarray*}$

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

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

Und jetzt weiß ich nicht weiter... Darf ich Fakultäten kürzen? Wie soll denn das Ergebnis davon aussehen?

b)
Tja und da weiß ich leider auch nicht wirklich was zu... Vielleicht den Grenzwert bilden und gucken, ob die Funktion wächst... Aber das heißt dann ja auch nicht, dass sie exponentiell wächst....

Wäre für jede Antwort echt super dankbar.
Liebe Grüße.

23.10.2006, 14:57

Dual Space

Auf diesen Beitrag antworten »

RE: Binomialkoeffizienten
*verschoben* (Obwohl es vielleicht in der Stochastikvorlesung behandelt wird, gehört es thematisch zur Algebra.)

23.10.2006, 18:08

Kolibri

Auf diesen Beitrag antworten »

Oh, tut mir Leid. War keine Absicht.

23.10.2006, 20:13

Abakus

Auf diesen Beitrag antworten »

Setz doch mal $\begin{eqnarray*} n := 2k \end{eqnarray*}$ für gerade $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} n := 2k + 1 \end{eqnarray*}$ für ungerade $\begin{eqnarray*} n \end{eqnarray*}$ .

Natürlich kannst du Faktoren rauskürzen, ggf. musst du dabei die Fakultäten auflösen.

Grüße Abakus smile

smile

23.10.2006, 20:38

Kolibri

Auf diesen Beitrag antworten »

Mmh, irgendwie hilft mir der Tipp nicht wirklich weiter :-( Hab es einfach einsetzen wollen, aber ich weiß nicht, worauf du hinaus willst...

23.10.2006, 20:50

Abakus

Auf diesen Beitrag antworten »

Um a) zu berechnen, musst du geeignet kürzen - soweit es halt geht. Mit der Substitution rechnet es sich da ggf. einfacher.

Grüße Abakus smile

smile

Anzeige

24.10.2006, 17:11

Kolibri

Auf diesen Beitrag antworten »

Also, ich hab das jetzt mal probiert... Und statt n! hab ich einfach 2k für gerades n eingesetzt... Ist das richtig?

Dann wär das Ergebnis (ohne Rücksubstitution)

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

und

$\begin{eqnarray*} \frac{f(2k+1)}{f(2k)}= \frac{2k}{2k+1} \end{eqnarray*}$

Aber mir kommt das so komisch vor, dass ich statt der Fakultät einfach 2k einsetze...

24.10.2006, 17:20

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
Aber mir kommt das so komisch vor, dass ich statt der Fakultät einfach 2k einsetze...

Das hat Abakus ja auch gar nicht gesagt! Für $\begin{eqnarray*} n \end{eqnarray*}$ sollst du das einsetzen, also

$\begin{eqnarray*} n! = (2k)!, \qquad \left\lfloor \frac{n}{2} \right\rfloor ! = \left\lfloor k \right\rfloor ! = k! \end{eqnarray*}$

für gerade $\begin{eqnarray*} n \end{eqnarray*}$ , also $\begin{eqnarray*} n=2k \end{eqnarray*}$ , usw.

24.10.2006, 17:31

Kolibri

Auf diesen Beitrag antworten »

mmh, aber das macht die sache doch gar nicht einfacher oder? also ob da nun n steht oder 2k... :-( Ich weiß nicht, wie ich die Fakultäten kürzen kann.. Hab das halt noch nie gemacht...

24.10.2006, 17:35

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
mmh, aber das macht die sache doch gar nicht einfacher oder?

Einfacher nicht, aber verständlicher, weil du dem $\begin{eqnarray*} k \end{eqnarray*}$ direkt ansiehst, dass es eine natürliche Zahl ist - Werte wie $\begin{eqnarray*} \left( \frac{n}{2} \right)! \end{eqnarray*}$ u.ä. sind eben in dieser Hinsicht etwas unhandlich.

Zum Kürzen: Da hilft die rekursive Definition $\begin{eqnarray*} n! = n\cdot (n-1)! \end{eqnarray*}$ der Fakultät. Dann ist eben $\begin{eqnarray*} (2k)! = (2k)\cdot (2k-1)! \end{eqnarray*}$ usw., und dann kannst du kürzen.

24.10.2006, 17:42

Kolibri

Auf diesen Beitrag antworten »

So, okay, auf ein Neues :-D
Also, für gerades n hätte ich nun zu bieten :-D

(Wieder mal ohne Rücksubstitution)

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

und

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

So richtig?
Und nun?

Aber k!k! ist ungleich (2k)! oder ???

24.10.2006, 17:50

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
$\begin{eqnarray*} f(2k)=\frac{(2k)!}{k!k!} \end{eqnarray*}$

Richtig.

Zitat:

Original von Kolibri
$\begin{eqnarray*} f(2k+1)=\frac{(2k+1)!}{(k+1/2)!k!} \end{eqnarray*}$

Falsch: Für $\begin{eqnarray*} n=2k+1 \end{eqnarray*}$ ist

$\begin{eqnarray*} \left\lfloor \frac{n}{2} \right\rfloor = \left\lfloor \frac{2k+1}{2} \right\rfloor = \left\lfloor k+\frac{1}{2} \right\rfloor = k \end{eqnarray*}$ ,

und demnach

$\begin{eqnarray*} \binom{n}{\left\lfloor \frac{n}{2} \right\rfloor} = \binom{2k+1}{k} = \frac{(2k+1)!}{k!\cdot ((2k+1)-k)!} = \frac{(2k+1)!}{k!\cdot (k+1)!} \end{eqnarray*}$ .

Konzentrieren beim Einsetzen! Außerdem "sieht" man einem Wert wie $\begin{eqnarray*} k+\frac{1}{2} \end{eqnarray*}$ ja an, dass er nicht ganzzahlig ist, und somit ein Fakultätswert davon völliger Humbug ist (solange man die Gammafunktion nicht kennt... Augenzwinkern

Augenzwinkern

).

P.S.: Wie das mit dem Kürzen geht, habe ich oben schon geschrieben. (2k)! kann man jedenfalls nicht durch k!*k! ersetzen!!!

24.10.2006, 18:01

Kolibri

Auf diesen Beitrag antworten »

ähm muss ich nicht n=2k+1 für ungerade n einsetzen???

Also ich hab halt erstmal f(n) und dann f(n+1) berechnen wollen für gerade n...

24.10.2006, 18:06

Kolibri

Auf diesen Beitrag antworten »

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

und dann hab ich n = 2k da eingesetzt:

$\begin{eqnarray*} f(2k+1)=\frac{(2k+1)!}{(k+0,5)!(k+0,5)!} \end{eqnarray*}$

24.10.2006, 18:38

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
$\begin{eqnarray*} !(k+0,5)! \end{eqnarray*}$

Da kann man sich die Hand wundschreiben, es wird einfach ignoriert:

Zitat:

Original von Arthur Dent
Außerdem "sieht" man einem Wert wie $\begin{eqnarray*} k+\frac{1}{2} \end{eqnarray*}$ ja an, dass er nicht ganzzahlig ist, und somit ein Fakultätswert davon völliger Humbug ist

24.10.2006, 18:45

Kolibri

Auf diesen Beitrag antworten »

Ja, aber ich hab meine Rechnung tausendmal angeschaut und ich finde keinen Fehler... Ich weiß ja auch, dass 0,5 nicht ganzzahlig ist... aber ich versteh nicht, wieso du abrundest... Ich mein, in der Aufgabenstellung steht doch, dass f(n) = n über n/2 sein soll, für gerade n und naja wieso ist dann bei dir [k+1/2] = k

24.10.2006, 18:47

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
Ich mein, in der Aufgabenstellung steht doch, dass f(n) = n über n/2 sein soll, für gerade n und naja wieso ist dann bei dir [k+1/2] = k

Ja, und wenn $\begin{eqnarray*} n \end{eqnarray*}$ gerade ist, was ist dann $\begin{eqnarray*} n+1 \end{eqnarray*}$ ??? Auch gerade??? Wohl nicht!!!

Und wir sprechen ja hier über $\begin{eqnarray*} f(n+1) \end{eqnarray*}$

24.10.2006, 18:53

Kolibri

Auf diesen Beitrag antworten »

okay, ich glaub dir das einfach mal :-) Werd nicht gleich böse bitte. Hab das noch nie so gerechnet... :-(

Also ich hab jetzt
$\begin{eqnarray*} \frac{f(2k+1)}{f(2k)}= \frac{k!(2k+1)!}{(2k)!(k+1)!} \end{eqnarray*}$

Ist das jetzt die Lösung für gerade n? Also müsst ich quasi jetzt rücksubstituieren und dann war's das?

24.10.2006, 18:57

AD

Auf diesen Beitrag antworten »

Bis hierhin richtig, aber jetzt kannst du noch kürzen!

P.S.: "Glauben" sollst du nicht, sondern begreifen: Wenn n gerade ist, kannst du doch nicht für die Berechnung von $\begin{eqnarray*} f(n+1) \end{eqnarray*}$ mit dem dann ungeraden Argument $\begin{eqnarray*} n+1 \end{eqnarray*}$ die Formel für gerade Argumente nehmen! Doch, da werde ich böse, wenn das in der x-ten Wiederholung ignoriert wird - und genau deshalb bin ich kein Lehrer.

24.10.2006, 19:00

Kolibri

Auf diesen Beitrag antworten »

Wenn n! = n (n - 1) ! ist, ist dann (2n)! = 2n (2n - 1) !

24.10.2006, 19:10

AD

Auf diesen Beitrag antworten »

Richtig - aber was heißt das konkret für den Ausdruck $\begin{eqnarray*} \frac{k!(2k+1)!}{(2k)!(k+1)!} \end{eqnarray*}$ ? Da wendest du das zweimal an:

$\begin{eqnarray*} (2k+1)! = (2k+1)\cdot (2k)! \end{eqnarray*}$ und $\begin{eqnarray*} (k+1)! = (k+1)\cdot k! \end{eqnarray*}$

P.S.: Verschoben in Schul-Algebra

24.10.2006, 19:13

Kolibri

Auf diesen Beitrag antworten »

Da kommt dann raus:
$\begin{eqnarray*} \frac{2k+1}{k+1} \end{eqnarray*}$ ?

24.10.2006, 19:17

AD

Auf diesen Beitrag antworten »

Richtig. Das war also $\begin{eqnarray*} \frac{f(n+1)}{f(n)} \end{eqnarray*}$ für gerade $\begin{eqnarray*} n \end{eqnarray*}$ , also $\begin{eqnarray*} n=2k \end{eqnarray*}$ .

Und jetzt das ganze so ähnlich für ungerade $\begin{eqnarray*} n \end{eqnarray*}$ , also $\begin{eqnarray*} n=2k+1 \end{eqnarray*}$ . In dem Fall ist dann aber $\begin{eqnarray*} n+1 \end{eqnarray*}$ gerade...

24.10.2006, 19:23

Kolibri

Auf diesen Beitrag antworten »

Okay, mach ich gleich mal und dann poste ich es rein :-) Danke schon mal :-)
Sag mal, muss ich nicht noch rücksubstituieren?
Was nehm ich denn dann? n=2k oder n=2k+1?

24.10.2006, 19:32

Kolibri

Auf diesen Beitrag antworten »

Also ungerades n:

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

mit n=2k

....

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

24.10.2006, 19:44

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
Also ungerades n:

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

mit n=2k - 1

....

= $\begin{eqnarray*} \frac{(2k-1)!}{(k-1)!(k-2)!} \end{eqnarray*}$

Nein - was rechnest du nur immer? Setz doch mal sorgfältig ein:

$\begin{eqnarray*} \binom{n}{\frac{n-1}{2}} = \binom{2k-1}{\frac{(2k-1)-1}{2}} = \binom{2k-1}{k-1} = \frac{(2k-1)!}{(k-1)!\cdot ((2k-1)-(k-1))!} = \frac{(2k-1)!}{(k-1)!\cdot k!} \end{eqnarray*}$ .

24.10.2006, 19:46

Kolibri

Auf diesen Beitrag antworten »

Habs eben schon verbessert.. Hoffe ich zumindest :-)

24.10.2006, 19:55

AD

Auf diesen Beitrag antworten »

Nein, jetzt hast du alles nur noch verschlimmert:

Du kannst doch nicht in einem Atemzug von "ungeraden n" und dann gleichzeitig "n=2k" sprechen - das beißt sich doch!

Also nochmal, da in deinem Kopf ein riesiges Durcheinander herrscht:

Es gilt, zwei Fälle zu betrachten:

(1) n gerade (haben wir oben getan)
(2) n ungerade (ist noch zu tun)

Und in jedem der Fälle ist der Quotient $\begin{eqnarray*} \frac{f(n+1)}{f(n)} \end{eqnarray*}$ zu betrachten. Im Fall (1) ist das ein Quotient mit ungeradem Funktionsargument im Zähler, und geradem Funktionsargument im Nenner. Im Fall (2) ist es genau umgekehrt: Gerades Funktionsargument im Zähler, und ungerades Funktionsargument im Nenner.

Warum nur wirfst du das immer wieder durcheinander, die Zahl $\begin{eqnarray*} n \end{eqnarray*}$ einerseits, und die zu betrachtenden Funktionsargumente andererseits? Einmal, zweimal OK - aber immer wieder?

24.10.2006, 19:58

Kolibri

Auf diesen Beitrag antworten »

Weil ich die substitution nicht verstehe... Ich find, dass das alles komplizierter macht... Und ich versteh nicht, wieso ich bei fall (1) einmal n = 2k definiere und dann auf einmal sage, dass n = 2k + 1 sein soll... und dann das einfach so stehen lassen darf`? Ohne Rücksubstitution?

24.10.2006, 20:18

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Kolibri
Und ich versteh nicht, wieso ich bei fall (1) einmal n = 2k definiere und dann auf einmal sage, dass n = 2k + 1 sein soll...

Nein, nein und nochmals nein, das hat nie jemand behauptet: Wenn n=2k ist, dann ist eben n+1=2k+1, und das ist ja wohl zweifelsohne richtig.

Was soll's, ich geb's auf.

24.10.2006, 20:19

Kolibri

Auf diesen Beitrag antworten »

ahhh :-) jetzt hab ichs verstanden :-)

25.10.2006, 01:46

Kolibri

Auf diesen Beitrag antworten »

Also bei ungeradem n hab ich raus:

$\begin{eqnarray*} \frac{f(2k)}{f(2k-1)} =\frac{k-1}{2k-1} \end{eqnarray*}$

und nach der Rücksubstitution:
$\begin{eqnarray*} \frac{f(n+1)}{f(n)} =\frac{1}{2}-\frac{1}{2n} \end{eqnarray*}$

und bei geradem n nach Rücksubstitution:
$\begin{eqnarray*} \frac{f(n+1)}{f(n)} =\frac{2n+2}{n+2} \end{eqnarray*}$

Ist das so richtig? :-)

25.10.2006, 07:47

AD

Auf diesen Beitrag antworten »

Es ist zum Haareausraufen - bei ungeraden $\begin{eqnarray*} n=2k-1 \end{eqnarray*}$ hast du dich schon wieder verrechnet. Richtig ist

$\begin{eqnarray*} \frac{f(n+1)}{f(n)} = \frac{f(2k)}{f(2k-1)} = \frac{(2k)!(k-1)!k!}{k!k!(2k-1)!} = \frac{[(2k)\cdot (2k-1)!](k-1)!k!}{[k\cdot (k-1)!]k!(2k-1)!} = \frac{(2k)}{k} = 2 \end{eqnarray*}$ .

Immerhin stimmt die Rücksubstitution bei geraden $\begin{eqnarray*} n \end{eqnarray*}$ .

25.10.2006, 13:08

Kolibri

Auf diesen Beitrag antworten »

Och Mensch, tut mir doch auch Leid :-( Aber wenn ich dabei keine Hilfe gebraucht hätte, dann hätte ich hier ja auch nichts reingeschrieben und ich versuch es ja wirklich auch :-( Der Fehler war bei der letztens Umformung... Naja... Auf jeden Fall schon mal DANKE :-)
Hab mich jetzt an Aufgabenteil b rangesetzt und mein Ansatz wäre da jetzt:

$\begin{eqnarray*} \lim_{n \to \infty} \frac{f(n)}{ a^{n} } \end{eqnarray*}$

Für gerades n:
$\begin{eqnarray*} \lim_{n \to \infty} \frac{n!}{(n/2)!(n/2)!a^{n}} = 0 \end{eqnarray*}$
mit a>1

Für ungerades n:
$\begin{eqnarray*} \lim_{n \to \infty} \frac{n!}{(n-1/2)!(n+1/2)!a^{n}} = 0 \end{eqnarray*}$
mit a>1

Also geht $\begin{eqnarray*} a^{n} \end{eqnarray*}$ schneller gegen unendlich als f(n).
Und die Aussage ist erfüllt. Reicht das als Beweis?

25.10.2006, 16:25

AD

Auf diesen Beitrag antworten »

Erneut Veto: Das gilt erst für a>2.

25.10.2006, 18:36

Kolibri

Auf diesen Beitrag antworten »

ach mensch, ich dachte, meine idee war so gut :-) aber mir fällt auch ehrlich gesagt nichts besseres ein :-(

26.10.2006, 10:05

Kolibri

Auf diesen Beitrag antworten »

Also für 1 < a < 2 müsste dann ja die Funktion erst steigen und dann auf Null fallen oder? Muss ich das denn überhaupt noch beweisen?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »