Induktion , Binomialkoeffizient

26.10.2011, 23:37

Pfirsichtee

Induktion , Binomialkoeffizient

Nabend , ich versuche mich gerade an folgender Aufgabe :

Zeigen Sie : $\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} 2n \\ 2k \end{pmatrix} = 2^{2n-1} \end{eqnarray*}$

Also ich versuche das ganze per Induktion zu machen. Nun habe ich schon beim Induktionsanfang ein Problem :

n = 0

$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1 \end{eqnarray*}$

$\begin{eqnarray*} 2^{-1} = 0,5 \end{eqnarray*}$

Also stimmt hier ja schon der Induktionsanfang nicht verwirrt

Für n=1 stimmt die Aussage dann auch wieder. Kann es sein, dass die Summe erst bei 1 anfangen muss?
Ich habe dann trotzdem erstmal versucht mit Induktion weiterzumachen.

Sei die Aussage also für ein n aus N richtig. Nun muss ich ja zeigen :

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} 2n \\ 2k \end{pmatrix} = 2^{2(n+1)-1} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} 2n \\ 2k \end{pmatrix} + \begin{pmatrix} 2(n+1) \\ 2k \end{pmatrix} = 2^{2n+1} \end{eqnarray*}$

Nun die Induktionsvorraussetzung benutzen :

$\begin{eqnarray*} 2^{2n-1} + \begin{pmatrix} 2n+2 \\ 2k \end{pmatrix} = 2^{2n+1} \end{eqnarray*}$

An dieser Stelle komme ich nun nicht mehr weiter.

Bin dankbar für jede Anmerkung ^^

26.10.2011, 23:55

galoisseinbruder

Auf diesen Beitrag antworten »

Ja die Aussage gilt wohl nur für alle $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ .
Was Du im I.S. zeigen musst ist aber dann

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} 2n +2 \\ 2k \end{pmatrix} = 2^{2(n+1)-1} \end{eqnarray*}$

P.S. Binomialkoeffizienten lassen sich auch durch \binom{n}{k} darstellen.

26.10.2011, 23:59

René Gruber

Auf diesen Beitrag antworten »

Eine Alternativlösung (ohne Induktion) geht über den Binomischen Satz, angewandt auf $\begin{eqnarray*} (1+1)^{2n}+(1-1)^{2n} \end{eqnarray*}$ .

27.10.2011, 00:20

Pfirsichtee

Auf diesen Beitrag antworten »

Ok ich mache morgen weiter und werd dann schreibenwie weit ich gekommen bin. ^^

29.10.2011, 17:00

Pfirsichtee

Auf diesen Beitrag antworten »

Hallo , also da bin ich wieder, später als angekündigt sry. ^^

Ich muss zugeben, dass ich immer noch nicht weitergekommen bin. Ich habe es weiter mit Induktion versucht und mir auch den Tipp mit dem binomischen Lehrsatz angesehen, komme aber bei beiden Lösungsansätzen zu keinem befriedigenden Ergebnis.

Ich mache einfach nochmal beides vor, damit ihr seht, an welchen Stellen ich hänge ( leider schon sehr früh unglücklich

)

Mit Induktion

$\begin{eqnarray*} \sum\limits_{k=0}^n \begin{pmatrix} 2n \\ 2k \end{pmatrix} = 2^{2n-1} \end{eqnarray*}$

IA : n = 1 ==> 2 = 2

IS :

zu zeigen : $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} 2n + 2 \\ 2k \end{pmatrix} = 2^{2n+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} 2n + 2 \\ 2k \end{pmatrix} = \sum\limits_{k=0}^{n} \begin{pmatrix} 2n + 2 \\ 2k \end{pmatrix} + \begin{pmatrix} 2n + 4 \\ 2k \end{pmatrix} = 2^{2n - 1 } + \begin{pmatrix} 2n + 4 \\ 2k \end{pmatrix} \end{eqnarray*}$

Und nun soll ja $\begin{eqnarray*} 2^{2n - 1 } + \begin{pmatrix} 2n + 4 \\ 2k \end{pmatrix} = 2^{20+1} \end{eqnarray*}$

Dazu müsste doch aber $\begin{eqnarray*} \begin{pmatrix} 2n + 4 \\ 2k \end{pmatrix} = 2^2 \end{eqnarray*}$ gelten. Aber das stimmt doch deke ich nicht. Hier komme ich also nicht mehr weiter.

Ansatz mit binomischen Lehrsatz

Auch hier komme ich recht früh nicht weiter. Ich bin mir auch nicht sicher, ob das so, wie ich es aufschreibe, richtig ist.

$\begin{eqnarray*} (1+1)^{2n} + (1-1)^{2n]} = \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot 1^{2n-k} \cdot 1^k + \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot 1^{2n-k} \cdot (-1)^k = \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} + \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot (-1)^k = \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot ( 1 + (-1)^k ) \end{eqnarray*}$

Und auch hier komme ich nicht weiter. Habe ich den Satz überhaupt richtig angewendet?

Gruß Pfirsichtee ^^

