Binomialkoeffizient < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:32 So 31.10.2010 | | Autor: | IG0R |
| Aufgabe | Weisen Sie nach, dass die nachfolgende Gleichung für alle $n [mm] \in \mathds{N}$ [/mm] und alle $k [mm] \in \mathds{N}$ [/mm] mit $k [mm] \leq [/mm] n$ gültig ist:
[mm] $\binom{n+1}{k+1} [/mm] = [mm] \sum \limits_{m=k}^{n} \binom{m}{k}$
[/mm]
TIPP: Im Induktionsschritt muss eine Fallunterscheidung vorgenommen werden. |
Jetzt zu meiner Frage. Ich habe für den Induktionsbeweis 2 Fälle betrachtet. Zum einen k=n. Der Fall ist einfach, da man da auf beiden Seiten einfach 1 stehen hat.
Dann als zweiten Fall k<n. Dort habe ich dann eine Induktion über n gemacht. Mit der Voraussetzung [mm] $\binom{n+1}{k+1} [/mm] = [mm] \sum \limits_{m=k}^n \binom{m}{k} [/mm] ~ [mm] \forall_{k < m}$ [/mm] und der Behauptung [mm] $\binom{n+2}{k+1} [/mm] = [mm] \sum \limits_{m=k}^{n+1} \binom{m}{k} ~\forall_{k
So ich hoffe mal, dass ich genug Informationen gegeben habe, ansonsten kann ich die Schritte der Induktion auch genau aufschreiben. Schonmal vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:05 So 31.10.2010 | | Autor: | abakus |
> Weisen Sie nach, dass die nachfolgende Gleichung für alle
> [mm]n \in \mathds{N}[/mm] und alle [mm]k \in \mathds{N}[/mm] mit [mm]k \leq n[/mm]
> gültig ist:
>
> [mm]\binom{n+1}{k+1} = \sum \limits_{m=k}^{n} \binom{m}{k}[/mm]
>
> TIPP: Im Induktionsschritt muss eine Fallunterscheidung
> vorgenommen werden.
> Jetzt zu meiner Frage. Ich habe für den Induktionsbeweis
> 2 Fälle betrachtet. Zum einen k=n. Der Fall ist einfach,
> da man da auf beiden Seiten einfach 1 stehen hat.
Hallo,
dürft ihr die recht bekannte Beziehung [mm] \binom{n+1}{k+1} =\binom{n}{k} +\binom{n}{k+1} [/mm] benutzen?
Aus ihr folgt
[mm] \binom{n+1}{k+1} [/mm]
[mm] =\binom{n}{k} +\binom{n}{k+1}
[/mm]
[mm] =\binom{n}{k} +\binom{n-1}{k}+\binom{n-1}{k-1}
[/mm]
[mm] =\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-2}{k-1}
[/mm]
[mm] =\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-3}{k}+\binom{n-3}{k-1}
[/mm]
...
Gruß Abakus
>
> Dann als zweiten Fall k<n. Dort habe ich dann eine
> Induktion über n gemacht. Mit der Voraussetzung
> [mm]\binom{n+1}{k+1} = \sum \limits_{m=k}^n \binom{m}{k} ~ \forall_{k < m}[/mm]
> und der Behauptung [mm]\binom{n+2}{k+1} = \sum \limits_{m=k}^{n+1} \binom{m}{k} ~\forall_{k
> Da sind soweit keinerlei Probleme aufgetreten. Allerdings
> meine ich mich erinnern zu können, dass das nicht so
> einfach war wie ich mir das grad gedacht habe. Denn musste
> man nicht auch zeigen, dass es wirklich für alle k gilt?
> Und wie genau wäre denn da der Ansatz?
>
> So ich hoffe mal, dass ich genug Informationen gegeben
> habe, ansonsten kann ich die Schritte der Induktion auch
> genau aufschreiben. Schonmal vielen Dank im Voraus.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:19 So 31.10.2010 | | Autor: | IG0R |
> Hallo,
> dürft ihr die recht bekannte Beziehung [mm]\binom{n+1}{k+1} =\binom{n}{k} +\binom{n}{k+1}[/mm]
> benutzen?
> Aus ihr folgt
> [mm]\binom{n+1}{k+1}[/mm]
> [mm]=\binom{n}{k} +\binom{n}{k+1}[/mm]
> [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-1}{k-1}[/mm]
>
> [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-2}{k-1}[/mm]
>
> [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-3}{k}+\binom{n-3}{k-1}[/mm]
>
> ...
> Gruß Abakus
Zum Einen ja die Formel dürfen wir benutzen, aber es müsste jeweils beim zweiten Koeffizienten, den du einsetzt, ein k+1 statt dem k-1 stehen, wenn ich das richtig sehe. Aber ich sehe jetzt nicht was du mir mit dem Hinweis sagen willst.
Das beantwortet auch nicht die Frage, ob man für den Teil "für alle k <= n" noch eine weitere Induktion oder ähnliches machen muss, denn die normale Induktion über n für EIN festes k habe ich ja schon gezeigt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:15 So 31.10.2010 | | Autor: | abakus |
> > Hallo,
> > dürft ihr die recht bekannte Beziehung
> [mm]\binom{n+1}{k+1} =\binom{n}{k} +\binom{n}{k+1}[/mm]
> > benutzen?
> > Aus ihr folgt
> > [mm]\binom{n+1}{k+1}[/mm]
> > [mm]=\binom{n}{k} +\binom{n}{k+1}[/mm]
> > [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-1}{k-1}[/mm]
>
> >
> > [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-2}{k-1}[/mm]
>
> >
> > [mm]=\binom{n}{k} +\binom{n-1}{k}+\binom{n-2}{k}+\binom{n-3}{k}+\binom{n-3}{k-1}[/mm]
>
> >
> > ...
> > Gruß Abakus
>
> Zum Einen ja die Formel dürfen wir benutzen, aber es
> müsste jeweils beim zweiten Koeffizienten, den du
> einsetzt, ein k+1 statt dem k-1 stehen, wenn ich das
> richtig sehe. Aber ich sehe jetzt nicht was du mir mit dem
> Hinweis sagen willst.
> Das beantwortet auch nicht die Frage, ob man für den Teil
> "für alle k <= n" noch eine weitere Induktion oder
> ähnliches machen muss, denn die normale Induktion über n
> für EIN festes k habe ich ja schon gezeigt.
Ja, du hast recht, es muss k+1 heißen.
Das kann so lange fortgeführt werden, bis der letzte Summand den Wert [mm] 1=\binom{n-(n-k)}{k} [/mm] hat.
Gruß Abakus
|
|
|
|
