| Autor |
Beitrag |
    
Rainer
| | Veröffentlicht am Freitag, den 26. Oktober, 2001 - 17:19: | 
|
Hallo! Wer weiß Rat?
Zeige für alle m, n € IN mit n ³ m, dass
"n+1 über m+1", also (n+1m+1) = Sn k=m (km)
Danke! |
Rainer
| | Veröffentlicht am Donnerstag, den 01. November, 2001 - 20:47: |
|
Ähm ... hallo?
Erbitte nur irgendeinen Hinweis, wie die Sache angegangen werden kann ... die Arbeit mach ich mir schon selber, also bitte nicht denken, dass hier der ganze Beweis von vorn bis hinten stehen müsste oder so...
Das kann ich hinterher selber machen, wenn ich den Ansatz habe.
.. oder vielleicht ein Link? |
Axel (Axe)
| | Veröffentlicht am Donnerstag, den 01. November, 2001 - 20:59: |
|
Versuchs mal über vollständige Induktion! |
Rainer
| | Veröffentlicht am Freitag, den 02. November, 2001 - 13:48: |
|
Danke. Gibt es noch einen etwas genaueren Hinweis?
Wie soll die Induktion ablaufen?
von n=1, von m=1, oder wie? |
Martin
| | Veröffentlicht am Samstag, den 03. November, 2001 - 11:37: |
|
Es gilt (n+1 über m+1)=(n über m)+(n über m+1)
(Weil im Pascalschen Dreieck jede Zahl die Summe der 2 darüberstehenden Zahlen ist)
Es gilt auch (n über m+1)=(n-1 über m)+(n-1 über m+1).
Das setzt man in die erste Gleichung ein:
(n+1 über m+1)=(n über m)+(n-1 über m)+(n-1 über m+1).
Es gilt (n-1 über m+1)=(n-2 über m)+(n-2 über m+1).
Wieder eingesetzt ergibt:
(n+1 über m+1)=(n über m)+(n-1 über m)+(n-2 über m)+(n-2 über m+1)
usw.
Weil x über y=0, wenn x<y ist, bricht diese Reihe dann irgendwann ab, und es bleibt genau das gleiche wie in der Angabe. |
Rainer
| | Veröffentlicht am Dienstag, den 06. November, 2001 - 23:33: |
|
Hallo Martin, danke für die noch eingegangene Antwort.
Vom Ablauf her ist mir das verständlich, nur mir wird es nicht ganz klar,
dass dabei auch wirklich genau n-m+1 Summanden herauskommen.
Hier die Musterlösung:
Behauptung: für alle m, n € IN gilt (n+1m+1) = Sn k=m(nm)
Beweis:
durch vollständige Induktion nach n
Induktionsanfang: n=m
(n+1m+1) = 1 = (nm) = Sm k=m(nm)
Induktionsvoraussetzung: für n ³ m gelte (n+1m+1) = Sn k=m(nm)
Induktionsschluss: (n+2m+2)
= (n+1m+1) + (n+1m) (wurde bereits bewiesen)
= Sn k=m(nm) + (n+1m) (gilt nach Induktionsvoraussetzung)
= Sn+1 k=m(nm)
Das soll's gewesen sein.
Dazu noch eine Frage:
Warum reicht Induktion über n?
Warum muss das nicht auch noch von m=1 an gezeigt werden und dann von m auf m+1 vererbt werden? |
|