29.10.2011, 17:14

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Pfirsichtee
$\begin{eqnarray*} (1+1)^{2n} + (1-1)^{2n]} = \ldots = \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot ( 1 + (-1)^k ) \end{eqnarray*}$

Und auch hier komme ich nicht weiter. Habe ich den Satz überhaupt richtig angewendet?

Ja, hast du.

Wie groß ist denn $\begin{eqnarray*} (1+(-1)^k) \end{eqnarray*}$

a) für gerade $\begin{eqnarray*} k \end{eqnarray*}$ , und

b) für ungerade $\begin{eqnarray*} k \end{eqnarray*}$ ? Augenzwinkern

29.10.2011, 17:21

Pfirsichtee

Auf diesen Beitrag antworten »

Ja also ich habe schon verstanden, dass praktisch jedes zweite Glied wegfällt, also für alle ungeraden k. Aber irgendwie hilft mir das Ganze noch nicht, um auf das gewollte $\begin{eqnarray*} 2^{2n+1} \end{eqnarray*}$ zu kommen. verwirrt

29.10.2011, 17:22

René Gruber

Auf diesen Beitrag antworten »

Nicht $\begin{eqnarray*} 2^{2n+1} \end{eqnarray*}$ , sondern $\begin{eqnarray*} 2^{2n-1} \end{eqnarray*}$ . Und die Antwort darauf liefert a) - bisher hast du dich ja nur zu b) geäußert. Augenzwinkern

29.10.2011, 17:24

Pfirsichtee

Auf diesen Beitrag antworten »

Achso , kann es sein, dass also für ungerade k die Summanden wegfallen und bei geraden k habe ich ja immer 2 mal blabla.

Und dieses blabla, ist das etwa wenn ich mich jetzt nicht vergucke $\begin{eqnarray*} 2^{2n} \end{eqnarray*}$ ? geschockt

Und dann halt mit dem mal 2 oben noch ne 1 dran

29.10.2011, 17:32

René Gruber

Auf diesen Beitrag antworten »

Eigentlich solltest du es jetzt ja haben, obwohl mich rätselhafte Bemerkungen wie

Zitat:

Original von Pfirsichtee
Und dann halt mit dem mal 2 oben noch ne 1 dran

schon etwas irritieren.

29.10.2011, 17:37

Pfirsichtee

Auf diesen Beitrag antworten »

Naja also ich meinte :

$\begin{eqnarray*} \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot (1 + (-1)^k ) = 2^{2n} \cdot 2 = 2^{2n+1} \end{eqnarray*}$

Hmmm ob das wohl so richtig aufgeschrieben ist? verwirrt

Also ich wqürde halt noch nen Sätzchen drunter schreiben, wie ich darauf komme, also ungerade k : Summand wird 0 etc...

29.10.2011, 17:40

René Gruber

Auf diesen Beitrag antworten »

So wird es gerade falsch - konzentriere dich bitte. unglücklich

29.10.2011, 17:52

Pfirsichtee

Auf diesen Beitrag antworten »

Hmm ok jetzt blick ich noch nicht so ganz durch. Also die Summe ausgeschrieben ergibt ja

$\begin{eqnarray*} \sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \cdot ( 1 + ( -1)^k ) = 2 \cdot \begin{pmatrix} 2n \\ 0 \end{pmatrix} + 2 \cdot \begin{pmatrix} 2n \\ 2 \end{pmatrix} + 2 \cdot \begin{pmatrix} 2n \\ 4 \end{pmatrix} + 2 \cdot \begin{pmatrix} 2n \\ 6 \end{pmatrix} + ... + 2 \cdot \begin{pmatrix} 2n \\ n \end{pmatrix} + ... + 2 \cdot \begin{pmatrix} 2n \\ 2n \end{pmatrix} \end{eqnarray*}$

Kann es sein, dass ich irgendwie die zwei, welche beim Summenzeichen oben steht, irgendwie verarbeiten kann/ muss?

29.10.2011, 17:56

René Gruber

Auf diesen Beitrag antworten »

Also den Summanden $\begin{eqnarray*} 2 \cdot \begin{pmatrix} 2n \\ n \end{pmatrix} \end{eqnarray*}$ solltest du weglassen, denn der gehört da nur rein, falls $\begin{eqnarray*} n \end{eqnarray*}$ gerade ist, sonst nicht.

Irgendwie hast du eine gewaltige Denkblockade bei dem nun eigentlich nur noch folgenden lächerlichen Schritt: Diese Summe muss ja nun gleich

$\begin{eqnarray*} (1+1)^{2n} + (1-1)^{2n} = 2^{2n} + 0^{2n} = 2^{2n} \end{eqnarray*}$

sein. Also letztendlich dann alles noch durch 2 dividieren, dann kommt man auch auf die gewünschten $\begin{eqnarray*} 2^{2n-1} \end{eqnarray*}$ . Traurig, dass du auf diesen letzten Schritt nicht selbst gekommen bist. unglücklich

29.10.2011, 18:01

Pfirsichtee

Auf diesen Beitrag antworten »

Ach Mensch böse