Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:00 So 19.11.2006 | | Autor: | simon_g |
| Aufgabe | Man zeige durch Induktion, daß für [mm] n,k \in \IN_0\ mit\ 0\le k \le n [/mm] gilt:
[mm] {n \choose k} = \frac{n!}{k!(n-k)!} [/mm]. Dabei ist [mm] {n \choose k} [/mm] rekursiv definiert mit
[mm] {n \choose 0 } := {n \choose n} := 1 [/mm] und für [mm] 1 \le k < n [/mm] gilt [mm] {n+1 \choose k+1} := {n \choose k} + { n \choose k+1} [/mm]. |
Also, ich habe den Induktionsanfang für [mm] n=0 [/mm] gemacht und hatte wegen [mm] 0\le k \le n [/mm] auch keine weitere Fallunterscheidung zu machen. Somit ist die Induktionsvoraussetzung [mm] {n \choose k} = \frac{n!}{k!(n-k)!} [/mm].
Beim Induktionsschluss ist meiner Meinung ja auf Grund von k eine Fallunterscheidung zu machen. [mm] k=0 \vee k = n+1 [/mm] ergibt sich durch die Definition ja 1. Das Problem ist für mich nun, dass [mm] {n+1 \choose k+1} := {n \choose k} + { n \choose k+1} [/mm] ja nur für [mm] 1 \le k < n [/mm] gilt, also letztlich für [mm] 2 \le l \le n [/mm] mit [mm] l = k+1 [/mm]. Somit wäre ja das ganze für l=1 gar nicht gezeigt, also [mm] {n+1 \choose 1} [/mm]......An dieser Stelle hänge ich jetzt schon ein wenig....vielleicht kann mir ja jmd von euch weiterhelfen, danke schon mal im voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo [mm] simon_g,
[/mm]
> Man zeige durch Induktion, daß für [mm]n,k \in \IN_0\ mit\ 0\le k \le n[/mm]
> gilt:
> [mm]{n \choose k} = \frac{n!}{k!(n-k)!} [/mm]. Dabei ist [mm]{n \choose k}[/mm]
> rekursiv definiert mit
> [mm]{n \choose 0 } := {n \choose n} := 1[/mm] und für [mm]1 \le k < n[/mm]
> gilt [mm]{n+1 \choose k+1} := {n \choose k} + { n \choose k+1} [/mm].
>
> Also, ich habe den Induktionsanfang für [mm]n=0[/mm] gemacht und
> hatte wegen [mm]0\le k \le n[/mm] auch keine weitere
> Fallunterscheidung zu machen. Somit ist die
> Induktionsvoraussetzung [mm]{n \choose k} = \frac{n!}{k!(n-k)!} [/mm].
> Beim Induktionsschluss ist meiner Meinung ja auf Grund von
> k eine Fallunterscheidung zu machen. [mm]k=0 \vee k = n+1[/mm]
> ergibt sich durch die Definition ja 1. Das Problem ist für
> mich nun, dass [mm]{n+1 \choose k+1} := {n \choose k} + { n \choose k+1}[/mm]
> ja nur für [mm]1 \le k < n[/mm] gilt, also letztlich für [mm]2 \le l \le n[/mm]
> mit [mm]l = k+1 [/mm]. Somit wäre ja das ganze für l=1 gar nicht
> gezeigt, also [mm]{n+1 \choose 1} [/mm]......An dieser Stelle hänge
> ich jetzt schon ein wenig....vielleicht kann mir ja jmd von
> euch weiterhelfen, danke schon mal im voraus
Langsam: Sei $0 [mm] \le [/mm] k [mm] \le [/mm] n+1$.
1. $k=n+1$; dann ist [mm]{n+1 \choose k}={n+1\choose 0}=1}[/mm] aufgrund der Definition; andererseits ist aber [mm]\bruch{(n+1)!}{\underbrace{k=0}k!(n+1-k)!}=\bruch{(n+1)!}{0! \cdot{} (n+1)!}=1[/mm], stimmt also.
2. $k<n+1$. Wegen $k [mm] \le [/mm] n$ ergibt sich $1 [mm] \le [/mm] k+1 [mm] \le [/mm] n+1$.
2a $k+1=n+1 [mm] \gdw [/mm] k=n$; entspr. wie 1.
2b [mm] $1\le [/mm] k+1 <n+1 [mm] \gdw [/mm] 0 [mm] \le [/mm] k <n$.
Die Bedingung $1 [mm] \le [/mm] k <n$ ist doch gleichbedeutend mit $0<k<n$  .
Speziell für $k=1, [mm] \quad [/mm] n [mm] \ge [/mm] 1$: [mm]{n \choose 1}={n-1 \choose 1} +{n-1 \choose 0} ={n-1 \choose 1}+1[/mm]. Damit läßt sich (auch ohne Induktion ) [mm]{n \choose 1}, n \ge 1[/mm] bestimmen.
Übrigens folgt aus der Definition noch für [mm]n \ge k[/mm]: [mm]{n+1 \choose k+1}=\summe_{i=k}^n {i \choose k}[/mm].
Hth
zahlenspieler
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Di 21.11.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
