?Forster? Aufg. 1.3a (Induktion, Binomalkoeff.)

15.01.2010, 00:18

AndrewWiles

Auf diesen Beitrag antworten »

?Forster? Aufg. 1.3a (Induktion, Binomalkoeff.)

Hallo zusammen,
kaum hab ich 1.2 abgeschlossen und denke, schlimmer geht's nimmer, hänge ich schon wieder. Und zwar:

?soll gezeigt werden,

$\begin{eqnarray*} \binom{2^n-1}{l} \end{eqnarray*}$ ist ungerade für alle $\begin{eqnarray*} 0\leq l\leq 2^n-1 \end{eqnarray*}$

der Induktionsanfang (n=1) geht noch recht einfach, aber beim Schritt hakts. Das geht schon damit los, dass mir überhaupt nicht klar ist, was ich denn da konkret zeigen soll. Wenn ich mich recht entsinne, lautet die Bedingung für ne ungerade Zahl n, daß sie sich formulieren lässt als: $\begin{eqnarray*} n=2k+1 \quad \quad (k \in \mathbb{Z}) \end{eqnarray*}$ , ich weiß jetzt nicht, wo ich die Induktionsbehauptung "n+1" unterbringen soll.

Eines der wenigen Dinge die ich weiß ist, dass sich der Binomkoeff darstellen lässt als $\begin{eqnarray*} \binom{2^n-1}{l} = \prod_{j=1}^{l} \frac{(2^n-1)-j+1}{j} \end{eqnarray*}$ , und das wäre dann auch mein Ansatz.

Einer geraden Zahl könnte ich vielleicht beikommen, indem ich mir eines der Produkte herausgreife (vorzugsweise j=1) und argumentiere, dass ein Produkt gerade ist, wenn ein Faktor gerade ist, aber bei ungerade weiß ich nich weiter.

Könnte wer helfen?

15.01.2010, 11:36

pseudo-nym

Auf diesen Beitrag antworten »

Das der gegebene Ausdruck ungerade ist kann man formalisieren als

$\begin{eqnarray*} \forall 0\leq l\leq 2^n-1 \, \exists m \in \mathbb N : \binom{2^n-1}{l} = 2m+1 \end{eqnarray*}$
Das ist die Induktionsvorraussetzung. Die darfst du verwenden, um zu zeigen, dass gilt:
$\begin{eqnarray*} \forall 0\leq l\leq 2^n-1 \, \exists r \in \mathbb N : \binom{2^{n+1}-1}{l} = 2r+1 \end{eqnarray*}$

Falls du die Vandermondesche Identität benutzen darfst, tu es! Augenzwinkern

Augenzwinkern

15.01.2010, 12:33

AndrewWiles

Auf diesen Beitrag antworten »

Vandermondesche Identität nennt sich das Ding also; Ja, das war die Aufgabe davor (Du hast das Buch wohl auch), dann guck ich mal.

Ich bin nicht sonderlich gut mit der Quantorenschreibweise vertraut, aber ich glaube Deine Formulierung beschreibt, was ich mit "ein Produkt herausgreifen" meinte, richtig? Leider leuchtet mir immer noch nicht ein, wie hieraus Ungeradheit zu schließen ist verwirrt

verwirrt

Aber ich werd' sehen. Danke erstma.

Bin dran und meld mich wieder.

15.01.2010, 12:46

tmo

Auf diesen Beitrag antworten »

Musst du Induktion benutzen?

Wenn nicht, könnte man ausnutzen, dass j stets als $\begin{eqnarray*} 2^{h_j}m_j \end{eqnarray*}$ dargestellt werden kann, wobei $\begin{eqnarray*} m_j \end{eqnarray*}$ ungerade ist.

Wegen $\begin{eqnarray*} 2^{h_j} \leq 2^{h_j}m_j = j \leq l < 2^n \end{eqnarray*}$ ist $\begin{eqnarray*} h_j < n \end{eqnarray*}$ gesichert, also macht es Sinn das Produkt so umzuschreiben:

