| Autor |
Beitrag |
    
Sascha-Oliver Damm (Nienor)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 19:35: | 
|
Hi Leute!
Bin gerade mit dem Studium angefangen, und hab folgendes Problem:
Ich soll beweisen, das
für alle k,n € N mit 0 £ k £ n (n über k) eine natürliche Zahl ist. |
test
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 21:17: |
|
Hallo!
ich schreibe mal meinen Lösungsversuch hier hin, ich weiß nicht, ob der lupenrein ist.
Mit der Definition von n über k:
(nk) = (n!/k!(n-k)!)
macht man sich durch Ersetzen von k durch k+1 bzw. auch von n durch n+1 klar, dass
(nk) + (nk+1) = (n+1k+1)
gilt.
Ich benutzte jetzt einmal das Verfahren der vollständigen Induktion, und zwar für den Schritt von k ® k+1 bei konstantem n und das andere Mal ein Verfahren, das sich an die vollständige Induktion anlehnt, für den Schritt n ® n+1 bei konstantem k.
Den Induktionsanfang stelle ich dabei ans Ende dieser Ausführung, weil dann deutlicher wird, für welche anfänglichen Wertekombinationen man sich vergewissern muss, dass sich natürliche Zahlen ergeben.
i) Schritt von k nach k+1:
Induktionsannahme: (nk)ÎIN
durch Ersetzen von n durch n+1 und k durch k+1 folgt dann (n+1k+1)ÎIN
Die Differenz dieser beiden natürlichen Zahlen (n+1k+1) - (nk)
ist dann ebenfalls eine natürliche Zahl.
Stellt man die Beziehung (nk) + (nk+1) = (n+1k+1) um, so ergibt sich:
(n+1k+1) - (nk) = (nk+1)
also ist (nk+1) ebenfalls eine natürliche Zahl.
Somit wurde hier gezeigt, dass aus der Aussage (nk)ÎIN die Aussage (nk+1)ÎIN folgt.
ii) nun muss noch der Schritt von n nach n+1 bei konstantem k betrachtet werden:
Es ist zu zeigen, dass aus der Aussage (nk)ÎIN die Aussage (n+1k)ÎIN folgt:
Dem entspricht, zu zeigen, dass aus der Aussage (nk+1)ÎIN die Aussage (n+1k+1)ÎIN folgt:
Nach einem Muster nach der Art der vollständigen Induktion kann man zeigen, dass man mit Hilfe der Gleichung (n0)+(n1) = (n+11) (ausgerechnet 1 + n = n+1)
von (n0)ÎIN und (n1)ÎIN nach (n+11)ÎIN gelangt ist.
Also hat man von der Gültigkeit der zu zeigenden Aussage für n auf die Gültigkeit für n+1 geschlossen, wenn k=0 ist.
Mit Hilfe von i) kann man nun von diesem k=0 auf beliebige Werte für k kommen.
Bleibt noch zu zeigen, dass die Induktion auch einen gültigen Anfang hat:
Nach der Definition (und mit 0!=1) gilt (00) = 1, (10) = 1 und (11) = 1, diese Werte sind alle natürliche Zahlen, also stimmt die Behauptung für den Anfang der Induktion.
Somit ist (nk)ÎIN |
test
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 21:29: |
|
Verbesserung: vor dem vorletzten Satz muss es heißen:
Also hat man von der Gültigkeit der zu zeigenden Aussage für n auf die Gültigkeit für n+1 geschlossen, wenn k=1 ist.
Mit Hilfe von i) kann man nun von diesem k=1 auf beliebige Werte für k kommen. |
Sascha-Oliver Damm (Nienor)
| | Veröffentlicht am Samstag, den 28. Oktober, 2000 - 00:32: |
|
Danke für die promte Beantwortung :-) |
t.
| | Veröffentlicht am Samstag, den 28. Oktober, 2000 - 07:58: |
|
tach!
bist du aus oldenburg?!
informatik?!
bei pieper-geier?! |
Nienor (Nienor)
| | Veröffentlicht am Samstag, den 28. Oktober, 2000 - 17:13: |
|
Hi t.!
So isses *g*
Bist du auch da gelandet? ;-) |
Carmichael
| | Veröffentlicht am Sonntag, den 28. Januar, 2001 - 21:21: |
|
Induktionsannahme: (n k)E IN
"durch Ersetzen von n durch n+1 und k durch k+1 folgt dann (n+1 k+1)E IN "
Kannst doch nicht machen?!!!! Du gehst ja davon aus dass es nur bis (n k) gilt.
Oder steh ich hier auf der Leitung, erklär mir das mal bitte. Ich hab mir mal einen Beweis überlegt, der geht aber mit Primfaktorzerlegung und will ich hier nicht nennen. ist etwas umständlich. |
Carmichael
| | Veröffentlicht am Montag, den 29. Januar, 2001 - 13:04: |
|
Habs mir nochmal durch den Kopf gehen.
Induktion haut tatsächlich. Brauchst aber nur ne von n->n+1 (es soll also immer für alle k gelten)
dazu brauchst dann nur noch die Fälle (n 0) und (n+1 n+1) extra betrachten und die sind trivial E IN. |
|
