Binomialkoeffizient, neg. Zahl < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:19 Sa 17.10.2009 | | Autor: | ChopSuey |
Hallo,
ich habe eine Übungsaufgabe, die mit Hilfe der vollständigen Induktion bewiesen werden soll und bin dann durch gewisse Umformungen irgendwann zu einem ganz bestimmten Binomialkoeffizienten gekommen, der
$\ [mm] \vektor{m \\ -1} [/mm] $ lautet.
Ich hab mir dabei eigentlich nichts gedacht, und erstmal weitergemacht.
Damit das aber wieder verschwindet, habe ich Gebrauch von der Gleichung
$\ [mm] \vektor{n \\ n} [/mm] = [mm] \vektor{n \\ n-k} [/mm] $ gemacht, sprich:
$\ [mm] \vektor{m \\ -1} [/mm] = [mm] \vektor{m \\ m+1}$. [/mm] Ich bin allerdings sehr sehr skeptisch, was das Ganze betrifft.
Darf ein solcher Ausdruck überhaupt entstehen? Beim Rechnen mit Binomialkoeffizienten schleichen sich doch gerne kleine Fehler ein.
Würde mich über eine Antwort freuen,
Danke
Viele Grüße
ChopSuey
|
|
| |
|
Hallo ChopSuey,
sowohl [mm] \vektor{m\\-1} [/mm] als auch [mm] \vektor{m\\m+1} [/mm] stimmen mich skeptisch. Natürlich kommt es darauf an, was Du da eigentlich beweisen willst. Möglicherweise machen ![[]](/images/popup.gif) verallgemeinerte Binomialkoeffizienten ja aber Sinn in Deiner Rechnung. Sei Dir nur bewusst, dass dann [mm] \vektor{m\\-1}=\vektor{m\\m+1}=0 [/mm] ist. Passt das in Deinen Beweis?
Wenn nein, dann zeig mal, wie Du auf den Wert gekommen bist.
> Beim Rechnen mit Binomialkoeffizienten schleichen sich doch
> gerne kleine Fehler ein.
Eben, eben...
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:50 Sa 17.10.2009 | | Autor: | ChopSuey |
Guten Abend reverend!
Die Verallgemeinerung des Binomialkoeffizienten ist ja interessant, danke! So etwas habe ich ungefähr gesucht.
> ja aber Sinn in Deiner Rechnung. Sei Dir nur bewusst, dass
> ... Passt das in
> Deinen Beweis?
Hm, gute Frage. Auf den ersten Blick scheint es mich leider nicht weiter zu bringen. Ich kann aber gerne zeigen, worum es überhaupt geht.
(wollte es erst zurueckhalten, weil es eine Hausübung ist und ich mich durchbeißen wollte)
Aufgabe:
Zeige mittels vollständiger Induktion, daß für alle $\ n,k,m [mm] \in \IN [/mm] $ die folgende Aussage gilt:
$\ {n+m [mm] \choose [/mm] k} = [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} $
so, nun folgen meine Überlegungen :
Induktionsanfang: $ k = 0 [mm] $\\
[/mm]
$ {n+m [mm] \choose [/mm] 0} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] 0} [mm] $\\
[/mm]
$ 1 = 1*1 $ ist wahr. [mm] \\
[/mm]
Wir vermuten, die Aussage gilt für alle $ k [mm] \in \mathbb [/mm] N$.
Induktionsschritt: $k [mm] \to [/mm] k+1$
Es ist $ [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 0} [mm] $\\
[/mm]
Folglich ist $ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 0} + {n [mm] \choose [/mm] k+1} [mm] \red{{m \choose -1}}$\\
[/mm]
Ohhhmann ! Jetzt seh' ich, was ich falsch gemacht hab.
Ich ließ den Laufindex nun von $\ 0 $ bis $\ k+1$ laufen und hab dann aber die obere Grenze nicht richtig eingesetzt, so dass ich $\ [mm] \red{k} [/mm] - (k+1) = -1 $ erhielt, wobei es natürlich $\ [mm] \green{k+1} [/mm] - (k+1) = 0 $ hätte sein sollen.
Richtig müsste es dann wie folgt lauten:
$ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 1} + {n [mm] \choose [/mm] k+1} [mm] \green{{m \choose 0}}$\\
[/mm]
>
> Wenn nein, dann zeig mal, wie Du auf den Wert gekommen
> bist.
>
> > Beim Rechnen mit Binomialkoeffizienten schleichen sich doch
> > gerne kleine Fehler ein.
>
> Eben, eben...
>
> Grüße
> rev
Saugeil, vielen Dank reverend. Du hast mich direkt zur Fehlerquelle geführt  Ich hab tatsächlich kurz bevor ich hier reingeschrieben hab, extra nochmal nachgesehen, ob ich den vermuteten Fehler nicht selbst finde aber ich hab's einfach nicht gesehen.
Viele Grüße
ChopSuey
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:52 Sa 17.10.2009 | | Autor: | ChopSuey |
Hallo nochmal,
da ich den Fehler erst während des Tippens entdeckte, habe ich vergessen, das Ganze nur als Mitteilung zu schreiben, entschuldigt.
Meine Frage hat sich vollständig beantwortet.
Viele Grüße
ChopSuey
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:21 Sa 17.10.2009 | | Autor: | reverend |
Hey, gut!
Ein selbst gefundener Fehler ist immer der beste. Das ist dann keine gefährliche Blockade, kein Unwissen, keine Blindheit - sondern einfach ein Denkfehler.
Wenn Dir eines Tages keiner mehr passiert, sei vorsichtig: wahrscheinlich bist Du tot.
LG, rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:38 Do 22.10.2009 | | Autor: | melisa1 |
Hallo;
ist jmd so net und sagt mir wie man auf diese Reihe kommt:
$ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 1} + {n [mm] \choose [/mm] k+1} [mm] \{{m \choose 0}} [/mm] $
hier steht ja zB:
[mm] \vektor{m \\ k}ich [/mm] dachte man muss hier überall wo k steht k+1 einsetzen muss hier nicht unter m k+1 stehen?
oder hier:
[mm] \vektor{n \\ 1} \vektor{m \\ k-1}
[/mm]
wenn man i=1 ist dann muss doch unter m nur k stehen weil ich für k k+1
einsetze und mein i eins ist also k+1-1= k ?
und hier versteh ich gar nichts mehr warum steht unter n auf einmal k?
$ {n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 1} + {n [mm] \choose [/mm] k+1} [mm] \{{m \choose 0}} [/mm] $
würde mich sehr freuen, wenn mir das jmd erklären kann
Lg Melisa
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:03 Do 22.10.2009 | | Autor: | melisa1 |
Hallo Herby,
> > und hier versteh ich gar nichts mehr warum steht unter n
> > auf einmal k?
> >
> > [mm]{n \choose k} {m \choose 1} + {n \choose k+1} \{{m \choose 0}}[/mm]
>
> hier stimmt das k, weil es ja erst das vorletzte Glied ist
>und anschließend noch i=k+1 folgt.
aber unter dem n ist doch eigentlich i warum ist jz i=k und wie kommt man auf die 1 unter m?
Lg Melisa
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:36 Do 22.10.2009 | | Autor: | Herby |
Hallo Melisa,
> Hallo Herby,
>
> > > und hier versteh ich gar nichts mehr warum steht unter n
> > > auf einmal k?
> > >
> > > [mm]{n \choose k} {m \choose 1} + {n \choose k+1} \{{m \choose 0}}[/mm]
>
> >
>
> > hier stimmt das k, weil es ja erst das vorletzte Glied ist
> >und anschließend noch i=k+1 folgt.
>
>
>
> aber unter dem n ist doch eigentlich i warum ist jz i=k und
> wie kommt man auf die 1 unter m?
weil es erst das vorletzte Glied ist - mmmh
Nehmen wir z.B. mal für i=0 bis i=k
$ [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k-0}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k-2} {m [mm] \choose [/mm] k-(k-2)}+{n [mm] \choose [/mm] k-1} {m [mm] \choose [/mm] k-(k-1)}+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] k-k}$
So, nun das gleiche für i=0 bis k+1
$ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k+1-0}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k+1-1}+...+{n [mm] \choose [/mm] k-2} {m [mm] \choose [/mm] k+1-(k-2)}+{n [mm] \choose [/mm] k-1} {m [mm] \choose k+1-(k-1)}+\underbrace{n \choose k}_{n\ "uber\ k} \underbrace{m \choose k+1-k}_{m\ "uber\ 1}+{n \choose k+1} \underbrace{m \choose k+1-(k+1)}_{m\ "uber\ 0}$
[/mm]
Nu besser?
Lg
Herby
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:43 Do 22.10.2009 | | Autor: | melisa1 |
Hallo Herby,
ja danke schon besser :D
ist damit jz der beweis zu ende, weil bei beiden (also k und k+1) das letzte glied gleich (also m über 0) ist?
Lg Melisa
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:48 Do 22.10.2009 | | Autor: | Herby |
> Hallo Herby,
>
> ja danke schon besser :D
>
> ist damit jz der beweis zu ende, weil bei beiden (also k
> und k+1) das letzte glied gleich (also m über 0) ist?
Öhm - nach dem Beweis hatte ich jetzt gar nicht geschaut. Ich hatte dir nur deine Frage beantwortet, wie man zu den Reihengliedern kommt.
Aber ich denke schon, da es ja bislang keine Rückfragen mehr gab
Liebe Grüße
Herby
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:04 Do 22.10.2009 | | Autor: | melisa1 |
Hallo;
ich glaub es ist noch nicht fertig
ich soll zeigen das $ \ {n+m [mm] \choose [/mm] k} = [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} $
und das habe ich damit glaube ich noch nicht oder :S
Lg Melisa
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:29 Do 22.10.2009 | | Autor: | Herby |
Hi,
> Hallo;
>
> ich glaub es ist noch nicht fertig
>
> ich soll zeigen das [mm]\ {n+m \choose k} = \sum\limits_{i=0}^k {n \choose i} {m \choose k-i}[/mm]
>
> und das habe ich damit glaube ich noch nicht oder :S
>
ah ok, jetzt habe ich mir das auch mal angeschaut - es handelt sich um die Vandermonde Identität (da findest du genug drüber im Netz). Aber vielleicht hilft dir ja auch schon mal jener welcher Artikel weiter:
![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]") Vandermonde Identität
Lg
Herby
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
ja, müsste eigentlich
