Beweis: Binomialkoeffizient < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen oder widerlegen Sie folgende Aussage:
Für jede natürliche Zahl [mm]n \in \IN[/mm] und jede reelle Zahl [mm]\alpha \in \IR[/mm] gilt:
[mm]{{\alpha \choose 0}} + {{\alpha + 1 \choose 1}} + {{\alpha + 2 \choose 2}} + … + {{\alpha + n \choose n}} = {{\alpha + n + 1 \choose n}}[/mm] |
Hallo zusammen!
Leider habe ich noch nicht einmal einen konkreten Ansatz zur Lösung dieser Aufgabe.
Was ich (auf Anhieb) sehe ist nur:
Sei [mm]\alpha = 0[/mm] und [mm]n = 0[/mm], dann gilt
[mm]{{0 \choose 0}} = {{1 \choose 0}} = 1[/mm]
Zumindest für [mm]\alpha, n = 0[/mm] ist die Aussage also wahr.
Mit der mir bekannten Beweistechnik der vollständigen Induktion kommt man hier, denke ich, wohl wegen der reellen Zahl [mm]\alpha[/mm] nicht weiter.
Was sind die nächsten Schritte, die ich zur Lösung der Aufgabe nehmen muss? Oder bin ich sogar schon mit meinem kleinen, schwammigen Ansatz auf dem Holzweg?
|
|
| |
|
Vll. hilft dir die Definition schon weiter
[mm] \vektor{\alpha\\ k} [/mm] = [mm] \begin{cases}\frac{\alpha (\alpha - 1)(\alpha - 2) \dotsm (\alpha - (k - 1))}{k!}, &\text{wenn } k>0\\ 1, &\text{wenn } k=0\\ 0, &\text{wenn } k<0 \end{cases}, [/mm]
damit kann du ja mal die ersten 2 oder 3 Terme zur Behauptung [mm] {{\alpha + 2 + 1 \choose 2}} [/mm] oder [mm] {{\alpha + 3 + 1 \choose 3}} [/mm] umstellen. Wenn das klappt kann man sich weitere schritte überlegen.
|
|
|
| |
|
Danke für Deine Hilfe, Reduktion!
Leider komme ich trotzdem nicht von der Stelle.
Wie kann ich hier was umstellen?
Wenn ich die von Dir angegebene Definition verwende und n = 2 sei, dann hätte ich:
[mm]1 + \bruch{\alpha}{1} + \bruch{\alpha(\alpha-1)}{2}[/mm]
Aber wie hilft mir das jetzt weiter?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:53 Sa 13.10.2012 | | Autor: | pits |
> Wenn ich die von Dir angegebene Definition verwende und n
> = 2 sei, dann hätte ich:
>
> [mm]1 + \bruch{\alpha}{1} + \bruch{\alpha(\alpha-1)}{2}[/mm]
Hier ist ein kleiner Fehler drin, da du immer wieder [mm] $\alpha$ [/mm] in die Definition des Binomialkoeffizienten eingesetzt hast. Du musst jeweils [mm] $\alpha+1$ [/mm] bzw. [mm] $\alpha+2$ [/mm] in die letzten beiden Koeffizienten einsetzen:
[mm]1+\bruch{\alpha+1}{1}+\bruch{(\alpha+2)(\alpha+1)}{2}[/mm]
> Aber wie hilft mir das jetzt weiter?
Dann kannst du auch entsprechend die rechte Seite der Gleichung mit Hilfe der Definition ausdrücken und schauen ob das Gleiche herauskommt. Damit wäre die Aussage für n=2 überprüft und man könnte dies auch als Induktionsanfang nehmen.
|
|
|
| |
|
Hallo Apfelchips,
natürlich geht da vollständige Induktion. Du setzt [mm] \alpha [/mm] als Parameter fest und führst die Induktion über n durch, wie immer.
Du wirst dazu den Quotienten [mm] \bruch{\vektor{\alpha+n+2\\n+1}}{\vektor{\alpha+n+1\\n}} [/mm] benötigen.
Der ist aber mit der Definition, an die Reduktion Dich erinnert hat, ganz leicht zu finden.
Grüße
reverend
|
|
|
| |
|
Hallo reverend,
danke für die Erklärung.
Wirklich schlauer bin ich aber leider trotzdem noch nicht … die ganze Materie ist noch ziemlich neu für mich.
Könnte ich jetzt einfach sagen, dass [mm]\alpha = 0[/mm] und dann für den Induktionsanfang (sei n=0) das hier zeigen?
[mm]{{0 \choose 0}} = 1 = {{0 + 0 + 1 \choose 0}}[/mm]
|
|
|
| |
|
Hallo nochmal,
lass [mm] \alpha [/mm] einfach so stehen.
> danke für die Erklärung.
> Wirklich schlauer bin ich aber leider trotzdem noch nicht
> … die ganze Materie ist noch ziemlich neu für mich.
Welche - Induktion oder verallgemeinerte Binomialkoeffizienten?
> Könnte ich jetzt einfach sagen, dass [mm]\alpha = 0[/mm]
Nein, zeig es für allgemeines [mm] \alpha=\alpha.
[/mm]
> und dann
> für den Induktionsanfang (sei n=0) das hier zeigen?
>
> [mm]{{0 \choose 0}} = 1 = {{0 + 0 + 1 \choose 0}}[/mm]
Anfang bei n=0 ist ok, wenn denn n=0 überhaupt mit zu zeigen ist. Da ist die Formel ja sozusagen selbstverständlich. Interessant wird sie erst danach, deswegen würde ich den Induktionsanfang eher bei n=1 setzen, aber das ist letztlich für die Induktion ziemlich egal.
Grüße
reverend
|
|
|
| |
|
> > … die ganze Materie ist noch ziemlich neu für mich.
>
> Welche - Induktion oder verallgemeinerte
> Binomialkoeffizienten?
Im Grunde sowohl als auch (1. Semester). Beim Thema Induktion fühle ich mich aber fitter als bei verallgemeinerten Binominalkoeffizienten.
Aber Übung macht ja bekanntlich den Meister.
> > Könnte ich jetzt einfach sagen, dass [mm]\alpha = 0[/mm]
>
> Nein, zeig es für allgemeines [mm]\alpha=\alpha.[/mm]
Okay, dann auf ein Neues – diesmal mit n=1 als Start:
IA:
sei n=1
[mm]{{\alpha \choose 0}} + {{\alpha + 1 \choose 1}} = {{\alpha + 2 \choose 1}}[/mm]
aus der Definition folgt damit:
[mm]1+ (\alpha + 1) \gdw (\alpha + 2) = (\alpha + 2)[/mm]
Und das ist eine wahre Aussage.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:45 Sa 13.10.2012 | | Autor: | pits |
> [mm]{{\alpha \choose 0}} + {{\alpha + 1 \choose 1}} = {{\alpha + 2 \choose 1}}[/mm]
>
> aus der Definition folgt damit:
>
> [mm]1+ (\alpha + 1) \gdw (\alpha + 2) = (\alpha + 2)[/mm]
>
> Und das ist eine wahre Aussage.
Genau und damit ist der Induktionsanfang für für $n=1$ gemacht. Jetzt musst du den Induktionsschritt von $n$ nach $n+1$ zeigen. Ich würde es so machen, dass ich mir die Linke Summe für den Fall $n+1$ hinschreibe, die ersten n Terme mit hilfe der Induktionsvorraussetzung (dass nämlich die Aussage für $n$ wahr ist) ersetzen und dann hoffen, dass ich durch Umformung die rechte Seite der Behauptung für $n+1$ hinbekomme.
Liebe Grüße
pits
|
|
|
| |
|
Danke fürs Helfen, pits!
> Jetzt musst du den Induktionsschritt von [mm]n[/mm] nach
> [mm]n+1[/mm] zeigen. Ich würde es so machen, dass ich mir die Linke
> Summe für den Fall [mm]n+1[/mm] hinschreibe, die ersten n Terme mit
> hilfe der Induktionsvorraussetzung (dass nämlich die
> Aussage für [mm]n[/mm] wahr ist) ersetzen und dann hoffen, dass ich
> durch Umformung die rechte Seite der Behauptung für [mm]n+1[/mm]
> hinbekomme.
Das bedeutet also, ich stelle (zunächst einmal) folgende Gleichung auf, oder?
[mm]\underbrace{{{\alpha + n + 1 \choose n}}}_{\mbox{aus der IV.}} + \underbrace{{{\alpha + \red{n + 1} \choose \red{n + 1}}}}_{\mbox{n+1tes Summenglied}} = {{\alpha + \red{n + 1} + 1 \choose \red{n + 1}}}[/mm]
|
|
|
| |
|
Hallo Apfelchips,
> Das bedeutet also, ich stelle (zunächst einmal) folgende
> Gleichung auf, oder?
>
> [mm]\underbrace{{{\alpha + n + 1 \choose n}}}_{\mbox{aus der IV.}} + \underbrace{{{\alpha + \red{n + 1} \choose \red{n + 1}}}}_{\mbox{n+1tes Summenglied}} = {{\alpha + \red{n + 1} + 1 \choose \red{n + 1}}}[/mm]
Jaaa...
Jetzt stell mal die Zeitlupe ab und geh wieder auf "Play".
In dem Tempo sind wir Mitte Februar fast fertig, wenn Du jeden Einzelschritt nachfragst.
Jetzt musst Du "nur noch" das zeigen, was Du da aufgestellt hast.
Schaffst Du das?
Grüße
reverend
|
|
|
| |
|
> Jetzt musst Du "nur noch" das zeigen, was Du da aufgestellt
> hast.
> Schaffst Du das?
Ich habe mal versucht das Ganze in die Fakultätsschreibweise umzuschreiben:
[mm]\bruch{(\alpha + n + 1)!}{n!(\alpha + 1)!} + \bruch{(\alpha + n + 1)!}{(n + 1)!\alpha!} = \bruch{(\alpha + n + 2)!}{(n + 1)!(\alpha + 1)!}[/mm]
Jetzt bilde ich den Hauptnenner:
[mm]\bruch{(\alpha + n + 1)! * (n + 1)! * \alpha! + (\alpha + n + 1)! * n! * (\alpha + 1)!}{n! * (\alpha + 1)! * (n + 1)! * \alpha!} = \bruch{(\alpha + n + 2)!}{(n + 1)!(\alpha + 1)!}[/mm]
Allerdings weiß ich nicht, wie ich die linke Seite der Gleichung jetzt noch so weit umformen kann, dass sie der rechten Seite entspricht.
|
|
|
| |
|
...kann manchmal wundervoll sein.
Aber im Ernst: Dein Hauptnenner ist etwas übertrieben.
> Ich habe mal versucht das Ganze in die
> Fakultätsschreibweise umzuschreiben:
>
> [mm]\bruch{(\alpha + n + 1)!}{n!(\alpha + 1)!} + \bruch{(\alpha + n + 1)!}{(n + 1)!\alpha!} = \bruch{(\alpha + n + 2)!}{(n + 1)!(\alpha + 1)!}[/mm]
>
> Jetzt bilde ich den Hauptnenner:
>
> [mm]\bruch{(\alpha + n + 1)! * (n + 1)! * \alpha! + (\alpha + n + 1)! * n! * (\alpha + 1)!}{n! * (\alpha + 1)! * (n + 1)! * \alpha!} = \bruch{(\alpha + n + 2)!}{(n + 1)!(\alpha + 1)!}[/mm]
[mm] (n+1)!*(\alpha+1)! [/mm] würde vollauf reichen, sofern Du die Fakultäten für reelle Zahlen ordentlich definiert hast.
Grüße
reverend
> Allerdings weiß ich nicht, wie ich die linke Seite der
> Gleichung jetzt noch so weit umformen kann, dass sie der
> rechten Seite entspricht.
|
|
|
| |
|
> [mm](n+1)!*(\alpha+1)![/mm] würde vollauf reichen, sofern Du die
> Fakultäten für reelle Zahlen ordentlich definiert hast.
Das kann ich leider nicht nachvollziehen. Warum würde [mm](n+1)!*(\alpha+1)![/mm] ausreichen?
Generell ist der Weg, den Beweis über die Fakultätsdarstellung zu erbringen, aber möglich und sinnvoll – oder gibt es da einen einfacheren Weg (für Anfänger wie mich)?
|
|
|
| |
|
Hallo nochmal,
als Hauptnenner wählt man doch normalerweise das [mm] \kgV [/mm] aller Nenner.
Da [mm] (\alpha+1)!=(\alpha+1)*\alpha! [/mm] und $(n+1)!=(n+1)*n!$ ist, ist das kleinste gemeinsame Vielfache der beiden Nenner links eben [mm] (\alpha+1)!*(n+1)!.
[/mm]
Und wie es hier einfacher gehen sollte, sehe ich nicht.
Grüße
reverend
|
|
|
| |
|
> Da [mm](\alpha+1)!=(\alpha+1)*\alpha![/mm] und [mm](n+1)!=(n+1)*n![/mm] ist,
> ist das kleinste gemeinsame Vielfache der beiden Nenner
> links eben [mm](\alpha+1)!*(n+1)!.[/mm]
Ich hab mir nochmal die Definition [mm]n! := n * (n-1)![/mm] deutlich gemacht und kann das jetzt auch soweit nachvollziehen.
Ich erweitere also wie folgt:
[mm]\bruch{(\alpha + n + 1)! * (n+1)}{(n + 1)! * (\alpha + 1)!} + \bruch{(\alpha + n + 1)! * (\alpha+1)}{(n + 1)! * (\alpha + 1)!} = \bruch{(\alpha + n + 2)!}{(n + 1)! * (\alpha + 1)!}[/mm]
[mm]\bruch{(\alpha + n + 1)! * (n+1) + (\alpha + n + 1)! * (\alpha+1)}{(n + 1)! * (\alpha + 1)!} = \bruch{(\alpha + n + 2)!}{(n + 1)! * (\alpha + 1)!}[/mm]
Allerdings bekomme ich es nicht hin, den linken Zähler so umzuformen, dass er dem rechten entspricht. Was übersehe ich da?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:12 So 14.10.2012 | | Autor: | pits |
> [mm]\bruch{(\alpha + n + 1)! * (n+1) + (\alpha + n + 1)! * (\alpha+1)}{(n + 1)! * (\alpha + 1)!} = \bruch{(\alpha + n + 2)!}{(n + 1)! * (\alpha + 1)!}[/mm]
>
> Allerdings bekomme ich es nicht hin, den linken Zähler so
> umzuformen, dass er dem rechten entspricht. Was übersehe
> ich da?
Du musst einfach im linken Zähler [mm] $(\alpha+n+1)!$ [/mm] ausklammern. Das was dann übrig bleibt, ergibt den noch fehlenden Faktor.
Gruß
pits
|
|
|
| |
|
> Du musst einfach im linken Zähler
> ausklammern. Das was dann übrig bleibt, ergibt den noch
> fehlenden Faktor.
Autsch … na klar, jetzt seh ich's auch:
[mm]\bruch{(\alpha + n + 1)!\left[(n + 1)+(\alpha + 1)\right]}{(n+1)! * (\alpha + 1)!} = \bruch{(\alpha + n + 2)!}{(n+1)! * (\alpha + 1)!}[/mm]
weil [mm](\alpha + n + 2)! = (\alpha + n + 2) * (\alpha + n + 1)![/mm]
Damit ist der Beweis erbracht. [mm]\square[/mm]
|
|
|
| |
|
Hallo nochmal,
> Damit ist der Beweis erbracht.
So ist es. ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
Dein Satz ist übrigens viel schöner als das übliche "was zu beweisen war", was eine typische Lehnübersetzung ist - von "quod erat demonstrandum".
Hoffentlich setzt sich Deine Fassung durch. Das ist ein vollständiger Hauptsatz, kurz, und mit der ganzen nötigen Aussage, notwendig und hinreichend zugleich.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:09 So 14.10.2012 | | Autor: | Apfelchips |
> Dein Satz ist übrigens viel schöner als das übliche
> "was zu beweisen war", was eine typische Lehnübersetzung
> ist - von "quod erat demonstrandum".
> Hoffentlich setzt sich Deine Fassung durch. Das ist ein
> vollständiger Hauptsatz, kurz, und mit der ganzen nötigen
> Aussage, notwendig und hinreichend zugleich.
Dankeschön. 
|
|
|
|