$\begin{eqnarray*} \prod_{j=1}^l \frac{2^n-j}{j} = \prod_{j=1}^l \frac{2^n-2^{h_j}m_j}{2^{h_j}m_j} = \prod_{j=1}^l \frac{2^{n-h_j}-m_j}{m_j} \end{eqnarray*}$

15.01.2010, 12:58

pseudo-nym

Auf diesen Beitrag antworten »

Zitat:

Original von AndrewWiles
Ich bin nicht sonderlich gut mit der Quantorenschreibweise vertraut, aber ich glaube Deine Formulierung beschreibt, was ich mit "ein Produkt herausgreifen" meinte, richtig? Leider leuchtet mir immer noch nicht ein, wie hieraus Ungeradheit zu schließen ist verwirrt

verwirrt

Was die erste Quantorenkette beschreibt ist salopp gesagt:
Man kann $\begin{eqnarray*} \binom{2^n-1}{l} \end{eqnarray*}$ in der Form $\begin{eqnarray*} 2m +1 \end{eqnarray*}$ darstellen.

Daraus könnte ich jetzt etwa schließen, dass $\begin{eqnarray*} (2n+3)\binom{2^n-1}{l} \end{eqnarray*}$ ungerade ist

$\begin{eqnarray*} (2n+3)\binom{2^n-1}{l}= (2n+3)(2m+1) = 4mn +6m + 2n + 3 = 2(2mn+3m+n)+3 \end{eqnarray*}$

Was für dich interessant sein könnte ist erstmal zu zeigen, dass wenn $\begin{eqnarray*} \binom{2^n-1}{l} \end{eqnarray*}$ ungerade ist, $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ gerade ist.

19.01.2010, 20:53

AndrewWiles

Auf diesen Beitrag antworten »

So, da bin ich wieder Wink

Wink

, hab mir ein bisschen Zeit gelassen. sorry, falls ich jemanden hab warten lassen.

Hab mittlerweile pseudo-nym's Rat befolgt, und mich der Geradheit von $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ angenommen, allerdings nur für sich genommen und nicht in Abhängigkeit von $\begin{eqnarray*} \binom{2^n-1}{l} \end{eqnarray*}$ , das wäre nämlich sowieso Teil 2 dieser Aufgabe.

Das sieht jetzt jedenfalls so aus:

Beweis: $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ is gerade für $\begin{eqnarray*} 1\leq l\leq 2^n-1 \end{eqnarray*}$ .

A(1): $\begin{eqnarray*} \binom{2}{l}=2 \end{eqnarray*}$ , da $\begin{eqnarray*} l \end{eqnarray*}$ ja hier nur 1 sein kann.

A(n)=>A(n+1):
$\begin{eqnarray*} \binom{2^{n+1}}{l}=\binom{2^n+2^n}{l}=\sum_{j=0}^{l}\binom{2^n}{l-j}\binom{2^n}{j}=\underbrace{\sum^{j=1}_{l-1}\binom{2^n}{l-j}\binom{2^n}{j}}_{gerade nach IV}+\underbrace{\binom{2^n}{l}\binom{2^n}{0}+\binom{2^n}{0}\binom{2^n}{l}}_{=\binom{2^n}{0}\cdot 2\cdot \binom{2^n}{l}} \end{eqnarray*}$

Hmm, bin ich da schon fertig?

falls ja, weiß ich leider immer noch nicht wie ich dieses Ergebnis auf die Ungeradheit der ursprünglichen Aufgabe anwenden soll.

@tmo: Neiin, muß nich unbedingt Induk. nutzen, aber das war der Schwerpunkt des vorangegangenen Kapitels, also...?!
prinzipiell ist mir natürlich jedes Mittel recht, aber:

Zitat:

Wenn nicht, könnte man ausnutzen, dass j stets als dargestellt werden kann, wobei ungerade ist.

