Polynomielle Identität mit Stirling-Zahlen (Induktion)

Question

Aufgabe:

Berechne die folgende polynomielle Identität mit Induktion nach n:

$$\sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^k=\prod \limits_{j=0}^{n-1}(X-j)$$

$$s_{n,k}$$ sind Stirling-Zahlen erster Art.

Problem/Ansatz:

Induktionsanfang ist kein Problem, aber beim Induktionsschritt hakt es an einer Stelle. Durch rekursives Einsetzen erhalte ich ja $$\sum \limits_{k=0}^{n+1}(-1)^{n-k+1}(s_{n,k-1}+ns_{n,k})X^k,$$was ich dann in zwei Summen aufteilen kann. Leider scheitere ich dann momentan immer beim Einsetzen der Induktionsvoraussetzung, der Indexshift will mir nicht so recht gelingen.

Answer 1

$$\sum \limits_{k=0}^{n+1}(-1)^{n+1-k}s_{n+1,k}X^k$$

vor der Rekursion musst du aber schauen, dass es keinen Ärger mit den

Indizes gibt , also besser erst mal

$$= (-1)^ns_{n+1,0}X^0+ \sum \limits_{k=1}^{n+1}(-1)^{n+1-k}s_{n+1,k}X^k$$

$$ =(-1)^n \cdot 0 \cdot X^0+ \sum \limits_{k=1}^{n+1}(-1)^{n+1-k}s_{n+1,k}X^k$$

$$ = \sum \limits_{k=1}^{n+1}(-1)^{n+1-k}s_{n+1,k}X^k$$

und dann die Rekursion

$$\sum \limits_{k=1}^{n+1}(-1)^{n-k+1}(s_{n,k-1}+ns_{n,k})X^k,$$
$$=\sum \limits_{k=1}^{n+1}(-1)^{n-k+1}s_{n,k-1}X^k+ \sum \limits_{k=1}^{n+1}(-1)^{n-k+1}ns_{n,k}X^k$$

Indexshift bei der 1. Summe:

$$=\sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^{k+1}+n \sum \limits_{k=0}^{n+1}(-1)^{n-k+1}s_{n,k}X^k$$

und der letzte Summand in der 2. Summe ist ja auch 0, also

$$=\sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^{k+1}+n \sum \limits_{k=0}^{n}(-1)^{n-k+1}s_{n,k}X^k$$

Jetzt aus der 1. Summe ein X und aus der zweiten eine (-1) rausziehen

$$=X\sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^{k} -n \sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^k$$

und dann die Summe ausklammern

$$=(X-n)\sum \limits_{k=0}^{n}(-1)^{n-k}s_{n,k}X^{k} $$

und jetzt die Induktionsannahme einsetzen gibt das gewünschte Ergebnis.