matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKombinatorikBeweis: Binomialkoeffizient
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Kombinatorik" - Beweis: Binomialkoeffizient
Beweis: Binomialkoeffizient < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:44 Fr 12.10.2012
Autor: Apfelchips

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?

        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 17:08 Fr 12.10.2012
Autor: Reduktion

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.

Bezug
                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:47 Sa 13.10.2012
Autor: Apfelchips


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?



Bezug
                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
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.



Bezug
        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 15:04 Sa 13.10.2012
Autor: reverend

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


Bezug
                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:03 Sa 13.10.2012
Autor: Apfelchips


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]


Bezug
                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 17:23 Sa 13.10.2012
Autor: reverend

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


Bezug
                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:00 Sa 13.10.2012
Autor: Apfelchips


> > … 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.


Bezug
                                        
Bezug
Beweis: Binomialkoeffizient: Induktionsanfang gut ...
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:42 Sa 13.10.2012
Autor: Apfelchips


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]


Bezug
                                                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 21:15 Sa 13.10.2012
Autor: reverend

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


Bezug
                                                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:16 So 14.10.2012
Autor: Apfelchips



> 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.

Bezug
                                                                        
Bezug
Beweis: Binomialkoeffizient: Zuviel des Guten...
Status: (Antwort) fertig Status 
Datum: 15:11 So 14.10.2012
Autor: reverend

...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.


Bezug
                                                                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:59 So 14.10.2012
Autor: Apfelchips



> [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)?

Bezug
                                                                                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 16:22 So 14.10.2012
Autor: reverend

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


Bezug
                                                                                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:07 So 14.10.2012
Autor: Apfelchips


>  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?

Bezug
                                                                                                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                                                                
Bezug
Beweis: Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:51 So 14.10.2012
Autor: Apfelchips


> 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]

Bezug
                                                                                                                        
Bezug
Beweis: Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
Datum: 19:03 So 14.10.2012
Autor: reverend

Hallo nochmal,

> Damit ist der Beweis erbracht.

So ist es. [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


Bezug
                                                                                                                                
Bezug
Beweis: Binomialkoeffizient: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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. :-)


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]