Das verstehe ich schon wieder nicht. warum lässt sich $\begin{eqnarray*} j \end{eqnarray*}$ immer so darstellen, und wie komme ich darauf, dass $\begin{eqnarray*} m_j \end{eqnarray*}$ ungerade ist?
Außerdem erschließt sich mir der Gewinn hierdurch nicht; ich kann immer noch keine Ungeradheit erkennen. Erstaunt2

Erstaunt2

Anzeige

19.01.2010, 22:41

tmo

Auf diesen Beitrag antworten »

Jede natürlich Zahl besteht aus Primfaktoren. Und jeder Primfaktor ist entweder 2 oder ungerade.

D.h. wenn wir aus einer natürlichen Zahlen die 2er-Potenz "extrahieren", bleibt eine ungerade Zahl übrig.

Z.b.

$\begin{eqnarray*} 60 = 2^2 \cdot 3 \cdot 5 = 2^2 \cdot 15 \end{eqnarray*}$ .

Dass das so umgeschriebene Produkt ungerade ist, sollte eigentlich nicht mehr schwer zu sehen sein. Guck dir doch einfach nur die Zähler an. Die sind immer... ?

19.01.2010, 22:53

pseudo-nym

Auf diesen Beitrag antworten »

Zitat:

Original von AndrewWiles
$\begin{eqnarray*} \underbrace{\sum^{j=1}_{l-1}\binom{2^n}{l-j}\binom{2^n}{j}}_{gerade nach IV} \end{eqnarray*}$

Hier musst du Acht geben. Die Induktionsvorraussetzung lautet nicht: " $\begin{eqnarray*} \sum_{j=1}^{l-1}\binom{2^n}{l-j}\binom{2^n}{j} \end{eqnarray*}$ ist gerade."
Aussagen über Summen eignen sich sehr gut für Induktionsbeweise. Das heißt nicht, dass man auf jede Summe in einem Induktionsbeweis die Induktionsvorraussetzung anwenden kann.

Zitat:

Original von AndrewWiles
$\begin{eqnarray*} \binom{2^{n+1}}{l}=\binom{2^n+2^n}{l}=\sum_{j=0}^{l}\binom{2^n}{l-j}\binom{2^n}{j} \end{eqnarray*}$

Bis hierher stimmt's und hier musst du auch deine IV " $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ is gerade für $\begin{eqnarray*} 1\leq l\leq 2^n-1 \end{eqnarray*}$ ." anwenden. (Achtung! kann größer als $\begin{eqnarray*} 2^n \end{eqnarray*}$ werden.)

19.01.2010, 23:22

AndrewWiles

Auf diesen Beitrag antworten »

@tmo:

Ahh, ok, das mit der Primzerlegung leuchtet ein, dennoch: einige der $\begin{eqnarray*} j \end{eqnarray*}$ sind ungerade, womit $\begin{eqnarray*} h_j \end{eqnarray*}$ =0 wird, und da die einzelnen Faktoren oft auch noch das ungerade $\begin{eqnarray*} m_j \end{eqnarray*}$ in der Form $\begin{eqnarray*} 2^{n-h_j}-m_j \end{eqnarray*}$ enthalten, trau ich mich nicht recht Aussagen über (Un-)Geradheit zu machen.

19.01.2010, 23:26

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von AndrewWiles
einige der $\begin{eqnarray*} j \end{eqnarray*}$ sind ungerade, womit $\begin{eqnarray*} h_j \end{eqnarray*}$ =0 wird

Und warum stört dich das?

19.01.2010, 23:46

AndrewWiles

Auf diesen Beitrag antworten »

Weil ich gerade dachte: so könnte ich dann keine Geradheitsaussage über $\begin{eqnarray*} 2^{h_j}m_j \end{eqnarray*}$ machen, aber ich seh grad, dass ich das ja auch net soll, sondern über $\begin{eqnarray*} 2^{n-h_j}-m_j \end{eqnarray*}$ , was natürlich trotz $\begin{eqnarray*} 2^{n-0} \end{eqnarray*}$ geht. (mein Fehler)

