Vollst. Induktion (Aufgabe)

06.04.2009, 17:12

Nightfall

Vollst. Induktion (Aufgabe)

Heyho!
Es geht um folgende Aufgabe (Otto Forster: Analysis I):

Zitat:

Für eine reele Zahl x und eine natürliche Zahl k werde definiert: $\begin{eqnarray*} \binom xk:=\prod_{j=1}^{n}\frac{x-j+1}{j}=\frac{x(x-1)*\ldots*(x-k+1)}{k!} \end{eqnarray*}$ , insbesondere $\begin{eqnarray*} \binom x0=1 \end{eqnarray*}$ . Man beweise für alle reelen Zahlen x, y und alle natürlichen Zahlen n $\begin{eqnarray*} \binom{x+y}n=\sum_{k=0}^n\binom x{n-k}\binom yk \end{eqnarray*}$ .

Naja, sah ja anfangs "easy" aus, aber dann... also hier erstmal was ich gemacht habe:

n=0: $\begin{eqnarray*} \binom {x+y}0=1=\sum_ {k=0}^0\binom x0\binom y0 \end{eqnarray*}$ (läuft...)
n nach n+1: $\begin{eqnarray*} \sum_{k=0}^{n+1}\binom x{n-k}\binom yk=\sum_{k=0}^{n}\binom x{n-k}\binom yk+\binom x{n-(n+1)}\binom y{n+1} \end{eqnarray*}$
[IV] $\begin{eqnarray*} =\binom {x+y}n+\binom x{-1}\binom x{n+1} \end{eqnarray*}$

so und hier ist nun "Feierabend". das k in $\begin{eqnarray*} \binom x{-1} \end{eqnarray*}$ ist -1 also nicht aus $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ . Also ist das gar nicht definiert und ich steh im Wald... *grml* Naja, ich glaub ja, dass ich was übersehen habe, aber ich seh's nicht. Vllt könnt ihr mir weiterhelfen?!

Danke und Gruß,
Nightfall

06.04.2009, 18:08

Auf diesen Beitrag antworten »

Nicht nur die Anzahl der Summanden ändert sich, auch die Summanden selbst! Die rechte Seite deiner Behauptung für n+1 lautet NICHT $\begin{eqnarray*} \sum_{k=0}^{n+1} \binom{x}{n-k}\binom{y}{k} \end{eqnarray*}$ , sondern $\begin{eqnarray*} \sum_{k=0}^{n+1} \binom{x}{n+1-k}\binom{y}{k} \end{eqnarray*}$ .

P.S.: Noch ein wenig Inspiration.

06.04.2009, 18:30

Nightfall

Auf diesen Beitrag antworten »

Klassischer Fall von Hammer

D'Oh! Danke dir!

07.04.2009, 11:24

Nightfall

Auf diesen Beitrag antworten »

Die Rechnung deiner Inspiration habe ich verstanden, aber dann hört's mit dem Inspirieren auch schon auf. Wo kommt das $\begin{eqnarray*} k \end{eqnarray*}$ vor der Summe her? Und vor allem wie und warum wende ich das im Induktionsschritt an? Kannst du bitte versuchen mich noch ein wenig mehr zu "erleuchten"?! Ich steh irgendwie immernoch im Wald Augenzwinkern

07.04.2009, 11:44

klarsoweit

Auf diesen Beitrag antworten »

Du mußt schon etwas konkreter werden. Welches k vor welcher Summe?

07.04.2009, 11:46

Nightfall

Auf diesen Beitrag antworten »

Es geht um den Link zu einam anderen Beitrag den Arthur gepostet hat...

Zitat:

Original von Arthur Dent
Es geht um den Beweis von

$\begin{eqnarray*} \sum_{j=0}^{k} \binom{x}{k-j} \binom{y}{j} = \binom{x+y}{k}\qquad (*) \end{eqnarray*}$

für beliebige reelle $\begin{eqnarray*} x,y \end{eqnarray*}$ und natürliche $\begin{eqnarray*} k \end{eqnarray*}$ durch Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ (dazu braucht man natürlich die bereits angesprochene allgemeinere Definition des Binomialkoeffizienten). Sehr oft wird (*) nur für natürliche Zahlen $\begin{eqnarray*} x,y \end{eqnarray*}$ bewiesen, was für den vorliegenden Fall nichts nützt.

Dabei ist der Nachweis für beliebige reelle Zahlen $\begin{eqnarray*} x,y \end{eqnarray*}$ gar nicht schwer, wenn man im Induktionsschritt den richtigen Hebel ansetzt:

$\begin{eqnarray*} k\sum_{j=0}^{k} \binom{x}{k-j} \binom{y}{j} &=& \sum_{j=0}^{k} (k-j)\binom{x}{k-j} \binom{y}{j} + \sum_{j=0}^{k} \binom{x}{k-j} j\binom{y}{j} = \cdots \end{eqnarray*}$

Konkret meine ich also das erste $\begin{eqnarray*} k \end{eqnarray*}$ vor dem ersten Summenzeichen.

07.04.2009, 12:09

klarsoweit

Auf diesen Beitrag antworten »

Woher das k vor der Summe kommt, ist unerheblich. ArthurDent betrachtet einfach den Ausdruck $\begin{eqnarray*} k\sum_{j=0}^{k} \binom{x}{k-j} \binom{y}{j} \end{eqnarray*}$ und formt diesen weiter um.

07.04.2009, 14:34

Nightfall

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} k\sum_{j=0}^{k} \binom{x}{k-j} \binom{y}{j} &=& \sum_{j=0}^{k} (k-j)\binom{x}{k-j} \binom{y}{j} + \sum_{j=0}^{k} \binom{x}{k-j} j\binom{y}{j} = \cdots \end{eqnarray*}$

Ok, dann mache ich da einfach mal weiter, obwohl ich immer noch nicht genau weiß worauf das hinauslaufen soll - was soll's. Also zunächst fällt mir jetzt auf, dass, wenn ich die Binominalkoeffizienten auflöse, ich jeweils einen letzen Faktor einer "Fakultät" wegkürzen kann:
$\begin{eqnarray*} =\sum_{j=0}^k(k-j)*\frac{x!}{(k-j)!(x-k+j)!}*\frac{y!}{j!(y-j)!}+\sum_{j=0}^k\frac{x!}{(k-j)!(x-k+j)!}*j*\frac{y!}{j!(y-j)!}\\=\sum_{j=0}^k\frac{x!}{(k-j-1)!(x-k+j)!}*\frac{y!}{j!(y-j)!}+\sum_{j=0}^k\frac{x!}{(k-j)!(x-k+j)!}*j*\frac{y!}{(j-1)!(y-j)!} \end{eqnarray*}$

Und dann ist bei mir Feierabend. Hm, keine Plan wie es weitergehen soll - wie wär's mit einem kleinen Tipp Augenzwinkern

07.04.2009, 18:09

Auf diesen Beitrag antworten »

Zitat:

Original von Nightfall
$\begin{eqnarray*} =\sum_{j=0}^k(k-j)*\frac{x!}{(k-j)!(x-k+j)!}*\frac{y!}{j!(y-j)!}+\sum_{j=0}^k\frac{x!}{(k-j)!(x-k+j)!}*j*\frac{y!}{j!(y-j)!}\\=\sum_{j=0}^k\frac{x!}{(k-j-1)!(x-k+j)!}*\frac{y!}{j!(y-j)!}+\sum_{j=0}^k\frac{x!}{(k-j)!(x-k+j)!}*\frac{y!}{(j-1)!(y-j)!} \end{eqnarray*}$

Das stimmt so nicht ganz: Für j=k kannst du in der ersten Summe NICHT kürzen, genausowenig wie für j=0 in der zweiten Summe! Glücklicherweise sind beide angesprochenen Summanden gleich Null, also lässt man sie gleich weg:

$\begin{eqnarray*} &=& \sum_{j=0}^{k-1}(k-j) \frac{x!}{(k-j)!(x-k+j)!} \cdot \binom{y}{j}+\sum_{j=1}^k \binom{x}{k-j} \cdot j\frac{y!}{j!(y-j)!}\\ &=& \sum_{j=0}^{k-1}\frac{x!}{(k-j-1)!(x-k+j)!} \cdot \binom{y}{j}+\sum_{j=1}^k \binom{x}{k-j} \cdot \frac{y!}{(j-1)!(y-j)!} \end{eqnarray*}$

Und jetzt jeweils im Zähler passend was abspalten:

$\begin{eqnarray*} &=& x \cdot \sum_{j=0}^{k-1}\frac{(x-1)!}{(k-j-1)!(x-k+j)!} \cdot \binom{y}{j}+y\cdot \sum_{j=1}^k \binom{x}{k-j} \cdot \frac{(y-1)!}{(j-1)!(y-j)!} \\ &=& x \cdot \sum_{j=0}^{k-1} \binom{x-1}{k-1-j} \cdot \binom{y}{j}+y\cdot \sum_{j=1}^k \binom{x}{k-j} \cdot \binom{y-1}{j-1} \end{eqnarray*}$ .

Das sollte jetzt weit mehr als die halbe Miete sein...

07.04.2009, 18:58

Nightfall

Auf diesen Beitrag antworten »

Oh, super! Danke dir! Jetzt seh ich wo's hinlaufen soll/kann! Danke für die Mühe!

Gruß,Nightfall

07.04.2009, 19:06

Auf diesen Beitrag antworten »

Ich sehe gerade, dass ich deinen Unsinn unkritisch mitgemacht habe: Hammer

Sind $\begin{eqnarray*} x,y \end{eqnarray*}$ beliebig reell, dann darfst du die Fakultätsschreibweise in Teilen so gar nicht verwenden! Die Beweisidee ist dennoch richtig, wenn du es etwas umschreibst, so mit

$\begin{eqnarray*} (k-j) \cdot \binom{x}{k-j} = x\cdot \binom{x-1}{k-1-j} \end{eqnarray*}$ und $\begin{eqnarray*} j \cdot \binom{y}{j} = y\cdot \binom{y-1}{j-1} \end{eqnarray*}$

basierend auf der allgemeineren Definition des Binomialkoeffizienten.

08.04.2009, 11:20

Nightfall

Auf diesen Beitrag antworten »

Meinen Unsinn?? *empörtbin* Augenzwinkern

Aber du hast recht, das hat mir gestern Abend ein Komilitone auch gesagt... Danke für deinen Hinweis! Gruß, Nightfall

Neue Frage »

Antworten »

Vollst. Induktion (Aufgabe)

Verwandte Themen