Binomialkoeffizient gerade/ung < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:39 So 31.10.2010 | | Autor: | Coup |
| Aufgabe | Zeigen Sie, dass für alle n [mm] \in [/mm] und für alle 0 < k < [mm] 2^n [/mm] der Binomialkoeffizient
[mm] \vektor{2^n - 1 \\ k} [/mm] ungerade und der Binomialkoeffizient [mm] \vektor{2^n \\ k}
[/mm]
gerade ist. |
Hallo liebes Forum !
Wie kann ich diese Aufgabe am besten lösen ?
Ich wollte mit dem Beweis für [mm] \vektor{2^n \\ k} [/mm] anfangen
Muss ich also für n hier z.b 2,4,6.. einsetzen ?
gruß
Flo
|
|
| |
|
Hallo Flo,
> Zeigen Sie, dass für alle n [mm]\in[/mm] und für alle 0 < k < [mm]2^n[/mm]
> der Binomialkoeffizient [mm]\vektor{2^n - 1 \\
k}[/mm] ungerade und der
> Binomialkoeffizient [mm]\vektor{2^n \\
k}[/mm] gerade ist.
> Hallo liebes Forum !
> Wie kann ich diese Aufgabe am besten lösen ?
> Ich wollte mit dem Beweis für [mm]\vektor{2^n \\
k}[/mm] anfangen
> Muss ich also für n hier z.b 2,4,6.. einsetzen ?
Nein, das wären ja nur gerade n. Ich nehme an, in der Voraussetzung stand "für alle $ [mm] n\in\IN [/mm] $"?
Am besten ist, Du setzt da gar nichts ein, sondern wendest die Definition der Binomialkoeffizienten an:
[mm] \vektor{2^n\\k}=\bruch{(2^n)!}{k!*(2^n-k)!}
[/mm]
Die Behauptung ist zu zeigen, indem Du herausfindest, wie oft der Faktor 2 im Zähler und wie oft er im Nenner steht. Im Zähler muss mindestens eine 2 mehr enthalten sein als im Nenner. Glücklicherweise bleibt die gesuchte Größenordnung ja im Zähler immer gleich, will heißen: von k unabhängig. Also brauchst Du nur noch den Exponenten der 2 im Nenner, abhängig von k, zu ermitteln.
Behandle also n als gegebenen Parameter und k als Variable.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:24 So 31.10.2010 | | Autor: | Coup |
Ausgeschrieben wäre dann
[mm] \bruch{2^n(2^n-1)...(2^n-k+1)}{k!} [/mm]
?
hilft mir das weiter ?
Hab noch große Probleme mit mit dem Gebiet anzufreunden.
Flo
|
|
|
| |
|
Hallo nochmal,
> Ausgeschrieben wäre dann
> [mm]\bruch{2^n(2^n-1)...(2^n-k+1)}{k!}[/mm]
> ?
Ja. Das ist vollkommen richtig.
> hilft mir das weiter ?
Hmm. Weiß ich nicht so recht. Es geht auch so, aber ich denke es ist einfacher, nicht zu kürzen.
> Hab noch große Probleme mit mit dem Gebiet anzufreunden.
Diese Aufgabe hat etwas Besonderes, das nicht so sehr am Bereich der Mathematik liegt. Das Problem ist zu ermitteln, welche Potenz von 2 in der Primfaktorzerlegung von k! auftaucht.
Dazu eine Überlegung: wenn ich die Fakultät ausschreibe, dann habe ich
[mm] \lfloor \bruch{k}{2} \rfloor [/mm] gerade Zahlen, wobei die lustigen Klammern natürlich die "unteren" Gaußklammern sind, also die größte natürliche Zahl, die kleiner oder gleich dem eingeschlossenen Term ist.
Nun gibt es den Faktor 2 aber noch öfter, selbst nachdem ich die bisher identifizierten schon ausgeklammert habe. Denn alle durch 4 teilbaren Zahlen sind ja auch nach der Kürzung noch gerade Zahlen. In diesen ist die 2 noch [mm] \lfloor \bruch{k}{4} \rfloor [/mm] mal enthalten.
So kann ich weiter verfahren, bis alle Zweien ausgeklammert sind und in dem (immer noch nicht berechneten) Produkt nur noch ungerade Zahlen stehen.
Die Zahl der ausgeklammerten Zweien ist nun [mm] \summe_{i=1}^{\infty}\lfloor \bruch{k}{2^i} \rfloor
[/mm]
Das sieht unpraktisch aus und ist es auch, wenn man eine leicht zu berechnende Formel braucht, um den genauen Wert zu bestimmen. Aber damit ist schon zu zeigen, warum im Zähler mindestens eine 2 mehr steht.
Es gilt nämlich [mm] \lfloor \bruch{a}{c} \rfloor +\lfloor \bruch{b}{c} \rfloor \le \lfloor \bruch{a+b}{c} \rfloor
[/mm]
Ab hier solltest Du weiter kommen. Es fehlen noch zwei Schritte.
Falls Du da gerade auf keine Idee kommst, probier doch mal aus, wie oft die 2 in 6!, 7!, 8! und wie oft in 14!, 15!, 16! vorkommt. Dann verstehst Du wahrscheinlich das Muster, das sich in der etwas komplizierteren Notation oben auch zeigt.
Grüße
reverend
|
|
|
|
