Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:06 Do 20.05.2010 | | Autor: | Adri_an |
| Aufgabe | Sei [mm] $\vektor{k \\ l}$ [/mm] der Binomialkoeffizient.
[mm] $\vektor{2^{n}-1 \\ l}$ [/mm] ist ungerade für alle [mm] $0\le l\le 2^{n}-1$. [/mm] |
Wie ist das zu verstehen?
Ist das eine Aussage über $n$ oder $l$?
Kann mir das jemand mit Begründung erklären?
Wenn es eine Aussage über $n$ ist, was ich stark vermute, ist dann mein Lösungsansatz richtig?
Mein Lösungsansatz:
Z.Z.: [mm] $\vektor{2^{n}-1 \\ l}=2n-1$.
[/mm]
Bew.:
Induktionsanfang:
Ann.: [mm] $n=1\Rightarrow\vektor{2^1-1 \\ 0}=\vektor{0 \\ 0}=1$ [/mm] ; $2*1-1$.
Induktionsschritt:
[mm] $\vektor{2^{n+1}-1 \\ l}=\produkt_{j=1}^{l}\bruch{(2^{n+1}-1)+j+1}{j}=\produkt_{j=1}^{l}\bruch{2^{n+1}+j}{j}$
[/mm]
|
|
| |
|
Der Induktionsanfang stimmt nicht. Für [mm]n=1[/mm] geht es um die Binomialkoeffizienten [mm]{1 \choose 0}[/mm] und [mm]{1 \choose 1}[/mm] und nicht um [mm]{0 \choose 0}[/mm]. Der letzte Binomialkoeffizient kommt bei [mm]n=0[/mm] vor. Immerhin sind alle drei Binomialkoeffizienten gleich 1, so daß die Behauptung für [mm]n=0[/mm] und [mm]n=1[/mm] stimmt. Auch [mm]n=2[/mm] könnte man sich noch überlegen:
[mm]{3 \choose 0} = 1 \, , \ {3 \choose 1} = 3 \, , \ {3 \choose 2} = 3 \, , \ {3 \choose 3} = 1[/mm]
Auch das paßt also: Alle vier sind ungerade.
Weiter stimmt deine Formel aus dem Induktionsschritt nicht. Es ist auch fraglich, ob eine Induktion hier sinnvoll ist. Besser ist es, den Binomialkoeffizienten direkt zu untersuchen. Wir können [mm]n \geq 3[/mm] annehmen. Für [mm]l=0[/mm] ist der Binomialkoeffizient 1, also ungerade, für [mm]l>0[/mm] gilt
[mm]{{2^n - 1} \choose l} = \prod_{j=1}^l \frac{2^n - j}{j}[/mm]
Und hier nimmt man sich den [mm]j[/mm]-ten Faktor vor: [mm]\frac{2^n - j }{j}[/mm], und schreibt [mm]j[/mm] als
[mm]j = 2^k \cdot u[/mm] mit ganzen Zahlen [mm]k,u \geq 0[/mm] und [mm]k
Dann gilt:
[mm]\frac{2^n - 2^k \cdot u}{2^k \cdot u} = \frac{2^{n-k} - u}{u}[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:28 Fr 21.05.2010 | | Autor: | Adri_an |
Danke, dass du mich auf meine Fehler aufmerksam gemacht hast und mir noch weitere gute Tipps gegeben hast. Ich hoffe, mit deinen Tipps weiterzukommen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:30 Fr 21.05.2010 | | Autor: | Adri_an |
Aah!
Ich resümiere:
Die Frage, die für den Fall [mm] $n\ge [/mm] 3$ und $0<l \ [mm] (\le 2^{n}-1)$ [/mm] zu stellen ist, ist:
Wann ist das Produkt [mm] $\produkt_{j=1}^{l}\bruch{2^{n}-j}{j}$ [/mm] ungerade?
Deine Antwort darauf war, nun mit meinen Gedanken dazu:
> Und hier nimmt man sich den [mm]j[/mm]-ten Faktor vor: [mm]\frac{2^n - j }{j}[/mm],
Du nimmst dir den $j.$-Faktor vor, weil du wahrscheinlich weißt, wenn ein Faktor gerade ist, dann ist das Produkt (aus natürlichen Zahlen) auch gerade. Korrekt? Wenn nicht, was hast du dir gedacht?
> und schreibt [mm]j[/mm] als
>
> [mm]j = 2^k \cdot u[/mm] mit ganzen Zahlen [mm]k,u \geq 0[/mm] und [mm]k
> [mm]u[/mm] ungerade
D.h., $j$ ist gerade. Hier sehe ich ein Problem, denn $j$ erfüllt [mm] $1\le j\le l\le 2^{n}-1$. [/mm] Mit anderen Worten $j$ kann auch ungerade sein. Wie erfasse ich die ungeraden $j$?
> Dann gilt:
>
> [mm]\frac{2^n - 2^k \cdot u}{2^k \cdot u} = \frac{2^{n-k} - u}{u}[/mm]
Okay, aber was sagt mir das? Kannst du mir einen Tipp geben, wie ich das Letzte verstehen soll?
|
|
|
| |
|
Jede positive ganze Zahl [mm]j[/mm] kann als Produkt einer Zweierpotenz und einer ungeraden Zahl dargestellt werden, z.B.
[mm]168 = 2^3 \cdot 21[/mm]
Man zieht einfach so viele Faktoren 2 heraus, bis etwas Ungerades übrigbleibt. Und da hast du den Exponenten [mm]k=0[/mm] vergessen, den ich in meiner Darstellung ausdrücklich zugelassen habe:
[mm]169 = 2^0 \cdot 169[/mm]
Und jetzt zurück:
[mm]\frac{2^n - j}{j} = \frac{2^{n-k} - u}{u}[/mm]
Was gilt nun bezüglich Geradheit und Ungeradheit bei Zähler und Nenner des Bruches?
|
|
|
|
