Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:52 Di 21.10.2008 | | Autor: | ohlala |
| Aufgabe | Zeigen sie mittels Induktion, dass für beliebige n,k in N die Gleichheit:
[mm][mm] {n+k\choose k}=\summe_{m=k-1}^{n+k-1}{m\choose k-1} [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also ich brauch unbedingt hilfe und würde mich riesig freuen wenn ihr die Aufgabe genau beschreiben könntet.
vielen lieben dank jetzt schon mal
lg ohlala
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:32 Di 21.10.2008 | | Autor: | Marcel |
Hallo,
> Zeigen sie mittels Induktion, dass für beliebige n,k in N
> die Gleichheit:
> [mm]{n+k\choose k}=\summe_{m=k-1}^{n+k-1}{m\choose k-1}[/mm]
> Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
> Also ich brauch unbedingt hilfe und würde mich riesig freuen wenn ihr die > Aufgabe genau beschreiben könntet.
> vielen lieben dank jetzt schon mal
> lg ohlala
na, etwas mußt Du schon selbst tun.
Ich kann Dir die Aufgabe mal umformulieren, vll. wird sie dann verständlicher für Dich:
Zeige, dass für jedes beliebige, aber feste $k [mm] \in \IN$ [/mm] gilt:
Für alle $n [mm] \in \IN$ [/mm] gilt:
[mm] $${n+k\choose k}=\summe_{m=k-1}^{n+k-1}{m\choose k-1}$$
[/mm]
Beweis.
Sei zunächst $k [mm] \in \IN$ [/mm] beliebig, aber fest.
Den Induktionsstart führst Du nun entweder für $n=0$ (falls bei Euch $0 [mm] \in \IN$) [/mm] oder für $n=1$ (falls bei Euch $0 [mm] \notin \IN$).
[/mm]
Ich mach's mal für $n=1$ (da bei mir $0 [mm] \notin \IN$, [/mm] und ich die Notation [mm] $\IN_0$ [/mm] für [mm] $\IN_0=\IN \cup \{0\}$ [/mm] benutze):
Zu zeigen ist hier also [mm] ${1+k\choose k}\overset{!}{=}\summe_{m=k-1}^{1+k-1}{m\choose k-1}=\summe_{m=k-1}^{k}{m\choose k-1}={k-1\choose k-1}+{k\choose k-1}\,.$
[/mm]
(Notfalls müßtest Du, falls bei Euch $0 [mm] \in \IN$, [/mm] den Fall $k=0$ nochmal gesondert betrachten und danach den Induktionsbeweis wie oben für $k [mm] \in \IN$ [/mm] mit $k [mm] \ge [/mm] 1$ betrachten.)
Dass das gilt, kannst Du entweder explizit durch einsetzen Eurer Definition der Binomialkoeffizienten nachprüfen, oder aber Du schaust in Satz 2.11 von ![[]](/images/popup.gif) hier. (Setze dort [mm] $n=\nu=k$ [/mm] ein.)
(Bzw. noch einfacher gehts, wenn man weiß (oder sich überlegen kann), dass [mm] ${k-1\choose k-1}=1$, ${k\choose k-1}=k$ [/mm] und [mm] ${k+1\choose k}=k+1\,.$)
[/mm]
Nun kommt der Induktionsschritt $n [mm] \mapsto [/mm] n+1$:
I.V. Es gelte nun [mm] ${n+k\choose k}=\summe_{m=k-1}^{n+k-1}{m\choose k-1}$ [/mm] für (irgend) ein $n [mm] \in \IN$.
[/mm]
Zu zeigen:
Dann gilt auch
[mm] ${n+1+k\choose k}\overset{!}{=}\summe_{m=k-1}^{n+1+k-1}{m\choose k-1}$
[/mm]
Satz 2.11 von oben liefert Dir nun:
[mm] $(\star)$ ${n+1+k\choose k}={(n+k)+1\choose k}\overset{\text{Satz 2.11}}{=}\blue{{n+k\choose k}}+{n+k\choose k-1}$
[/mm]
Auf den blauen Term kannst Du nun die I.V. anwenden. Danach vergleiche dies mit [mm] $\summe_{m=k-1}^{n+1+k-1}{m\choose k-1}$, [/mm] denn das soll ja am Ende bei der Rechnung in [mm] $(\star)$ [/mm] stehen.
Gruß,
Marcel
|
|
|
|
