6
$\begingroup$

$\mathbf {Theorem:} $ $$ \sum_{k=0}^n S_1(n,k)x^k = x(x +1)···(x +n−1) $$

I want to prove the above theorem, and I know that I should use the recurrence relation $$ S_1(n,k)=S_1(n-1,k-1)+(n-1)S_1(n-1,k). $$ I also know that $$\sum_{k=0}^n S_1(n,k)=n! ,\quad S_1(n,1)=(n-1)! ,\quad S_1(n,n)=1,$$ and $$S_1(n,0)=S_1(0,n)=0 \quad \text{if} \quad n\neq0. $$ I just started doing this:$$ \sum_{k=0}^n S_1(n,k)x^k =S_1(n,0)+S_1(n,1)x+S_1(n,2)x^2+...+S_1(n,n)x^n.$$ However I do not know how to proceed further. Can anybody help at this point?

$\endgroup$
  • 1
    $\begingroup$ Multiply the last equation by $(x+n)$ and use $S_1(n+1,k)=S_1(n,k-1)+nS_1(n,k)$ ... & of course induction. $\endgroup$ – Donald Splutterwit Jul 23 '17 at 12:20
1
$\begingroup$

As Donald Splutterwit mentioned in the comments, you can prove this by induction in the same way you can prove the binomial formula by induction and Pascal's recurrence. In this case we have

\begin{align} x^{\overline{n}} &= \sum_{k = 0}^n S_1(n,k)x^k \\ x^{\overline{n + 1}} &= (x + n)\sum_{k = 0}^n S_1(n,k)x^k \\ &= \sum_{k = 1}^{n + 1} S_1(n,k - 1)x^{k} + \sum_{k = 0}^{n} nS_1(n,k)x^{k} \\ &= \sum_{k = 0}^{n + 1} S_1(n + 1,k)x^k. \end{align}

$\endgroup$
  • $\begingroup$ @DonaldSplutterwit thanks $\endgroup$ – Trevor Gunn Jul 23 '17 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.