Summe von Binomialkoeffizienten

12.07.2004, 20:29

Mathespezialschüler

Summe von Binomialkoeffizienten

Hi, hab grad was bei Wikipedia gefunden. Ich stells mal hierhin, hätte natürlich auch in Stochastik gepasst:

$\begin{eqnarray*} \sum_{i=0}^n~\begin{pmatrix} i \\ k \end{pmatrix} = \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \end{eqnarray*}$

1. Frage: Warum ist das so?? (Bitte ohne vollständige Induktion)

2. Frage: Muss k nicht immer gleich 0 sein, wenn z.B. k=4 und n=7:

$\begin{eqnarray*} \sum_{i=0}^7~\begin{pmatrix} i \\ 4 \end{pmatrix} = \begin{pmatrix} 0 \\ 4 \end{pmatrix} + \begin{pmatrix} 1 \\ 4 \end{pmatrix} + \begin{pmatrix} 2 \\ 4 \end{pmatrix} + \begin{pmatrix} 3 \\ 4 \end{pmatrix} + \begin{pmatrix} 4 \\ 4 \end{pmatrix} + \begin{pmatrix} 5 \\ 4 \end{pmatrix} + \begin{pmatrix} 6 \\ 4 \end{pmatrix} + \begin{pmatrix} 7 \\ 4 \end{pmatrix} \end{eqnarray*}$
Ich kann mir nämlich nicht vorstellen, wie $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ für $\begin{eqnarray*} n < k \end{eqnarray*}$ definiert ist verwirrt

?!

Danke euch!

12.07.2004, 20:50

grybl

Auf diesen Beitrag antworten »

RE: Summe von Binomialkoeffizienten

Zitat:

Ich kann mir nämlich nicht vorstellen, wie $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ für $\begin{eqnarray*} n < k \end{eqnarray*}$ definiert ist verwirrt

Schau mal bei Binomialkoeffizient nach. Da wird dir gleich zu Beginn deine Frage durch eine Definition beantwortet. smile

12.07.2004, 20:51

Philipp-ER

Auf diesen Beitrag antworten »

Hi.
Zu deiner 2. Frage:
Schreib dir die Definition doch einfach mal für konkrete Zahlen hin.
Du wirst sehen, dass es gerade 0 ist.

12.07.2004, 21:06

Guevara

Auf diesen Beitrag antworten »

Gibt es so eine Formel auch für
$\begin{eqnarray*} \sum_{k=0}^n~(\frac{s}{k}) \end{eqnarray*}$
Das s müsste eigentlich ein n sein aber das war schon vergeben. Wie macht man eigentlich n über k beim mimetex.

12.07.2004, 21:09

Philipp-ER

Auf diesen Beitrag antworten »

Wenn ich deine Summe richtig verstehe, so ist das gerade $\begin{eqnarray*} 2^n \end{eqnarray*}$

12.07.2004, 21:16

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Guevara
Gibt es so eine Formel auch für
$\begin{eqnarray*} \sum_{k=0}^n~(\frac{s}{k}) \end{eqnarray*}$
Das s müsste eigentlich ein n sein aber das war schon vergeben. Wie macht man eigentlich n über k beim mimetex.

Die kenne ich eigentlich auch schon, is wohl relativ bekannt und wie Philipp schon gesagt hat, gilt:

$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} n \\ k \end{pmatrix} = 2^n \end{eqnarray*}$

@Philipp und @grybl

Danke für die Antworten, 2. Frage is jetz klar, aber die 1.?

edit: Wenn $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = 0 \end{eqnarray*}$ für $\begin{eqnarray*} n < k \end{eqnarray*}$ , könnte man die Summe dann nicht einfach weniger verwirrend darstellen, indem man schreibt:

$\begin{eqnarray*} \sum_{i=k}^n~\begin{pmatrix} i \\ k \end{pmatrix} = \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \end{eqnarray*}$

13.07.2004, 11:39

Guevara

Auf diesen Beitrag antworten »

Das hab ich nicht so gemeint. Es soll nicht die summe aller Kombinationen zusammen gezählt werden.
z.B. 5 über k, und ich will nur die Summe von k= 0,1,2,3 und das in einer Formel.

13.07.2004, 11:59

Philipp-ER

Auf diesen Beitrag antworten »

