Stirlingzahlen erster Art per Induktion beweisen

05.07.2010, 13:43

mathenovize

Stirlingzahlen erster Art per Induktion beweisen

Hallo Forum,

es ist Montag, malwieder. Und ich versauere vor der dritten Aufgaben eines Matheuebungsblattes. Ich bin fuer jeden Tip oder Schubser in die richtige oder "richtigere" Richtung sehr dankbar smile

Also, gegeben ist eine rekursive Definition der Stirlinzahlen erster Art:

$\begin{eqnarray*} s(n,k) = s(n-1,k-1)+(n-1)*s(n-1,k) \end{eqnarray*}$

Sowie folgende hilfreiche Bemerkungen:

$\begin{eqnarray*} \sum_{k=1}^n s(n,k)=n! \end{eqnarray*}$

und

$\begin{eqnarray*} s(n,k) = 0, k=0 \\ 1, k=n \end{eqnarray*}$

Ich soll jetzt folgenden Ausdruck induktiv beweisen:

$\begin{eqnarray*} \sum_{k=0}^n s(n,k) = s(n+1,1) = n! \end{eqnarray*}$

Ich habe das ganze jetzt als zwei Identiaeten interpretiert, also Summe=s(n+1,1) und s(n+1,1)=n!.
Der Induktionsanfang haut auch super hin. Allerdings tue ich mich bei dem Induktionsschluss sehr schwer, weil mir einfach die richtige Idee fehlt. So sieht mein (vermurkster) Ansatz aus:

$\begin{eqnarray*} \sum_{k=0}^{n+1} s((n+1)+1,k) =_{IV} s(n+1,1) + s(n+1,1) =_{IV} n! + n! \end{eqnarray*}$

Dabei habe ich:
- Die Summe auseinandergezogen
- Fuer die enstehende bis n laufende Summe die IV eingesetzt
- Dann fuer beide Teile die zweite Identitaet eingesetzt (s(n+1,1) = n!)

Aber ich muss auf (n+1)! kommen. Und daran scheitere ich.

Wuerde mich ueber einen Tip sehr freuen.

Danke und

Gruesse,
der Mathenovize

05.07.2010, 13:59

Auf diesen Beitrag antworten »

Deine Überlegungen zum Induktionsschritt sind mir schon vom Start weg rätselhaft. unglücklich

Es geht doch um den Schritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ des Induktionsbeweises von $\begin{eqnarray*} \sum_{k=0}^n s(n,k) = n! \end{eqnarray*}$ , oder? Da ist es doch naheliegend, so anzufangen:

$\begin{eqnarray*} \sum_{k=0}^{n+1} s(n+1,k) = s(n+1,0) + \sum_{k=1}^n (s(n,k-1)+n\cdot s(n,k)) + s(n+1,n+1) \end{eqnarray*}$ ,

gemäß rekursiver Definition. Jetzt $\begin{eqnarray*} s(n+1,0)=0 \end{eqnarray*}$ und $\begin{eqnarray*} s(n+1,0)=1 \end{eqnarray*}$ einsetzen, Summe teilen und in erster Summe den Index verschieben

$\begin{eqnarray*} \ldots = 1+ \sum_{k=0}^{n-1} s(n,k)+n\cdot \sum_{k=1}^n s(n,k) \end{eqnarray*}$ ,

der Rest sollte dann klar sein.

---------------------------

Der andere Teil $\begin{eqnarray*} s(n+1,1)=n! \end{eqnarray*}$ ist noch einfacher, da nach Rekursion

$\begin{eqnarray*} s(n+2,1) = s(n+1,0) + (n+1)\cdot s(n+1,1) = (n+1)\cdot s(n+1,1) \end{eqnarray*}$

gilt.

05.07.2010, 14:11

Kühlkiste

Auf diesen Beitrag antworten »

RE: Stirlingzahlen erster Art per Induktion beweisen

Zitat:

Original von mathenovize
Also, gegeben ist eine rekursive Definition der Stirlinzahlen erster Art:

$\begin{eqnarray*} s(n,k) = s(n-1,k-1)+(n-1)*s(n-1,k) \end{eqnarray*}$

Zu einer solchen Rekursion gehören auch die Startwerte dazu.

Zitat:

Original von mathenovize
Sowie folgende hilfreiche Bemerkungen:

$\begin{eqnarray*} \sum_{k=1}^n s(n,k)=n! \end{eqnarray*}$

Das soll doch gerade bewiesen werden - oder... verwirrt

Zitat:

Original von mathenovize
und

$\begin{eqnarray*} s(n,k) = 0, k=0 \\ 1, k=n \end{eqnarray*}$

Ich soll jetzt folgenden Ausdruck induktiv beweisen:

$\begin{eqnarray*} \sum_{k=0}^n s(n,k) = s(n+1,1) = n! \end{eqnarray*}$

Wenn Du Dir die Rekursionsgleichung mal anguckst, dann sollte direkt klar sein, dass $\begin{eqnarray*} s(n+1,1)=n! \end{eqnarray*}$ . Sonst kannst Du das auch mit ner fast trivialen Induktion zeigen.

Zitat:

Original von mathenovize
Ich habe das ganze jetzt als zwei Identiaeten interpretiert, also Summe=s(n+1,1) und s(n+1,1)=n!.

Zitat:

Original von mathenovize
So sieht mein Ansatz aus:

$\begin{eqnarray*} \sum_{k=0}^{n+1} s((n+1)+1,k) =_{IV} s(n+1,1) + s(n+1,1) =_{IV} n! + n! \end{eqnarray*}$

Hier geht's aber ziemlich den Bach runter...

Betrachte:

$\begin{eqnarray*} \sum_{k=0}^{n+1}s(n+1,k)=\sum_{k=1}^n \left( s(n,k-1)+ns(n,k)\right) + 1 \end{eqnarray*}$

und dann immer geradeaus

05.07.2010, 15:51

mathenovize

Auf diesen Beitrag antworten »

Hallo,

aiai, geradeaus smile

Das war ja jetzt ein ziemlich dickes Brett vorm Kopf. Ich danke euch beiden.

Das hat mir jetzt schon sehr beim Verstaendnis geholfen, habe die zweite Induktion auch ohne Hilfe hinbekommen und bin bei der ersten einen Schritt weiter. Ein Schritt ist mir allerdings noch nicht ganz klar geworden (wieder seit > 1 Stunde am verzweifeln).

Du aenderst die Indexe der Summe, um die Induktionsvorraussetzung anzuwenden. Aber die gilt doch nur fuer eine Summe von k=0 bis n. Muss ich dann nicht eine Summe haben, die auch von k=0 bis n laeuft, um die IV anwenden zu duerfen?

Mein Rechenweg sieht jetzt so aus:

$\begin{eqnarray*} \sum_{k=0}^{n+1} s(n+1,k) = s(n+1,0) + \sum_{k=1}^n (s(n,k-1)+n*s(n,k))+s(n+1,n+1) \end{eqnarray*}$
s(n+1,0) ist 0 (klar) und s(n+1,n+1) ist 1, auch klar. Also einsetzen und weiter:

$\begin{eqnarray*} \sum_{k=1}^n (s(n,k-1)+n*s(n,k))+1 \end{eqnarray*}$

Alles schoen auseinanderziehen um (immer schoen vorwaerts) die IV einsetzen zu koennen:

$\begin{eqnarray*} 1+ \sum_{k=1}^n s(n,k-1) + \sum_{k=1}^n n*s(n,k) \end{eqnarray*}$

So und jetzt kommt die Umformung, die ich leider noch nicht verstehe (und vermutlich falsch angewendet hab):

$\begin{eqnarray*} 1 + \sum_{k=0}^{n-1} s(n,k) + n*\sum_{k=0}^{n-1} s(n,k) \\ =_{IV} 1+ s((n-1)+1,1) + n*s((n-1)+1,1) \end{eqnarray*}$

Und davon jetzt darauf zu kommen dass

$\begin{eqnarray*} =s(n+1,1) \end{eqnarray*}$

gilt. Daran verzweifle ich gerade.

Danke euch beiden nochmal, ihr bringt mich gerade echt weiter im Verstaendniss smile

Gruesse

05.07.2010, 16:35

Auf diesen Beitrag antworten »

Zitat:

Original von mathenovize
Du aenderst die Indexe der Summe, um die Induktionsvorraussetzung anzuwenden. Aber die gilt doch nur fuer eine Summe von k=0 bis n. Muss ich dann nicht eine Summe haben, die auch von k=0 bis n laeuft, um die IV anwenden zu duerfen?

Ja. Ich hab ja nicht behauptet, dass mein Induktionsschritt schon vollständig ist - etwas sollst du ja auch noch zu tun haben. Augenzwinkern

Wenn also irgendwelche Summanden zuviel sind oder fehlen, um die IV anzuwenden, dann musst du nach dem Prinzip der "nahrhaften Null" diese Summen dahingehend anpassen.

Außerdem habe ich oben nicht skizziert, wie man $\begin{eqnarray*} \sum_{k=0}^n s(n,k) = s(n+1,1) \end{eqnarray*}$ nachweist, sondern $\begin{eqnarray*} \sum_{k=0}^n s(n,k) = n! \end{eqnarray*}$ .

06.07.2010, 11:17

mathenovize

Auf diesen Beitrag antworten »

Hallo zusammen und guten Morgen,

dein Hinweis hat mich gestern noch bis tief in die Nacht beschaeftigt. Es sieht einfach zu einfach aus, aber ich komme nicht drauf.

Dass es das einfachste ist Die Summe = n! zu beweisen und dann den Schritt von rechts nach links (n! =s(...)) zu beweisen ist mir mittlerweile klar. Leider hast du mich mit deinem Hinweis auf die nahrhafte Null ins dutzendweise rumrechnen Land geschickt smile

Ich wollte es einfach wissen.

Aber die einzig sinnvolle Idee, die mir gekommen ist ist folgende:

$\begin{eqnarray*} = 1 + \sum_{k=0}^{n-1} s(n,k) + n*\sum_{k=0}^{n-1} s(n,k) \end{eqnarray*}$

$\begin{eqnarray*} = 1+ \sum_{k=0}^{n} s(n,k) - n*s(n,k) + n*\sum_{k=0}^{n} s(n,k) - n*s(n,k) \end{eqnarray*}$

Ich vermute, dass ich schon zu Anfang irgendwo die Summe falsch umgeformt habe, aber danach hab ich mir heute Nacht einen Wolf gesucht.

Es waere so schoen, einfach deinen Ausdruck:

$\begin{eqnarray*} 1 +\sum_{k=0}^{n-1} s(n,k) + n*\sum_{k=0}^{n} s(n,k) \end{eqnarray*}$

So umzuformen, dass:
- Ich eine -1 irgendwoher hole um die +1 loszuwerden
- Den Index der ersten Summe bis n laufen lassen koennte

Bin fuer jeden Tip dankbar smile

06.07.2010, 11:20

mathenovize

Auf diesen Beitrag antworten »

Hallo nochmal,

habe es jetzt nochmal umgeformt:

$\begin{eqnarray*} 1 + (n+1)*\sum_{k=0}^{n-1} s(n,k) \end{eqnarray*}$
wenn ich jetzt noch die 1 in die Summe reinbauen koennte waere es denke ich geschafft.

Gruesse

06.07.2010, 11:51

mathenovize

Auf diesen Beitrag antworten »

Okay, ich glaube ein kleiner Hinweis eines Kollegen hat mir gerade die Rettung gebracht. Eine kurze Bestaetigung ja/nein waere sehr hilfreich.

Also, ich starte mit dem bekannten Ausdruck:

$\begin{eqnarray*} 1+\sum_{k=0}^{n-1} s(n,k) + n*\sum_{k=1}^{n} s(n,k) \end{eqnarray*}$

Dann benutze ich den hinweis der nahrhaften Null und ziehe das erste Element der ersten Summe, welches s(a,0)=0 ist aus der Summe:

$\begin{eqnarray*} 1+0+ \sum_{k=1}^{n-1} s(n,k) + n*\sum_{k=1}^{n} s(n,k) \end{eqnarray*}$

Jetzt ziehe ich bei beiden Summen s(a,0)=0 mit in die Summen rein und kann so den Index ab k=0 laufen lassen (ist ja dann statt s(n,1)+s(n,2)+... einfach eine Null draufaddiert ganz am Anfang)

$\begin{eqnarray*} 1+\sum_{k=0}^{n-1} s(n,k) + n*\sum_{k=0}^{n} s(n,k) \end{eqnarray*}$

Jetzt ueberlege ich mir, dass das allerhoechste Glied der ersten Summe ja s(n,k) mit n=k also s(n,k)=1 ist. Ich forme also meine 1 entsprechend um und ziehe sie wieder in die erste Summe rein. Das ergibt dann:

$\begin{eqnarray*} \sum_{k=0}^{n} s(n,k) + n*\sum_{k=0}^{n} s(n,k) \end{eqnarray*}$

Jetzt kann ich umklammern und erhalte:

$\begin{eqnarray*} (n+1)*\sum_{k=0}^{n} s(n,k) \end{eqnarray*}$

Da setze ich noch die IV ein und bekomme:

$\begin{eqnarray*} (n+1)*n! \end{eqnarray*}$

Das entspricht (logisch):

$\begin{eqnarray*} (n+1)! \end{eqnarray*}$

qed.

Richtig?

Gruesse und Danke im Vorraus

06.07.2010, 11:59

Auf diesen Beitrag antworten »

Na endlich, das wurde aber auch Zeit. Freude