Vollständige Induktion?

01.12.2007, 13:54	speedyschmidt	Auf diesen Beitrag antworten »
Vollständige Induktion? Hey Ihr da draussen An folgender Summenformel zerbeiß ich mir jetzt schon sehr lange die Zähne: $\begin{eqnarray} \sum_{k=1}^n~(-1)^k\cdot k^m\cdot {n \choose k}=0 \end{eqnarray}$ Angeblich soll das sowohl mit als auch ohne Induktion machbar sein. Ohne Induktion stört mich das k^m gewaltig, da ich nicht weiß, wie ich das aus der Summe kriege. Und mit Induktion über n komme ich auf folgendes: $\begin{eqnarray} \sum_{k=1}^{n+1}~(-1)^k\cdot k^m\cdot {n+1 \choose k} =(-1)^{n+1}\cdot (n+1)^m+ \sum_{k=1}^{n}~(-1)^k\cdot k^m \cdot {n \choose k} +\sum_{k=1}^{n}~(-1)^k\cdot k^m\cdot {n \choose k-1} \end{eqnarray}$ $\begin{eqnarray} =(-1)^{n+1}\cdot (n+1)^m+\sum_{k=1}^{n}~(-1)^k\cdot k^m\cdot {n \choose k-1}=\sum_{k=1}^{n+1}~(-1)^k\cdot k^m\cdot {n \choose k-1}=\sum_{k=0}^{n}~(-1)^{k+1}\cdot (k+1)^m\cdot {n \choose k} \end{eqnarray}$ Und hier komm ich jetzt nicht weiter, da der mittlere Faktor enorm stört... Auch bei Induktion über m komm ich kein stück weit... Was also kann ich tun? Vielen Dank, Euer Speedy
01.12.2007, 14:31	AD	Auf diesen Beitrag antworten »
Hast du nicht was an Voraussetzungen vergessen? Etwa die Einschränkung, dass $\begin{eqnarray} m<n \end{eqnarray}$ ist? Für $\begin{eqnarray} m\geq n \end{eqnarray}$ ist die Aussage nämlich falsch.
01.12.2007, 14:37	speedyschmidt	Auf diesen Beitrag antworten »
jo, Verzeihung. $\begin{eqnarray} 1<m<n \end{eqnarray}$
01.12.2007, 14:39	AD	Auf diesen Beitrag antworten »
Ich kenne die Formel aus diesem kombinatorischen Zusammenhang: Anzahl surjektiver Funktionen Die Summe kennzeichnet also die Anzahl der Surjektiven Abbildungen einer $\begin{eqnarray} m \end{eqnarray}$ -elementigen Menge in eine $\begin{eqnarray} n \end{eqnarray}$ -elementige Menge. Ist $\begin{eqnarray} m<n \end{eqnarray}$ , dann gibt es offensichtlich überhaupt keine solche surjektive Abbilung, daher der Summenwert Null. Für $\begin{eqnarray} m\geq n \end{eqnarray}$ dagegen gibt es surjektive Abbildungen.
01.12.2007, 14:43	speedyschmidt	Auf diesen Beitrag antworten »
Ohh, muss ich den Zusammenhang verstehen, den du verlinkt hast, um das zu beweisen?
01.12.2007, 14:51	AD	Auf diesen Beitrag antworten »
Nein, musst du nicht - es gibt viele Wege nach Rom, das ist einer der bequemsten, wenn man die Siebformel kennt. Dein Weg oben verläuft wohl als Induktion über $\begin{eqnarray} n \end{eqnarray}$ , oder? Da scheint schon der Induktionsanfang $\begin{eqnarray} n=m+1 \end{eqnarray}$ (drunter gilt es ja gar nicht) nicht gerade trivial ...
Anzeige

01.12.2007, 15:06	speedyschmidt	Auf diesen Beitrag antworten »
richtig, auch das würde ich wieder mittels Induktion machen, aber auch hier stoße ich auf unlösbare probleme...
01.12.2007, 15:25	AD	Auf diesen Beitrag antworten »
Auch wenn ich es nicht probiert habe, könnte ich mir eher vorstellen, dass eine Induktion über $\begin{eqnarray} m \end{eqnarray}$ bei festem $\begin{eqnarray} n \end{eqnarray}$ klappt: Induktionsanfang $\begin{eqnarray} m=0 \end{eqnarray}$ ist recht leicht zu sehen. Allerdings dürfte der Induktionsschluss $\begin{eqnarray} (m-1)\to m \end{eqnarray}$ nur für $\begin{eqnarray} m<n \end{eqnarray}$ funktionieren, aber das reicht ja auch.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »