Stirling Numbers of the Second Kind Proof

Question

Prove that \begin{align*} \sum_{n=1}^\infty S(n,n-2)x^n=\dfrac{x^3(1+2x)}{(1-x)^5} \end{align*}

My guess is that I have to take the LHS and simply it, as well as take the RHS and simplify it, but not sure how to exactly do that.

Any help, tips, or a fully worked out solution would be appreciated!

Answer 1

Answer $1$ : Using the recurrence relation.

The Stirling numbers of the second kind satisfy the recurrence relation \begin{eqnarray*} {n \brace k}= k {n-1 \brace k}+ {n-1 \brace k-1}. \end{eqnarray*} With $k=n$ we have ${n \brace n}= {n-1 \brace n-1}=1$ and \begin{eqnarray*} S_{0}(x)=\sum_{n=1}^{\infty} {n \brace n} x^n = \frac{x}{1-x}. \\ \end{eqnarray*} For $k=n-1$ we have \begin{eqnarray*} S_{1}(x)=\sum_{n=2}^{\infty} {n \brace n-1} x^n &=& \sum_{n=2}^{\infty} (n-1){n-1 \brace n-1} x^n+ \sum_{n=2}^{\infty} {n-1 \brace n-2} x^n\\ &=& x^2 \frac{d}{dx} \left( \frac{S_0(x)}{x} \right) + x S_1(x) \\ \end{eqnarray*} Differentiating & rearranging gives \begin{eqnarray*} S_{1}(x)=\frac{x^2}{(1-x)^3}. \\ \end{eqnarray*} For $k=n-2$ we have \begin{eqnarray*} S_{2}(x)=\sum_{n=3}^{\infty} {n \brace n-2} x^n &=& \sum_{n=3}^{\infty} (n-1){n-1 \brace n-2} x^n+ \sum_{n=3}^{\infty} {n-1 \brace n-3} x^n\\ &=& x^3 \frac{d}{dx} \left( \frac{S_1(x)}{x} \right) + x S_2(x) \\ \end{eqnarray*} Again differentiating & rearranging gives \begin{eqnarray*} S_{2}(x)=\frac{x^3(1+2x)}{(1-x)^5}. \\ \end{eqnarray*}

Answer $2$: Combinatorial interpretation.

The stirling number ${n \brace k}$ of the second kind are the number of ways to split an $n$-set into $k$ (disjoint) blocks.

For ${n \brace n-2}$ there are two possibilities

$1)$ A block of size $3$ and $n-3$ blocks of size $1$ ... & there are $\binom{n}{3}$ ways to choose these configurations, giving the generating function \begin{eqnarray*} \frac{x^3}{(1-x)^4}. \\ \end{eqnarray*}

$2)$ $2$ blocks of size $2$ and $n-4$ blocks of size $1$ ... & there are $3 \times \binom{n}{4}$ ways to choose these configurations, giving the generating function \begin{eqnarray*} \frac{3x^4}{(1-x)^5}. \\ \end{eqnarray*} Now add these two terms to obtain the required generating function.

Answer 2

Hint

Using what @Henry wrote in comments, we face the problem of $$a_n=n(n-1)(n-2)(3n-5)$$ So, the usual trick is to write $$a_n=A n(n-1)(n-2)(n-3)+Bn(n-1)(n-2)+Cn(n-1)+Dn$$ Comparing the coefficients, $A=3$, $B=4$, $C=D=0$.

Now you face the problem of the summation of the derivatives of $\sum_{n=1}^\infty x^n$.