Binomialkoeffizient und Indextransformation

29.10.2012, 13:21

johnB128

Binomialkoeffizient und Indextransformation

Meine Frage:
Hi,

Ich habe folgende Aufgabe(für alle n aus N):
$\begin{eqnarray*} \sum_{j=0}^{n-1}\binom{n}{n-j}=\sum_{k=1}^n\binom nk \end{eqnarray*}$
Bitte Formeln in Latex darstellen!

Ich dachte eigentlich ich hätte gut aufgelöst, aber irgendwie kann es nicht sein... meine Ideen dazu:

Meine Ideen:
1. Man sieht schon das es gleich sein muss, da auf der rechten Seite immer herauskommt: (1 über n) + (2 über n) + ... + (n über n).
Auf der linken Seite hingegen genau das gleiche, nur von "Hinten nach vorne".

Ich habe also erst einmal eine Indextransformation ausgeführt, nämlich:
SIGMA j=0 n-1 (n über n-j) = SIGMA n-1 k=0 (n+1 über k+1)
Und dann weiter aufgelöst...

Am Ende kommt bei mir, leider, (j+1)! = (n+1)!
heraus... Ahja: Nach der Transformation habe ich beide Laufindexe gleich benannt, also mit "j".

29.10.2012, 16:42

Mystic

Auf diesen Beitrag antworten »

RE: Binomialkoeffizient und Indextransformation
Du kannst das z.B. so lösen, indem du folgende zwei Formeln verwendest:

1. $\begin{eqnarray*} \binom n{n-j}=\binom nj \end{eqnarray*}$
2. $\begin{eqnarray*} \binom n0= \binom nn \end{eqnarray*}$

29.10.2012, 16:44

HAL 9000

Auf diesen Beitrag antworten »

Wenn ich das richig sehe, benötigt man hier nicht mal die Binomialkoeffizientensymmetrie, sondern das ganze ist eine simple Indextransformation $\begin{eqnarray*} k=n-j \end{eqnarray*}$ .

Du hast dich ja hier

Zitat:

Original von johnB128
1. Man sieht schon das es gleich sein muss, da auf der rechten Seite immer herauskommt: (1 über n) + (2 über n) + ... + (n über n).
Auf der linken Seite hingegen genau das gleiche, nur von "Hinten nach vorne".

schon entsprechend geäußert - wo ist also eigentlich noch das Problem? verwirrt

30.10.2012, 15:23

johnB128

Auf diesen Beitrag antworten »

Vielen Dank @ Mystic,
bin so auf die Lösung gekommen :-)

