Wert einer Summe bestimmen < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich möchte den Wert der Summe [mm] \sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k} [/mm] selbst bestimmen, bzw. beweisen, dass der Wert der Summe [mm] 2^{n-1} [/mm] ist.
Da es ja immer von Vorteil ist das Ergebnis zu kennen, dachte ich mir, dass es ja mit Sicherheit einen weg über den binomischen Lehrsatz gibt das ganze zu zeigen, aber Pustekuchen, ich sehe es zumindest nicht.
Ich habe jetzt mehrere Versuche gestartet, wobei ich verwenden wollte, dass [mm] \sum_{k=0}^{n}\vektor{n \\ k}=2^{n} [/mm] ist:
[mm] \sum_{k=0}^{n}\vektor{n \\ k}=\sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k}+\sum_{k=0}^{n}\vektor{n \\ 2k+1}
[/mm]
um dann zu zeigen, dass diese beiden Summen den gleichen Wert besitzen, also jeweils [mm] 2^{n-1} [/mm] ergeben, was mich ja ans ziel gebracht hätte... Funktioniert aber nicht !
Gehe ich den komplett falschen Weg? Kann mir jemand einen Denkanstoß liefern ?
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:54 Di 25.01.2011 | | Autor: | abakus |
> Hallo,
>
> ich möchte den Wert der Summe
> [mm]\sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k}[/mm] selbst bestimmen,
> bzw. beweisen, dass der Wert der Summe [mm]2^{n-1}[/mm] ist.
>
> Da es ja immer von Vorteil ist das Ergebnis zu kennen,
> dachte ich mir, dass es ja mit Sicherheit einen weg über
> den binomischen Lehrsatz gibt das ganze zu zeigen, aber
> Pustekuchen, ich sehe es zumindest nicht.
> Ich habe jetzt mehrere Versuche gestartet, wobei ich
> verwenden wollte, dass [mm]\sum_{k=0}^{n}\vektor{n \\ k}=2^{n}[/mm]
> ist:
>
> [mm]\sum_{k=0}^{n}\vektor{n \\ k}=\sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k}+\sum_{k=0}^{n}\vektor{n \\ 2k+1}[/mm]
Hallo,
einmal addierst du bis k=n, einmal nur bis k=n/2 (ist aber sicher nur ein Tippfehler).
Dein geplantes Vorgehen funktioniert nur in den Zeilen des Pascalschen Dreiecks mit einer geraden Anzahl von eingetragenen Zahlen (also für ungerade n).
Da, wo es so direkt nicht funktioniert, könntest du ausnutzen, dass die Binomialkoeffizienten einer jeden Zeile die Summe der beiden darüber stehenden Koeffizienten sind (es also auf eine Zeile zurückführen, in der das Verfahren funktioniert).
Alternative: einen stinknormalen Induktionsbeweis führen.
Gruß Abakus
>
> um dann zu zeigen, dass diese beiden Summen den gleichen
> Wert besitzen, also jeweils [mm]2^{n-1}[/mm] ergeben, was mich ja
> ans ziel gebracht hätte... Funktioniert aber nicht !
>
> Gehe ich den komplett falschen Weg? Kann mir jemand einen
> Denkanstoß liefern ?
>
> Vielen Dank.
|
|
|
| |
|
Hallo,
danke für deine Antwort. Zu dem tippfehler, wenn ich von k=0 bis n summiere, dann bekomme ich doch zwangsläufig binomialkoeffizienten mit [mm] \vektor{n \\ 2n} [/mm] zum beispiel, was geschieht denn damit ? Das kann doch nicht funktionieren. Mir ist gerade schleierhaft, wie ich eine Induktion überhaupt anfangen sollte...
Wenn ich bis n summiere, dann lautet die Summe doch [mm] 2^{n-1}=\sum_{k=0}^{m}\vektor{2m \\ 2k}, [/mm] mit n/2=m, wolframalpha bestätigt das !
Soweit korrekt ?
Ist diese Aussage also wahr, haben wir als Induktionsvorraussetzung:
[mm] 2^{2m-1}=\sum_{k=0}^{m}\vektor{2m \\ 2k}
[/mm]
Wäre das eine Möglichkeit ?
Nun für n=1, haben wir dann
[mm] 2^{2-1}=1=\sum_{k=0}^{1}\vektor{2 \\ 2k}=\vektor{2 \\ 0}+\vektor{2 \\ 2}=2 [/mm]
das stimmt, aber wie geht es dann weiter?
Vielleicht erbarmt sich jemand...
Danke !
|
|
|
| |
|
Tach Kollege, 
Du denkst zu kompliziert...
Für 0<k<m ist ja [mm] \vektor{2m\\2k}=\vektor{2m-1\\2k-1}+\vektor{2m-1\\2k}
[/mm]
Also ist [mm] \summe_{k=0}^{m}\vektor{2m\\2k}=\vektor{2m\\0}+\vektor{2m\\2m}+\summe_{k=1}^{m-1}\vektor{2m\\2k}=1+1+\summe_{i=1}^{2m-2}\vektor{2m-1\\i}=2+\left(\summe_{i=0}^{2m-1}\vektor{2m-1\\i}\right)-2=2^{2m-1}
[/mm]
Das funktioniert im Prinzip genauso für die ungeraden...
Es gilt nämlich auch [mm] \summe_{k=0}^{m}\vektor{2m+1\\2k}=2^{2m}
[/mm]
Allgemeiner formuliert: [mm] \summe_{0\le 2k\le n}\vektor{n\\2k}=2^{n-1}
[/mm]
...oder auch mit Gaußklammer, wenn Du diese Summation nicht magst.
Es ist vielleicht schöner, Du zeigst es also nicht nur für gerade n, sondern gleich für alle. Das geht im Prinzip genauso wie oben.
Grüße
reverend
|
|
|
| |
|
Hallo nochmal,
> danke für deine Antwort, das bringt schon sehr viel Licht
> in mein Dunkel .
There's a light over at the Frankenstein place...
<k><m ist="" ja="">> > Das funktioniert im Prinzip genauso für die ungeraden...
>
> Wo steckt denn in deinen Umformungen die Annahme drin, dass
> m gerade ist ?
Äh, gar nicht. Das war ungeschickt formuliert. Du hattest vorhin doch erst einmal n=2m ersetzt. Ich wollte nur darauf hinweisen, dass das nicht nötig ist, weil die Behauptung eben auch für n=2m+1 gilt.
> > Es gilt nämlich auch
> > [mm]\summe_{k=0}^{m}\vektor{2m+1\\
2k}=2^{2m}[/mm]
>
> Ok.
>
> > Allgemeiner formuliert: [mm]\summe_{0\le 2k\le n}\vektor{n\\
2k}=2^{n-1}[/mm]
>
> Das folgt, wenn man es noch für den ungeraden fall gezeigt
> hat ?
Ja, das ist nur eine mögliche Form, es für beide Fälle zusammen aufzuschreiben. So Fallunterscheidungen sind ja immer blöd, wenn sie eigentlich gar nicht die Behauptung unterscheiden, sondern nur aus Notationsgründen nötig sind. Daher der Vorschlag, wie auch der folgende:
> > ...oder auch mit Gaußklammer, wenn Du diese Summation
> > nicht magst.
Grüße
rev
</m></k>
|
|
|
| |
|
Hallo (schon wieder),
> Hallo nochmal,
>
> > danke für deine Antwort, das bringt schon sehr viel Licht
> > in mein Dunkel .
>
> There's a light over at the Frankenstein place...
>
> <k><m ist="" ja="">> > Das funktioniert im Prinzip genauso
> für die ungeraden...
> >
> > Wo steckt denn in deinen Umformungen die Annahme drin, dass
> > m gerade ist ?
>
> Äh, gar nicht. Das war ungeschickt formuliert. Du hattest
> vorhin doch erst einmal n=2m ersetzt. Ich wollte nur darauf
> hinweisen, dass das nicht nötig ist, weil die Behauptung
> eben auch für n=2m+1 gilt.
>
> > > Es gilt nämlich auch
> > > [mm]\summe_{k=0}^{m}\vektor{2m+1\\
2k}=2^{2m}[/mm]
> >
> > Ok.
> >
> > > Allgemeiner formuliert: [mm]\summe_{0\le 2k\le n}\vektor{n\\
2k}=2^{n-1}[/mm]
>
> >
> > Das folgt, wenn man es noch für den ungeraden fall gezeigt
> > hat ?
>
> Ja, das ist nur eine mögliche Form, es für beide Fälle
> zusammen aufzuschreiben. So Fallunterscheidungen sind ja
> immer blöd, wenn sie eigentlich gar nicht die Behauptung
> unterscheiden, sondern nur aus Notationsgründen nötig
> sind. Daher der Vorschlag, wie auch der folgende:
>
> > > ...oder auch mit Gaußklammer, wenn Du diese Summation
> > > nicht magst.
Das mit der Gaußklammer kam mir vorher auch schon in den Sinn, dann würde die Summation bis [mm] \left\lfloor\frac{n}{2}\right\rfloor [/mm] sinn machen, oder ?
Um ganz ehrlich zu sein bin ich jetzt aber mit meiner Induktion noch nicht wirklich weiter gekommen, bzw. ich sehe den Ansatz noch nicht. Klar ist mir jetzt die Summation. Die Induktionsvorraussetzung ist auch klar:
[mm] 2^{n-1}=\sum_{k=0}^{n}\vektor{n \\ 2k}
[/mm]
für n=1 ist das ganze wahr, der induktionsanfang.
bloß, was ist nun der induktionsschritt ? entschuldige, wenn ich nochmals nachfrage, vielleicht sehe ich es einfach nicht in deiner antwort...
Liebe Grüße !
|
|
|
| |
|
Hi,
zu ungeraden n hat Marcel gerade den einfachsten Vorschlag gemacht. Übersichtlicher geht es nicht, denke ich.
<k><m ist="" ja="">> > > > ...oder auch mit Gaußklammer, wenn Du diese Summation
> > > > nicht magst.
>
> Das mit der Gaußklammer kam mir vorher auch schon in den
> Sinn, dann würde die Summation bis
> [mm]\left\lfloor\frac{n}{2}\right\rfloor[/mm] sinn machen, oder ?
Ja, genau.
> Um ganz ehrlich zu sein bin ich jetzt aber mit meiner
> Induktion noch nicht wirklich weiter gekommen, bzw. ich
> sehe den Ansatz noch nicht. Klar ist mir jetzt die
> Summation. Die Induktionsvorraussetzung ist auch klar:
>
> [mm]2^{n-1}=\sum_{k=0}^{n}\vektor{n \\
2k}[/mm]
Hier stimmt doch wieder die Obergrenze des Summationindexes nicht...
> für n=1 ist das ganze wahr, der induktionsanfang.
>
> bloß, was ist nun der induktionsschritt ? entschuldige,
> wenn ich nochmals nachfrage, vielleicht sehe ich es einfach
> nicht in deiner antwort...
Ich habe gar keine Induktion gemacht, sondern es für n=2m>0 direkt gezeigt.
Im Moment sehe ich keinen eleganten Weg, direkt eine vollständige Induktion zu machen, sondern nur, wie man es für gerade n und dann getrennt davon für ungerade n zeigt. Das ist nicht schön, geht aber immerhin (und entspricht Marcels Vorschlag [mm] n\to{n+2} [/mm] ja genau).
Ich lasse die Frage mal auf "halb", vielleicht hat ja jemand eine hübsche Induktionsidee.
Grüße
rev
</m></k>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Fr 28.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:09 Mi 26.01.2011 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> ich möchte den Wert der Summe
> [mm]\sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k}[/mm] selbst bestimmen,
> bzw. beweisen, dass der Wert der Summe [mm]2^{n-1}[/mm] ist.
>
> Da es ja immer von Vorteil ist das Ergebnis zu kennen,
> dachte ich mir, dass es ja mit Sicherheit einen weg über
> den binomischen Lehrsatz gibt das ganze zu zeigen, aber
> Pustekuchen, ich sehe es zumindest nicht.
> Ich habe jetzt mehrere Versuche gestartet, wobei ich
> verwenden wollte, dass [mm]\sum_{k=0}^{n}\vektor{n \\ k}=2^{n}[/mm]
> ist:
>
> [mm]\sum_{k=0}^{n}\vektor{n \\ k}=\sum_{k=0}^{\frac{n}{2}}\vektor{n \\ 2k}+\sum_{k=0}^{n}\vektor{n \\ 2k+1}[/mm]
>
> um dann zu zeigen, dass diese beiden Summen den gleichen
> Wert besitzen, also jeweils [mm]2^{n-1}[/mm] ergeben, was mich ja
> ans ziel gebracht hätte... Funktioniert aber nicht !
>
> Gehe ich den komplett falschen Weg? Kann mir jemand einen
> Denkanstoß liefern ?
>
> Vielen Dank.
neben allen anderen Vorschlägen, die hier gemacht wurden, und die ich mir nicht genau angeguckt habe, hoffe ich, dass meiner nun noch nicht erwähnt wurde:
Bedenke mal, dass die Binomialkoeffizienten symmetrisch sind, d.h. es gilt
$${n [mm] \choose [/mm] k}={n [mm] \choose [/mm] n-k}$$
für alle $0 [mm] \le [/mm] k [mm] \le n\,.$
[/mm]
Damit ergibt sich die Behauptung für ungerade [mm] $n\,$ [/mm] relativ schnell, wenn man zudem die sich aus der binomischen Formel ergebende
[mm] $$2^n=(1+1)^n=\sum_{k=0}^n [/mm] {n [mm] \choose [/mm] k}$$
Formel benutzt. (Beachte [mm] $1^k\,$ [/mm] und [mm] $1^{n-k}$ [/mm] sind beide stets [mm] $=1\,.$)
[/mm]
Ich schreib' Dir mal ein Beweisschema auf, speziell ist bei mir zwar [mm] $n=5\,,$ [/mm] aber das macht nichts:
[mm] \begin{matrix}
& \;{5 \choose 0} & + {5 \choose 2} & + {5 \choose 4}\\
&+{5 \choose 5} & + {5 \choose 3} & + {5 \choose 1}\,.
\end{matrix}
[/mm]
Bleibt noch der Fall der geraden [mm] $n\,$ [/mm] zu untersuchen. Da kann man aber vielleicht nun einfach eine Induktion mit Induktionsschritt $n [mm] \mapsto [/mm] n+2$ machen. (Induktionsstart mit [mm] $n=0\,.$)
[/mm]
(Dabei sollte man im Hinterkopf behalten, dass wir die Gleichheit für ungerade [mm] $n\,$ [/mm] ja wegen der Symmetrie der Binomialkoeffizienten aus obigem Schema ablesen können. Für ungerade [mm] $n\,$ [/mm] haben wir sie also bewiesen. (Du kannst es auch meinetwegen ein wenig formaler machen:
Für ungerade $n$ gilt:
[mm] $$2^n=\sum_{k=0}^n [/mm] {n [mm] \choose k}=\sum_{\substack{g=0\\g\text{ gerade }}}^{n} [/mm] {n [mm] \choose g}+\sum_{\substack{g=0\\g\text{ gerade }}}^{n} [/mm] {n [mm] \choose n-g}=\ldots\,,$$
[/mm]
wobei erwähnt sei, dass man jede Menge [mm] $\{0,\ldots,n\}$ [/mm] partitionieren kann durch "Aufspalten in den Anteil der geraden und den Anteil der ungeraden Zahlen"; und dass man die ungeraden Zahlen [mm] $\{1,\ldots,n\}$ ($n\,$ [/mm] war ja ungerade) auch ("rückwärts", d.h. im Sinne von "fallend") schreiben kann als [mm] $\{n-0,\;n-2,\;\ldots,\;n-(n-1)\}$ [/mm] (d.h. von [mm] $n\,$ [/mm] zieht man einfach (nach und nach) die geraden Zahlen aus [mm] $\{0,\ldots,n\}$ [/mm] ab).))
Gruß,
Marcel
|
|
|
|
