Binomialkoeffizient < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:58 Mo 25.10.2010 | | Autor: | eLi |
| Aufgabe | Beweisen sie per vollständiger Induktion:
[mm] \summe_{j=0}^{n}\vektor{n \\ 2j}=2^{n-1}
[/mm]
[mm] n\in\IN [/mm] |
Hallo,
ich bräuchte einen Tipp für obige Aufgabe. Ich schreibe erstmal auf, wie weit ich gekommen bin.
Induktionsanfang:
Für n=1 ist [mm] \summe_{j=0}^{1}\vektor{1 \\ 2j}=1 [/mm] , ebenso wie [mm] 2^{1-1} [/mm] = 1 ist. Der IA ist also korrekt.
Induktionsvorraussetzung:
Es gilt für ein beliebiges aber festes [mm] n\in\IN
[/mm]
Induktionsschritt:
n [mm] \to [/mm] n+1
[mm] \summe_{j=0}^{n+1}\vektor{n+1 \\ 2j}=\summe_{j=0}^{n}\vektor{n+1 \\ 2j}+\vektor{n+1 \\ 2n+2} [/mm]
[mm] \vektor{n+1 \\ 2n+2} [/mm] ist per Definition = 0 fällt also weg.
[mm] \summe_{j=0}^{n}\vektor{n+1 \\ 2j}=\summe_{j=0}^{n}[\vektor{n \\ 2j}+\vektor{n \\ 2j-1}]=\summe_{j=0}^{n}\vektor{n \\ 2j}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}
[/mm]
Nach der Induktionsvorraussetzung ist [mm] \summe_{j=0}^{n}\vektor{n \\ 2j}=2^{n-1}.
[/mm]
[mm] \summe_{j=0}^{n}\vektor{n \\ 2j}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}=2^{n-1}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}
[/mm]
Um jetzt auf die verbliebende Summe die Vorrausetzung anwenden zu können, muss eine Indexverschiebung durchgeführt werden. Ich weiß allerdings nicht, wie das in diesem Fall funktionieren soll. Kann ich einfach sagen:
[mm] \summe_{j=0}^{n}\vektor{n \\ 2j-1}=\summe_{j=-1}^{n-1}\vektor{n \\ 2j}?
[/mm]
Wäre für jegliche Hilfe dankbar.
Grüße,
eLi
|
|
| |
|
Hallo eLi,
> Beweisen sie per vollständiger Induktion:
> [mm]\summe_{j=0}^{n}\vektor{n \\ 2j}=2^{n-1}[/mm]
> [mm]n\in\IN[/mm]
> Hallo,
> ich bräuchte einen Tipp für obige Aufgabe. Ich schreibe
> erstmal auf, wie weit ich gekommen bin.
>
> Induktionsanfang:
> Für n=1 ist [mm]\summe_{j=0}^{1}\vektor{1 \\ 2j}=1[/mm] , ebenso
> wie [mm]2^{1-1}[/mm] = 1 ist. Der IA ist also korrekt.
>
> Induktionsvorraussetzung:
> Es gilt für ein beliebiges aber festes [mm]n\in\IN[/mm]
>
> Induktionsschritt:
> n [mm]\to[/mm] n+1
>
> [mm]\summe_{j=0}^{n+1}\vektor{n+1 \\ 2j}=\summe_{j=0}^{n}\vektor{n+1 \\ 2j}+\vektor{n+1 \\ 2n+2}[/mm]
> [mm]\vektor{n+1 \\ 2n+2}[/mm] ist per Definition = 0 fällt also
> weg.
> [mm]\summe_{j=0}^{n}\vektor{n+1 \\ 2j}=\summe_{j=0}^{n}[\vektor{n \\ 2j}+\vektor{n \\ 2j-1}]=\summe_{j=0}^{n}\vektor{n \\ 2j}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}[/mm]
>
> Nach der Induktionsvorraussetzung ist
> [mm]\summe_{j=0}^{n}\vektor{n \\ 2j}=2^{n-1}.[/mm]
>
> [mm]\summe_{j=0}^{n}\vektor{n \\ 2j}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}=2^{n-1}+\summe_{j=0}^{n}\vektor{n \\ 2j-1}[/mm]
>
> Um jetzt auf die verbliebende Summe die Vorrausetzung
> anwenden zu können, muss eine Indexverschiebung
> durchgeführt werden. Ich weiß allerdings nicht, wie das
> in diesem Fall funktionieren soll. Kann ich einfach sagen:
> [mm]\summe_{j=0}^{n}\vektor{n \\ 2j-1}=\summe_{j=-1}^{n-1}\vektor{n \\ 2j}?[/mm]
Nein.
Beachte stattdessen:
[mm]\left(1+1\right)^{n}=\summe_{k=0}^{n}\pmat{n \\ k}1^{k}*1^{n-k}=\summe_{k=0}^{n}\pmat{n \\ k}1^{n}=\summe_{k=0}^{n}\pmat{n \\ k}[/mm]
Diese rechte Summe lässt sich auch noch etwas anders schreiben:
[mm]2^{n}=\summe_{k=0}^{n}\pmat{n \\ k}=\summe_{l=1}^{2l-1 \le n}\pmat{n \\ 2l-1}+\summe_{l=0}^{2l \le n}\pmat{n \\ 2l}[/mm]
Der Ausdruck
[mm]\summe_{l=0}^{2l \le n}\pmat{n \\ 2l}[/mm]
kann auch so geschrieben werden:
[mm]\summe_{l=0}^{n}\pmat{n \\ 2l}[/mm]
Damit ergibt sich:
[mm]2^{n}=\summe_{k=0}^{n}\pmat{n \\ k}=\summe_{l=1}^{2l-1 \le n}\pmat{n \\ 2l-1}+\summe_{l=0}^{n}\pmat{n \\ 2l}
[/mm]
Und das kannst Du mit der Induktionsvoraussetzung berechnen.
>
> Wäre für jegliche Hilfe dankbar.
>
> Grüße,
> eLi
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:51 Mo 25.10.2010 | | Autor: | eLi |
Danke schonmal für die Antwort, aber ich versteh noch nicht so ganz, wo genau ich deinen Ansatz jetzt bei mir "unterbringen" kann, sodass es mich weiterbringt. Könntest du mir da vllt nochmal Hilfestellung leisten?
|
|
|
| |
|
Hallo eLi,
> Danke schonmal für die Antwort, aber ich versteh noch
> nicht so ganz, wo genau ich deinen Ansatz jetzt bei mir
> "unterbringen" kann, sodass es mich weiterbringt. Könntest
> du mir da vllt nochmal Hilfestellung leisten?
Ausgehend von
[mm] 2^{n}=\summe_{k=0}^{n}\pmat{n \\ k}=\summe_{l=1}^{2l-1 \le n}\pmat{n \\ 2l-1}+\summe_{l=0}^{n}\pmat{n \\ 2l} [/mm]
Der Ausdruck
[mm]\summe_{l=1}^{2l-1 \le n}\pmat{n \\ 2l-1}[/mm]
kann auch anders geschrieben werden, da
[mm]\pmat{n \\ -1}:=0[/mm]
und
[mm]\pmat{n \\ 2l-1}:=0, \ 2l-1 > n[/mm]
Dann steht hier:
[mm] 2^{n}=\summe_{k=0}^{n}\pmat{n \\ k}=\summe_{l=0}^{n}\pmat{n \\ 2l-1}+\summe_{l=0}^{n}\pmat{n \\ 2l} [/mm]
Und da laut Aufgabe
[mm]\summe_{l=0}^{n}\pmat{n \\ 2l}=2^{n-1}[/mm]
kannst Du aus der Gleichung
[mm] 2^{n}=\summe_{l=0}^{n}\pmat{n \\ 2l-1}+\summe_{l=0}^{n}\pmat{n \\ 2l} [/mm]
den Wert des Ausdruckes
[mm]\summe_{l=0}^{n}\pmat{n \\ 2l-1}[/mm]
bestimmen.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:21 Di 26.10.2010 | | Autor: | eLi |
Ok, ist nachvollziehbar. Aber wie kommst du auf diese Summen?
[mm] 2^{n}=\summe_{k=0}^{n}\pmat{n \\ k}=\summe_{l=1}^{2l-1 \le n}\pmat{n \\ 2l-1}+\summe_{l=0}^{n}\pmat{n \\ 2l}
[/mm]
Warum kann man [mm] 2^{n} [/mm] auch so schreiben, wie nach dem 2. Gleichheitszeichen?
|
|
|
| |
|
Ich bin einfach mal so böse in einem fremden Tread zu antworten...^^
Das erste Gleichheitszeichen ist hoffentlich verständlich.
Nach dem zweiten wurde die Summe, wie man ja sieht, zerlegt.
Warum das aber auch wirklich das gleiche ist siehst du am besten, wenn
du dir die Summen mal ohne Summenzeichen aufschreibst.
Interessant ist hierbei nur der untere Wert des Binominalkoeffizienten.
In der ersten Summe haben wir 2l-1.
Das heißt der erste Wert ist 2*1-1=1
Der zweite Wert ist 2*2-1=3
etc.
In der zweiten Summe haben wir einfach das -1 nicht, also haben wir hier die Werte 0,2,4,6,...
Somit haben wir in der ersten Summe alle ungeraden Zahlen, in der zweiten alle geraden.
Und da der untere Wert immer kleiner oder gleich dem n ist wurde so die gesamte Summe (nicht mehr und nicht weniger^^) in zwei Summen zerlegt, jenachdem ob der untere Wert des Binominalkoeffizienten gerade oder ungerade ist.
|
|
|
|