Jetzt leuchtet mir ein, warum $\begin{eqnarray*} \prod_{j=1}^l \frac{2^{n-h_j}-m_j}{m_j} \end{eqnarray*}$ ungerade ist.

Reicht es denn, das so hinzuschreiben? Schöner wäre natürlich eine etwas explizitere Aussage der Form 2k+1.

Und warum ist $\begin{eqnarray*} h_j<n \end{eqnarray*}$ wichtig?

19.01.2010, 23:58

AndrewWiles

Auf diesen Beitrag antworten »

@ pseudo-nym: Aber ich darf doch jetzt benutzen, dass $\begin{eqnarray*} \binom{2^n}{j} \end{eqnarray*}$ gerade ist. Und damit dürfte dann die ganze Summe ebenfalls gerade sein. und $\begin{eqnarray*} j \end{eqnarray*}$ läuft doch nur bis $\begin{eqnarray*} l<2^n \end{eqnarray*}$ .

20.01.2010, 00:04

AndrewWiles

Auf diesen Beitrag antworten »

@tmo: vergiss die $\begin{eqnarray*} h_j<n \end{eqnarray*}$ -Frage. Hammer

Hammer

20.01.2010, 00:25

pseudo-nym

Auf diesen Beitrag antworten »

l ist vom Exponenten des betrachteten Binomialkoeffizienten abhängig.
Betrachtest du $\begin{eqnarray*} \binom{2^{n+1}}{l} \end{eqnarray*}$ so ist $\begin{eqnarray*} 1\leq l\leq 2^{n+1}-1 \end{eqnarray*}$ und für $\begin{eqnarray*} l > 2^n \end{eqnarray*}$ ist $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ a priori nicht gerade.

20.01.2010, 01:18

AndrewWiles

Auf diesen Beitrag antworten »

äähm, dann brauch ich noch ne Fallunterscheidung für $\begin{eqnarray*} 2^n \leq l \leq 2^{n+1} \end{eqnarray*}$ ?

Oder meinst Du jetzt was anderes als ich?

ich erachte das als unkritisch, denn für $\begin{eqnarray*} l>2^n \end{eqnarray*}$ wird $\begin{eqnarray*} \binom{2^n}{l} \end{eqnarray*}$ doch eh 0, oder?

20.01.2010, 01:29

pseudo-nym

Auf diesen Beitrag antworten »

Richtig, für große l der Binnomialkoeffizient null. Die Fallunterscheidung kann man sich sparen man sollte sich der Tatsache nur bewusst sein.

20.01.2010, 07:25

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von AndrewWiles
Jetzt leuchtet mir ein, warum $\begin{eqnarray*} \prod_{j=1}^l \frac{2^{n-h_j}-m_j}{m_j} \end{eqnarray*}$ ungerade ist.

Reicht es denn, das so hinzuschreiben? Schöner wäre natürlich eine etwas explizitere Aussage der Form 2k+1.

Oder sowas hier:

Angenommen das Produkt ist gerade.
Dann gilt $\begin{eqnarray*} 2a = \frac{\prod_{j=1}^l 2^{n-h_j}-m_j}{\prod_{j=1}^l m_j} \end{eqnarray*}$ oder auch $\begin{eqnarray*} 2a \prod_{j=1}^l m_j= \prod_{j=1}^l 2^{n-h_j}-m_j \end{eqnarray*}$ , woraus folgt, dass 2 das rechte Produkt teilt. Wenn eine Primzahl ein Produkt teilt, teilt es aber mindestens einen Faktor, also gibt es ein $\begin{eqnarray*} 1 \leq i \leq l \end{eqnarray*}$ mit $\begin{eqnarray*} 2 | 2^{n-h_i}-m_i \Longleftrightarrow 2 | m_i \end{eqnarray*}$ .

21.01.2010, 13:59

AndrewWiles

Auf diesen Beitrag antworten »

Gekauft!

Freude

Dank euch.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »