Binomialkoeffzient - Beweis

24.12.2006, 13:09

Sila85

Auf diesen Beitrag antworten »

Binomialkoeffzient - Beweis

Zeigen Sie für n € N:

$\begin{eqnarray*} \sum_{k=0}^n \end{eqnarray*}$ (n über k)² = (2n über n)

Hinweis: Vergleichen Sie die x^n-Koeffizienten von (1+x)^n*(1+x)^n und (1+x)^2n

Also ich habs mit vollständiger Induktion probiert. Induktionsannahme hat gestimmt. Doch beim Induktionsschritt komme ich hier nicht weiter und würde mich freuen wenn eine schnelle Antwort käme...

Sum(binomial(n+1,k)²)k=0,n+1 = Sum(binomial(n+1,k)²)k=0,n + ... ?

vielen Dank!
sila

edit: ich habe schon gelesen dass man dies mit der sogenannten Vandermondeschen Identität beweisen kann...aber ist das überhaupt möglich? muss man denn dann nicht auch noch die Vandermondesche Identität beweisen um dies anwenden zu dürfen?
vielen dank im voraus!

24.12.2006, 13:57

therisen

Auf diesen Beitrag antworten »

Hallo,

warum probierst du vollständige Induktion, wenn extra ein Hinweis dabei steht, wie du es machen sollst?

Es ist $\begin{eqnarray*} (1+x)^n(1+x)^n = \left(\sum_{k=0}^n {n\choose k} x^k\right) \cdot \left(\sum_{k=0}^n {n\choose k} x^k \right) = \sum_{k=0}^{2n} {2n\choose k} x^k = (1+x)^{2n} \end{eqnarray*}$ .

Das liefert insbesondere
$\begin{eqnarray*} {n\choose 0}{n\choose n}x^n + {n\choose 1}{n\choose n-1}x^n + \dots + {n\choose n}{n\choose 0}x^n = \sum_{k=0}^n {n\choose k}{n\choose n-k} x^n = {2n\choose n} x^n \end{eqnarray*}$

Mit $\begin{eqnarray*} {n\choose k}{n\choose n-k} = {n\choose k}^2 \end{eqnarray*}$ folgt nach Koeffizientenvergleich die Behauptung.

Gruß, therisen

24.12.2006, 14:36

Sila85

Auf diesen Beitrag antworten »

Hallo therisen,
erst mal vielen dank dass du das alles so schön hingeschrieben hast. jedoch verstehe ich einige dinge nicht so ganz.

Wie komme beim Hinweis bei der Multiplikation von den beiden Summenschreibweisen auf:

