Induktion Analysis I < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:54 So 01.11.2009 | | Autor: | xhizux |
Man zeige durch Induktion:
Für n ∈ N \ {1} gilt [mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] = [mm] 2^{n}
[/mm]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Man zeige durch Induktion:
Für n ∈ N \ {1} gilt [mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] = [mm] 2^{n}
[/mm]
Nun mir ist das Prinzip schon klar, jedoch krieg ich den schritt mit der zuhilfenahme der induktionsvorraussetyung nicht hin, oder zumindest nicht ganz
ich würde zuerst n => n+1 und demnach steht da [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}, [/mm] wandle dieses zu [mm] \summe_{k=0}^{n} \vektor{n+1 \\ k} [/mm] , zerteile dies wieder in [mm] \summe_{k=0}^{n} \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1} [/mm] setzte die induktionsvorraussetzung ein.
demnach steht da nun [mm] 2^{n} [/mm] + [mm] \vektor{n \\ k-1}
[/mm]
nur weiß ich jetzt nicht weiter. wie beweise ich denn nun das da [mm] 2^{n+1} [/mm] rauskommt?
Wäre sehr freundlich wenn mir jemand einen tippn geben könnte.
danke
|
|
| |
|
Hallo!
Du hast deinen Beweis in solch einer Schnelligkeit verfasst, dass einige Ungenauigkeiten auftreten. Zu Beginn hast du:
[mm] $\sum_{k=0}^{n+1}\vektor{n+1\\k} [/mm] = [mm] \left(\sum_{k=0}^{n}\vektor{n+1\\k}\right) [/mm] + [mm] \vektor{n+1\\n+1} [/mm] = [mm] \left(\sum_{k=0}^{n}\vektor{n+1\\k}\right) [/mm] + 1$
Dein Ansatz ist nun richtig, wir wollen die Formel [mm] $\vektor{n+1\\ k} [/mm] = [mm] \vektor{n\\k} [/mm] + [mm] \vektor{n\\k-1}$ [/mm] anwenden. Es gibt allerdings ein Problem: Da die obige Summe von $k = 0$ losläuft, wäre der Ausdruck [mm] $\vektor{n\\k-1}$ [/mm] für $k = 0$ nicht besonders elegant. Deswegen werden wir vor dieser Umformung noch den Fall $k=0$ aus der Summe ziehen:
$= [mm] \left(\sum_{k=1}^{n}\vektor{n+1\\k}\right) +\vektor{n+1\\0} [/mm] + 1 = [mm] \left(\sum_{k=1}^{n}\vektor{n+1\\k}\right) [/mm] + 2$
Jetzt also Anwendung der Umformung:
$= 2 + [mm] \sum_{k=1}^{n}\left(\vektor{n\\k} + \vektor{n\\k-1}\right) [/mm] = 2 + [mm] \sum_{k=1}^{n}\vektor{n\\k} [/mm] + [mm] \sum_{k=1}^{n}\vektor{n\\k-1}$
[/mm]
Nun können wir in die erste Summe mit der 1 von vorn wieder den Summanden [mm] $\vektor{n\\0} [/mm] =1$ einfügen; bei der zweiten steht noch $k-1$ im Binomialkoeffizienten. Das umgehen wir, indem wir eine Indexverschiebung der Summe von 1 bis n zu 0 bis n-1 machen. Das bedeutet, in der Summe werden alle k's zu k+1:
$= 1 + [mm] \sum_{k=0}^{n}\vektor{n\\k} [/mm] + [mm] \sum_{k=0}^{n-1}\vektor{n\\k}$
[/mm]
Nun können wir auch die weitere 1 von vorn in die hintere Summe als Summand [mm] $\vektor{n\\n} [/mm] = 1$ einfügen:
$= [mm] \sum_{k=0}^{n}\vektor{n\\k} [/mm] + [mm] \sum_{k=0}^{n}\vektor{n\\k}$
[/mm]
So, und nun ist es noch ein Katzensprung 
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:14 So 01.11.2009 | | Autor: | xhizux |
ah danke!! ★
|
|
|
|