Mein Problem war es, dass ich einfach alles (also alle n über k's)
ausgeschrieben habe und dann nicht wusste, wie ich weiter
verfahren muss. Diese Kniffe/Tricks/Mathematische Auge ist bei mir noch
nicht sooo gut, dass ich gesehen habe, dass ich auf beiden Seiten 1 addieren
kann und diese auch als (n über 0) bzw. (n über n) schreiben kann.

Danke.
-------------------------------------------------------------------------------

Ich habe noch diese letzte Aufgabe zu dem Thema: Siehe Dateianhang.

Ich habe diesmal versucht, mir erst einmal klar zu machen, was die linke bzw. rechte Seite macht.
Mithilfe von Zahlen... Hatte beispielsweise n=2 gesetzt (und auch n=3)
Links kommt bei mir dann mit n=2 heraus: 7
Und rechts: 5

Ein ungleiches Ergebnis erhielt ich auch für n=3. Also dachte ich, die
Gleichung sei falsch.

ABER: Wolfram Alpha ergibt True... nur warum!? oO

Zu meiner Rechnung mit n=2:
Links: SIGMA von 0 bis 2, dh. also: (3 über 0)+(3 über 1)+(3 über 2) = 1+3+3 = 7
Rechts: SIGMA von 1 bis 1, dh. also: (1 über 1) = 1 * 2 = 2 + 3 = 5

Wo ist mein Fehler?!

30.10.2012, 15:34

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von johnB128
Wo ist mein Fehler?!

Der Fehler liegt sicher nicht in deiner obigen Rechnung, sondern woanders, z.B. ein Abschreibfehler der Angabe...

Jedenfalls solltst du immer im Kopf haben, dass die Summe aller Binomialkoeffizienten in der n-ten Reihe des Pascalschen Dreiecks gerade $\begin{eqnarray*} 2^n \end{eqnarray*}$ ergibt (Achtung: Nummerierung der Reihen beginnt bei 0.) Damit kann man dann die beiden Seiten der Gleichung leicht berechnen und auch sehen, dass die verschieden sind...

Edit: Stopp, ist alles Unsinn, die Formel stimmt und du hast dich auf der rechten Seite verrechnet...

30.10.2012, 15:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Damit kann man dann die beiden Seiten der Gleichung leicht berechnen und auch sehen, dass die verschieden sind...

Tatsächlich? Also ich sehe links $\begin{eqnarray*} 2^{n+1}-1 \end{eqnarray*}$ und rechts $\begin{eqnarray*} 3+2(2^n-2) \end{eqnarray*}$ , sieht ziemlich gleich aus, zumindest für $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ .

30.10.2012, 16:16

johnB128

Auf diesen Beitrag antworten »

Danke vorest schonmal für eure Beiträge...

Jedoch, ausgehend davon das die Gleichung stimmt, verstehe ich nicht,
wo ein Fehler in meiner (rechten)Rechnung sein soll oO

30.10.2012, 16:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von johnB128
Rechts: SIGMA von 1 bis 1, dh. also: (1 über 1) = 1 * 2 = 2 + 3 = 5

Für $\begin{eqnarray*} n=2 \end{eqnarray*}$ ist

$\begin{eqnarray*} 3+ 2\sum_{r=1}^{n-1} \binom{n}{r} = 3+ 2\sum_{r=1}^{1} \binom{2}{r} = 3 + 2\cdot 2 = 7 \end{eqnarray*}$

30.10.2012, 16:34

johnB128

Auf diesen Beitrag antworten »

Danke,

kein Plan was mich da geritten hat...
(2 über 1) ist natürlich 2 und nicht 1 .... argh.. zuviel Mathe gemacht heute.

Okay, durch Einsetzen komme ich nun auf die Lösung, aber ich rechne und stelle
nun wild umher, und weiß nicht, welchen Kniff (wie oben in der Aufgabe) ich
gebrauchen muss, um zu zeigen, dass es wirklich gleich ist... Jemand ein Tipp??

30.10.2012, 16:37

HAL 9000

Auf diesen Beitrag antworten »

Den Tipp hat Mystic schon genannt:

Zitat:

Original von Mystic
Jedenfalls solltst du immer im Kopf haben, dass die Summe aller Binomialkoeffizienten in der n-ten Reihe des Pascalschen Dreiecks gerade $\begin{eqnarray*} 2^n \end{eqnarray*}$ ergibt (Achtung: Nummerierung der Reihen beginnt bei 0.)

Was im vorliegenden Fall $\begin{eqnarray*} \sum_{r=0}^{n+1} \binom{n+1}{r} = 2^{n+1} \end{eqnarray*}$ sowie $\begin{eqnarray*} \sum_{r=0}^n \binom{n}{r} = 2^n \end{eqnarray*}$ bedeutet. Für die paar $\begin{eqnarray*} r \end{eqnarray*}$ , die links sowie rechts in der Summe "fehlen", musst du die zugehörigen Summanden eben von diesen Zweierpotenzen subtrahieren.

30.10.2012, 17:31

JohnB128

Auf diesen Beitrag antworten »

Hammer, danke! :-) Echt super das Forum.

Also ich habe es mal so notiert:

SIGMA r=1 bis n-1 von (n über r) =
(n über 1) + (n über 2) + ... + (n über n-1) =
2^n - (n über 0) - (n über n) =
2^n - 2

smile

Nur bei der linken Seite, verstehe ich leider nicht, woher die -1 kommt?

SIGMA r=0 bis n von (n über r) =
(n+1 über 0) + (n+1 über 1) + ... (n+1 über n) =
2^n ... aber woher kommt da da die -1?

Rest ist klar... die Gleichung die Du gepostet hast ergibt, dann natürlich
2^n - 1 = 3 + 2(2^n - 2)
2^n - 1 = 2^n - 1

30.10.2012, 17:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von JohnB128
Nur bei der linken Seite, verstehe ich leider nicht, woher die -1 kommt?

Ich sage nur: $\begin{eqnarray*} \binom{n+1}{n+1} \end{eqnarray*}$

In dem Zusammenhang sehe ich, dass du zur Schlamperei neigst - hier und da mal was "Unwichtiges" weglassen, hmm?

Zitat:

Original von JohnB128 (ergänzt)
SIGMA r=0 bis n von ((n+1) über r) =
(n+1 über 0) + (n+1 über 1) + ... (n+1 über n) =
2^(n+1) ... aber woher kommt da da die -1?

30.10.2012, 18:15

JohnB128

Auf diesen Beitrag antworten »

Achso, jetzt verstehe ich. Vielen Dank für die Hilfe :-)

Und ja, ich habe mal das n+1 vergessen... jeder macht mal einen
Fehler ^^

30.10.2012, 18:16

HAL 9000

Auf diesen Beitrag antworten »

Ja, einen. Aber wenn es fünf oder sechs in derselben kleinen Aufgabe sind...

Neue Frage »

Antworten »

Binomialkoeffizient und Indextransformation

Verwandte Themen