(Summe(Binomial(2n,k)k=0,n) x^k ??? und von dem Term auf (1+x)^2n ???

Dann schreibst du dass das insbesondere ... liefert. verwirrt

verwirrt

Also auch hier habe ich Schwierigkeiten dies nachzuvollziehen! unglücklich

unglücklich

Würde mich freuen wenn du vielleicht noch kurz die einzelnen Schritte erklären könntest bzw nur stichwortartig definierst...

vielen dank

P.S.: Wie schreibt man denn die Summen und Binomialkoeffizienten hin? Mit dem Formeleditor hab ichs schon probiert...haut beispielsweise bei Sigma"k=0 bis (n+1)" nicht hin...
auch dafür merci im voraus

24.12.2006, 18:54

Mathespezialschüler

Auf diesen Beitrag antworten »

Wir haben so einen tollen Formeleditor, da siehst du das. Sollte eigentlich alles klar sein. Was verstehst du denn an dem Editor nicht?
Therisen hat zweimal den binomischen Satz angewendet:

1. $\begin{eqnarray*} (1+x)^n=\sum_{k=0}^n~{n\choose k}x^k \end{eqnarray*}$

2. $\begin{eqnarray*} (1+x)^{2n}=\sum_{k=0}^{2n}~{2n\choose k}x^k \end{eqnarray*}$ .

Und dann hat er einfach bei

$\begin{eqnarray*} (1+x)^{2n}=(1+x)^n\cdot (1+x)^n \end{eqnarray*}$

auf beiden Seiten eingesetzt. Das Produkt auf der rechten Seite

$\begin{eqnarray*} \left(\sum_{k=0}^n~{n\choose k}x^k\right)\cdot\left(\sum_{k=0}^n~{n\choose k}x^k\right) \end{eqnarray*}$

muss man dann natürlich noch ausrechnen. Das ist dann die nächste Zeile. Und dann kann man einen Koeffizientenvergleich machen.

Gruß MSS

25.12.2006, 09:36

Sila85

Auf diesen Beitrag antworten »

Alles klar! hatte nen denkfehler

vielen dank euch beiden Gott

Gott

schöne feiertage!

gruß sila

07.01.2007, 19:56

donvito

Auf diesen Beitrag antworten »

Du stududierst wohl auch in Freiburg Informatik, oder?

Sitze auch grade an dem Matheblatt *ächz*

Was ich nicht verstehe ist folgendes:

wo kommt denn immer dieses $\begin{eqnarray*} x^k \end{eqnarray*}$ her? Das steht in meiner Aufgabe (dieselbe wie oben) nämlich nirgends...

Anzeige

08.01.2007, 10:26

klarsoweit

Auf diesen Beitrag antworten »

Meinst du das x^k in $\begin{eqnarray*} (1+x)^n=\sum_{k=0}^n~{n\choose k}x^k \end{eqnarray*}$ ?
Wenn ja, dann schau dir nochmal den binomischen Lehrsatz an. Augenzwinkern

Augenzwinkern

01.11.2013, 21:59

Kääsee

Auf diesen Beitrag antworten »

Hey,
das Thema ist jetzt zwar schon etwas länger her, aber ich verstehe nicht, wie man auf den Punkt
"das liefert insbesondere" kommt. Vielleicht stehe ich nur wieder auf dem Schlauch, aber mag mir vielleicht jemand einen Denkanstoß geben?

LG

01.11.2013, 22:11

MatheIstLustig

Auf diesen Beitrag antworten »

Wenn Du den Thread aufmerksam gelesen hast, steht oben schon die Antwort:
Berechne

$\begin{eqnarray*} \left(\sum_{k=0}^n~{n\choose k}x^k\right)\cdot\left(\sum_{k=0}^n~{n\choose k}x^k\right) \end{eqnarray*}$

Von dem Ergebnis ist für den Beweis nur relevant, was als Koeffizient vor $\begin{eqnarray*} x^n \end{eqnarray*}$ steht.

01.11.2013, 22:43

Kääsee

Auf diesen Beitrag antworten »

ich glaube, ich bin echt zu doof traurig

traurig

$\begin{eqnarray*} \left({n\choose 0}+ {n\choose 1}x +{n\choose 2}x^2 + \dots + {n\choose n}x^n \right) \cdot \left({n\choose 0}+ {n\choose 1}x +{n\choose 2}x^2 + \dots + {n\choose n}x^n \right)\\= {n\choose 0}{n\choose 0}+ {n\choose 0}{n\choose 1}x +{n\choose 0}{n\choose 2}x^2 + \dots + {n\choose 0}{n\choose n}x^n <br /> \\+{n\choose 1}{n\choose 0}x+ {n\choose 1}{n\choose 1}x^2 +{n\choose 1}{n\choose 2}x^3 + \dots + {n\choose 1}{n\choose n}x^{n+1}+ \dots <br /> \\+{n\choose n}{n\choose 0}x^n+ {n\choose n}{n\choose 1}x^{n+1} +{n\choose n}{n\choose 2}x^{n+2} + \dots + {n\choose n}{n\choose n}x^{2n} \end{eqnarray*}$

edit:

Zitat:

Original von MatheIstLustig

Von dem Ergebnis ist für den Beweis nur relevant, was als Koeffizient vor $\begin{eqnarray*} x^n \end{eqnarray*}$ steht.

Und was passiert mit dem Rest?!!

01.11.2013, 22:54

MatheIstLustig

Auf diesen Beitrag antworten »

überflüssig, da ich nur die Koeffizienten vor $\begin{eqnarray*} x^n \end{eqnarray*}$ vergleichen will.
Du brauchst nur die entsprechenden Teile des Produktes auszurechnen
siehe auch oben:

$\begin{eqnarray*} {n\choose 0}{n\choose n}x^n + {n\choose 1}{n\choose n-1}x^n + \dots + {n\choose n}{n\choose 0}x^n \end{eqnarray*}$

01.11.2013, 23:05

Kääsee

Auf diesen Beitrag antworten »

Tut mir wirklich Leid, ich kann das echt gerade nicht nachvollziehen verwirrt

verwirrt

Vielleicht ist es auch einfach zu spät. Ich verstehe schon, dass die Koeffizienten vor dem x^n diese sein müssen, aber warum man die anderen gar nicht betrachtet...?
Außerdem verstehe ich nicht, wie man auf das hier kommt.
$\begin{eqnarray*} \sum_{k=0}^n {n\choose k}{n\choose n-k} x^n = {2n\choose n} x^n \end{eqnarray*}$
Ich fühle mich überfordert traurig

traurig

01.11.2013, 23:12

MatheIstLustig

Auf diesen Beitrag antworten »

linke Seite ist x ausklammern und die ganzen Binomialkoeffizienten als Summe schreiben.
Rechte Seite ergibt sich, wenn aus der Summe $\begin{eqnarray*} \sum_{k=0}^{2n} {2n\choose k} x^k \end{eqnarray*}$ auch nur der Teil mit $\begin{eqnarray*} x^n \end{eqnarray*}$ betrachtet wird.
Da das Produkt der Summen und diese Summe gleich sind, muss vor jedem x der gleiche Koeffizient stehen.
Für den Beweis der Behauptung braucht man nur deie gleichen Koeffizienten vor $\begin{eqnarray*} x^n. \end{eqnarray*}$

01.11.2013, 23:32

Kääsee

Auf diesen Beitrag antworten »

Boaar, ich glaube, ich breche mein Studium ab unglücklich

unglücklich

Wo die linke Seite herkam, hatte ich schon verstanden. Ich wusste nur nicht, wie man auf die rechte Seite kommt. Aber genau darin liegt ja mein Problem. Dieses komisch "nur die Koeffizienten vor x^n betrachten"!

Zitat:

Original von MatheIstLustig
Da das Produkt der Summen und diese Summe gleich sind, muss vor jedem x der gleiche Koeffizient stehen.
[/latex]

Kannst du das vielleicht etwas näher erklären? Sorry, wenn ich mich blöd dranstelle.

02.11.2013, 01:21

MatheIstLustig

Auf diesen Beitrag antworten »

Wenn ich deine Frage jezt richtig verstehe:

In der ersten Zeile des Beweises stehen zwei Polynome als Produkt von 2 Summen/ als Summe geschrieben.
Wenn zwei Polynome gleich sind, stimmen sie in jedem Koeffizienten überein. "Das liefert insbesondere" reduziert den Vergleich auf einen einzigen Koeffizienten.

02.11.2013, 12:04

Kääsee

Auf diesen Beitrag antworten »

Oh mein Gott, bin ich so hohl! Na klar! Am besten schieben wir das einfach wirklich auf die Uhrzeit Augenzwinkern

Augenzwinkern

Vielen Dank!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »