Gleichung induktiv beweisen

15.04.2006, 18:02

creasy

Gleichung induktiv beweisen

Hallo

Bräuchte ein wenig Hilfe um folgende Gleichung zu beweisen:

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

Ich wollte induktiv vorgehen, allerdings hänge ich ein wenig beim Induktionsschluss. Komme nicht auf die richtige Idee.
Kann mir vielleicht jemand weiterhelfen?! Gott

MfG
creasy

15.04.2006, 18:06

mercany

Auf diesen Beitrag antworten »

Sicher kann man da helfen.
Allerdings nur, wenn du auch zeigst, was du bis jetzt schon gemacht hast. smile

Gruß, mercany

15.04.2006, 18:51

creasy

Auf diesen Beitrag antworten »

Klar:
I-Anfang: n=0 gilt!
Also sei n>0:
I-Voraussetzung: $\begin{eqnarray*} \sum_{k=0}^n~ {n \choose k}^{2} = {2n \choose n} \end{eqnarray*}$
I-Schritt n --> n+1: $\begin{eqnarray*} \sum_{k=0}^{n+1}~ {n+1 \choose k}^{2} = {2(n+1) \choose n+1} \end{eqnarray*}$
Jetzt habe ich halt ein wenig mit den Regeln über den Binomialkoeff. rumgespielt, finde aber keinen Weg den Schritt zu beweisen!

15.04.2006, 18:58

mercany

Auf diesen Beitrag antworten »

Die Idee mit dem Binomialkoeffizienten ist ganz gut!
Was hast du da denn probiert?

Gruß, mercany

15.04.2006, 19:06

creasy

Auf diesen Beitrag antworten »

Alles mögliche. Ich will ja die Summe so verändern, dass ich die IV anwenden kann. Habe also mittels der Regeln versucht die Summe passend umzuformen, allerdings ohne Erfolg bis jetzt.

edit: natürlich nicht alles mögliche, sonst hätte ich ja schon die Lösung smile

16.04.2006, 00:10

mercany

Auf diesen Beitrag antworten »

Kennst du das Additionstheorem der Binomialkoeffizienten?
Mit dem geht es ganz einfach.

Für alle $\begin{eqnarray*} s,t \in \mathbb C \end{eqnarray*}$ und $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt

$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix} = \begin{pmatrix} s+t \\ n \end{pmatrix} \end{eqnarray*}$

Und daraus folgt deine Behauptung dann schon direkt!

Gruß, mercany

16.04.2006, 01:06

creasy

Auf diesen Beitrag antworten »

Man findet ja so einiges über Binomialkoeff. aber dass kannte ich noch nicht!
Hättest du vielleicht auch den Beweis dafür?!
THX
Gruß creasy

16.04.2006, 01:07

mercany

Auf diesen Beitrag antworten »

Zitat:

Original von creasy
Man findet ja so einiges über Binomialkoeff. aber dass kannte ich noch nicht!
Hättest du vielleicht auch den Beweis dafür?!
THX
Gruß creasy

Ja, habe ich!
Aber erst morgen... für heute ist bei mir Schluss.

Gute Nacht. Wink

16.04.2006, 11:37

creasy

Auf diesen Beitrag antworten »

Super, danke

16.04.2006, 19:21

mercany

Auf diesen Beitrag antworten »

Hallo.

Der Beweis setzt den Identitätssatz vorraus, welcher besagt:

Stimmen die Werte der Polynome

$\begin{eqnarray*} f(x) = a_nx^n + ... a_1x + a_0 \end{eqnarray*}$
$\begin{eqnarray*} g(x) = b_nx^n + ... b_1x + b_0 \end{eqnarray*}$

an $\begin{eqnarray*} n+1 \end{eqnarray*}$ Stellen überein, so gilt $\begin{eqnarray*} a_k = b_k \end{eqnarray*}$ für $\begin{eqnarray*} k = 0,...,n \end{eqnarray*}$ und somit $\begin{eqnarray*} f(x) = g(x) \end{eqnarray*}$ für alle $\begin{eqnarray*} x \in \mathbb C \end{eqnarray*}$

Beweis (1):