@Guevara: Dann verstehe ich nicht, was du meinst.
@Spezialschüler: Doch, kann man, ich kannte es auch so (abgesehen davon, dass du dich auf der rechten Seite der Gleichung vertippt hast, da muss natürlich immernoch n+1 stehen).

Warum willst du die Aussage denn eigentlich unbedingt ohne Induktion beweisen?

13.07.2004, 12:04

Guevara

Auf diesen Beitrag antworten »

Wenn ich zum Beispiel rechnen will:
Ich werfe 20 münzen wie groß ist die Wahrscheinlichkeit dass mehr als 15 mal zahl fällt. Da muss ich doch die Wahrscheinlichkeiten Summieren. Wie geht dass?

13.07.2004, 15:47

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Philipp-ER
@Spezialschüler: Doch, kann man, ich kannte es auch so (abgesehen davon, dass du dich auf der rechten Seite der Gleichung vertippt hast, da muss natürlich immernoch n+1 stehen).

Warum willst du die Aussage denn eigentlich unbedingt ohne Induktion beweisen?

Ja, hab die 1 vergessen, danke!

Zur Induktion:
Ich möcht ja erstmal gar nicht so richtig "beweisen", sondern nur wissen, warum das so ist, also irgendwie ne logische Erklärung oder Ähnliches.

Ne kleine Idee bzw. ein Ansatz:
Man kann doch z.B., wenn das nicht direkt geht, erstmal schreiben:

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k+1 \end{pmatrix} \end{eqnarray*}$

D.h. man müsste "nur" zeigen, dass

$\begin{eqnarray*} \sum_{i=k}^n~\begin{pmatrix} i \\ k \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k+1 \end{pmatrix} \end{eqnarray*}$

, wenn das irgendwie leichter sein sollte.

14.07.2004, 08:43

Mathespezialschüler

Auf diesen Beitrag antworten »

Sorry für den Doppelpost, aber der letzte Post is ja schon n bisschen her.

Mir is da was eingefallen:

$\begin{eqnarray*} \sum_{i=k}^n~\begin{pmatrix} i \\ k \end{pmatrix} = \begin{pmatrix} k \\ k \end{pmatrix} + \begin{pmatrix} k+1 \\ k \end{pmatrix} + \begin{pmatrix} k+2 \\ k \end{pmatrix} + \begin{pmatrix} k+3 \\ k \end{pmatrix} + ... + \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

Es gilt: $\begin{eqnarray*} \begin{pmatrix} k \\ k \end{pmatrix} = \begin{pmatrix} k+1 \\ k+1 \end{pmatrix} \end{eqnarray*}$

Wie schon gesagt, ist dann

$\begin{eqnarray*} \begin{pmatrix} k+1 \\ k+1 \end{pmatrix} + \begin{pmatrix} k+1 \\ k \end{pmatrix} = \begin{pmatrix} k+2 \\ k+1 \end{pmatrix} \end{eqnarray*}$

Und für die Summe:

$\begin{eqnarray*} \sum_{i=k}^n~\begin{pmatrix} i \\ k \end{pmatrix} = \begin{pmatrix} k+2 \\ k+1 \end{pmatrix} + \begin{pmatrix} k+2 \\ k \end{pmatrix} + \begin{pmatrix} k+3 \\ k \end{pmatrix} + ... + \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} = \begin{pmatrix} k+3 \\ k+1 \end{pmatrix} + \begin{pmatrix} k+3 \\ k \end{pmatrix} + ... + \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} = ... \end{eqnarray*}$

$\begin{eqnarray*} = \begin{pmatrix} n-1 \\ k+1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n \\ k+1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} \end{eqnarray*}$

Und damit hat sich mein Problem sogut wie in Luft aufgelöst. Aber trotzdem danke für die Hilfe! :]

edit: @Guevara

Zitat:

Original von Guevara
Das hab ich nicht so gemeint. Es soll nicht die summe aller Kombinationen zusammen gezählt werden.
z.B. 5 über k, und ich will nur die Summe von k= 0,1,2,3 und das in einer Formel.

Wenn ich das jetzt richtig verstanden habe, dann willst du folgendes:

$\begin{eqnarray*} \sum_{k=0}^z~\begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

mit $\begin{eqnarray*} z < n \end{eqnarray*}$

Hab ich das jetzt richtig verstanden??

edit: @Tmc
Deine Frage wurde hierhin abgetrennt.

Neue Frage »

Antworten »

Summe von Binomialkoeffizienten

Verwandte Themen