Binomialkoeffizient - Symm. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie die Identität mit vollständiger Induktion über n unter Verwendung der Rekursion für Binomialkoeffizienten.
[mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n \\ n-k} [/mm] für alle n,k [mm] \in \IN [/mm] mit 0 [mm] \le [/mm] k [mm] \le [/mm] n |
Hallo,
ich soll die Identität mit Induktion beweisen.
Da steht ja unter Verwendung der Rekursion für Binomialkoeff. ALso die beiden hier:
[mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n-1 \\ k} [/mm] + [mm] \vektor{n-1 \\ k-1}
[/mm]
und
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{k!}{(n-k)k!}
[/mm]
Ich spare mir mal den Induktionsanfang und kürze ab:
IV : Es gelte [mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n \\ n-k} [/mm]
IS: n -> n+1
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k} [/mm] + [mm] \vektor{n \\ k-1}
[/mm]
Wie gehe ich jetzt am besten vor, ich muss jetzt irgendwie auf [mm] \vektor{n+1 \\ n+1-k} [/mm] kommen.
Hat jemand einen Tipp, welche Rekursionsformel ich hier benutzen sollte, um es nicht unnötig kompliziert zu machen?
Vielen Dank im Voraus.
|
|
| |
|
Hallo,
dein Ansatz ist doch richtig*.
Die beiden Summanden auf der rechten Seite lassen sich jetzt entsprechend der Induktionsvoraussetzung umformen. Dann die Addition zweier benachbarter Binomialkoeffizienten anwenden, und du bis fertig.
*Den Induktionsanfang wegzulassen ist noch nie eine gute Idee gewesen.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:34 Di 27.12.2016 | | Autor: | sinnlos123 |
Ich möchte zustimmen, dass es eine schlechte Angewohnheit ist den Induktionsanfang wegzulassen.
|
|
|
| |
|
Hallo,danke für die Antworten.
Den Anfang habe ich aus Faulheit weggelassen, aufgeschrieben habe ich ihn natürlich.
Dennoch habe ich eine Frage:
"Dann die Addition zweier benachbarter Binomialkoeffizienten anwenden, und du bis fertig."
Was ist mit "benachbarter Binom.koeffizienten" gemeint? Das habe ich noch nicht ganz verstanden.
|
|
|
| |
|
Hallo,
> Dennoch habe ich eine Frage:
>
> "Dann die Addition zweier benachbarter
> Binomialkoeffizienten anwenden, und du bis fertig."
>
> Was ist mit "benachbarter Binom.koeffizienten" gemeint? Das
> habe ich noch nicht ganz verstanden.
[mm] \vektor{n \\ k}+ \vektor{n \\ k+1}= \vektor{n+1 \\ k+1}[/mm]
Die beiden Binomialkoeffizienten auf der linken Seite stehen im ![[]](/images/popup.gif) Pascal'schen Dreieck nebeneinander, daher meine Ausdrucksweise.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:05 Di 27.12.2016 | | Autor: | pc_doctor |
Ah, jetzt macht es Klick :D
Okay, vielen Dank für die Antwort. Das sollte ich nun alleine hinbekommen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:52 Di 27.12.2016 | | Autor: | X3nion |
Hallo pc_doctor,
falls es dich interessiert, es gibt auch einen anderen Lösungsweg ohne vollständige Induktion, der sich an der Definition und an Umformungen der Definition entlanghangelt.
Es gilt nach Definition
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n!}{k!(n-k)!}
[/mm]
Somit ergibt sich:
[mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n!}{k!(n-k)!} [/mm] = [mm] \bruch{n!}{(n-k)!k!} [/mm] = [mm] \bruch{n!}{(n-k)!(n-(n-k))!} [/mm] = [mm] \vektor{n \\ n-k}
[/mm]
Viele Grüße,
X3nion
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:55 Mi 28.12.2016 | | Autor: | pc_doctor |
Hallo,
danke für die Antwort. Das geht natürlich auch, aber das hatten wir quasi schon bewiesen. Induktion war leider Pflicht.
|
|
|
|