Das Additionstheorem gilt, falls $\begin{eqnarray*} s,t \in \mathbb N \end{eqnarray*}$ .
Dafür stellen wir $\begin{eqnarray*} (1+x)^{s+t} \end{eqnarray*}$ auf zwei Weisen dar:

$\begin{eqnarray*} (1+x)^{s+t} = \sum_{n=0}^{s+t}~\begin{pmatrix} s+t \\ n \end{pmatrix} x^n \end{eqnarray*}$

$\begin{eqnarray*} (1+x)^s \cdot (1+x)^t &=& \sum_{k=0}^s~ \begin{pmatrix} s \\ k \end{pmatrix} x^k \cdot \sum_{q=0}^t~ \begin{pmatrix} t \\ k \end{pmatrix} \cdot x^q \\ &=& \sum_{n=0}^{s+t}~\left(\sum_{k=0}^{n}~ \begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix}\right) x^n \end{eqnarray*}$

Aus dem Koeffizientenvergleich erfolgt jetzt sofort die Behauptung.

Jetzt zeigen wir, dass es auch für $\begin{eqnarray*} s,t \in \mathbb C \end{eqnarray*}$ gilt.

(2)
Behauptung: Das Theorem gilt, falls $\begin{eqnarray*} t \in \mathbb N \end{eqnarray*}$
Beweis: Seit $\begin{eqnarray*} t \in N \end{eqnarray*}$ fest gewählt so stellen beide Seiten von

$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix} = \begin{pmatrix} s+t \\ n \end{pmatrix} \end{eqnarray*}$

Polynome in $\begin{eqnarray*} s \end{eqnarray*}$ dar. Nach (1) stimmen diese für alle $\begin{eqnarray*} s \in \mathbb N \end{eqnarray*}$ überein und nach dem Identitätssatz also für alle $\begin{eqnarray*} s \in \mathbb C \end{eqnarray*}$

(3)
Benauptung: Das Theorem gilt!
Beweis: Sei $\begin{eqnarray*} s \in \mathbb C \end{eqnarray*}$ fest, so stellen beide Seiten von

$\begin{eqnarray*} \sum_{k=0}^n~\begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix} = \begin{pmatrix} s+t \\ n \end{pmatrix} \end{eqnarray*}$

Polynome in $\begin{eqnarray*} t \end{eqnarray*}$ dar. Nach (2) stimmen diese für alle $\begin{eqnarray*} t \in \mathbb N \end{eqnarray*}$ und nach dem Identitätssatz auch für alle $\begin{eqnarray*} t \in \mathbb C \end{eqnarray*}$

Gruß, mercany

17.04.2006, 20:48

Sephiroth

Auf diesen Beitrag antworten »

Zitat:

Original von mercany

$\begin{eqnarray*} (1+x)^s \cdot (1+x)^t &=& \sum_{k=0}^s~ \begin{pmatrix} s \\ k \end{pmatrix} x^k \cdot \sum_{q=0}^t~ \begin{pmatrix} t \\ k \end{pmatrix} \cdot x^q \\ &=& \sum_{n=0}^{s+t}~\left(\sum_{n=0}^{s+t}~ \begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix}\right) x^n \end{eqnarray*}$

kann es sein, dass es eher so heißen soll?

$\begin{eqnarray*} (1+x)^s \cdot (1+x)^t &=& \sum_{k=0}^s~ \begin{pmatrix} s \\ k \end{pmatrix} x^k \cdot \sum_{q=0}^t~ \begin{pmatrix} t \\ q \end{pmatrix} \cdot x^q \\ &=& \sum_{n=0}^{s+t}~\left(\sum_{k=0}^{n}~ \begin{pmatrix} s \\ k \end{pmatrix} \begin{pmatrix} t \\ n-k \end{pmatrix}\right) x^n \end{eqnarray*}$

18.04.2006, 12:13

mercany

Auf diesen Beitrag antworten »

Ja, da hast du recht!
Danke schön für den Hinweis, ich hab es oben verbessert.

Gruß, mercany

Neue Frage »

Antworten »

Gleichung induktiv beweisen

Verwandte Themen