induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:38 Di 11.11.2008 | | Autor: | doener |
| Aufgabe | man soll zeigen, dass [mm] \vektor{N+M \\ k+M} =\summe_{i=0}^{M} \vektor{N \\ k+i}\vektor{M \\ i}
[/mm]
zuerst also M=1: das ist einfach, da bekanntlich [mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n-1 \\ k} [/mm] + [mm] \vektor{n-1 \\ k-1} [/mm] gilt.
|
nun also für M+1:
[mm] \summe_{i=0}^{M+1} \vektor{N \\ k+i} \vektor{M+1 \\ i} [/mm] = [mm] \vektor{N \\ k+M+1} [/mm] + [mm] \summe_{i=0}^{M} \vektor{N \\ k+i} \Bigg[\vektor{M \\ i} [/mm] + [mm] \vektor{M \\ i-1}\Bigg]
[/mm]
das wieder wegen der eigenschaft, die schon für M=1 angewendet wurde
= [mm] \vektor{N \\ k+M+1} [/mm] + [mm] \summe_{i=0}^{M} \vektor{N \\ k+i}\vektor{M \\ i} [/mm] + [mm] \summe_{i=0}^{M}\vektor{N \\ k+i} \vektor{M \\ i-1}
[/mm]
das ist auch klar, nun aber:
= [mm] \vektor{N \\ k+M+1} [/mm] + [mm] \vektor{N+M \\ k+M}+\summe_{i=0}^{M-1} \vektor{N \\ k+i+1}\vektor{M \\ i} [/mm]
habe keine ahnung, was hier genau umgeformt wurde, ebenso im nächsten schritt:
= [mm] \vektor{N \\ k+M+1} [/mm] + [mm] \vektor{N+M \\ k+M} [/mm] + [mm] \vektor{N+M\\k+1+M}-\vektor{N \\ k+M+1}
[/mm]
der rest ist dann einfach. danke im voraus!
|
|
| |
|
Von der zweiten zur dritten Zeile wurde im mittleren Term die Induktionsvoraussetzung verwendet. Im hinteren Term wurde der Index i verschoben, also i+1 statt i nach der Summe. Dadurch läuft i nicht mehr von 0 bis M, sondern von -1 bis M-1. Den Summand für i=-1 hat man weggelassen, weil er 0 ergibt: [mm] \vektor{M \\ -1} [/mm] = 0
Von der dritten zur vierten Zeile hat man in Gedanken die letzte Summe um den Summanden für i=M erweitert, dieser wird in der vierten Zeile wieder abgezogen. Und für die dann entstehende Summe die Induktionsvoraussetzung mit k+1 angewendet.
|
|
|
|
