1
$\begingroup$

For a fixed integer k, how would I prove that

$$\sum_{n\ge k} \left\{n \atop k\right\}x^n= \frac{x^k}{(1-x)(1-2x)...(1-kx)}.$$

where $\left\{n \atop k\right\}=k\left\{n-1 \atop k\right\}+\left\{n-1 \atop k-1 \right\}$

$\endgroup$
2
  • $\begingroup$ Use the recurrence for the Stirling numbers. $\endgroup$ Oct 28 '18 at 16:41
  • $\begingroup$ There are some basic proofs at the following MSE link. $\endgroup$ Oct 28 '18 at 17:32
0
$\begingroup$

The definition of ${n\brace k}$ through the recursion is easily seen to be equivalent to the combinatorial definition "the number of ways for partitioning a set with $n$ elements into $k$ non-empty subsets". $m^n$ can be interpreted as the number of functions from $[1,n]$ to $[1,m]$: if we classify them according to the cardinality of their range, we may easily check that $$ m^n =\sum_{k=1}^{n}{n\brace k}k! \binom{m}{k} \tag{1}$$ i.e. Stirling numbers of the second kind allow to decompose monomials into linear combination of binomial coefficients. In equivalent terms ${n\brace k}k!$ is the number of surjective functions from $[1,n]$ to $[1,k]$, and $${n \brace k}k!=\sum_{j=0}^{k}\binom{k}{j}j^n (-1)^{k-j} \tag{2}$$ follows by inclusion-exclusion. $(2)$ is a natural counter-part of $(1)$, and it leads to $$ {n\brace k} x^n = \sum_{j=0}^{k}\frac{x^n j^n (-1)^{k-j}}{j!(k-j)!} \tag{3}$$ then to: $$ \sum_{n\geq k}{n\brace k}x^n = x^k\sum_{j=0}^{k}\frac{j^k (-1)^{k-j}}{j!(k-j)!(1-jx)}=x^k\sum_{j=1}^{k}\frac{j^k}{k!}\binom{k}{j}\frac{(-1)^{k-j}}{1-jx}.\tag{4}$$ By residues or equivalent techniques, the last sum can be easily checked to be the partial fraction decomposition of $\frac{1}{(1-x)(1-2x)\cdot\ldots\cdot(1-kx)}$, proving the claim.

$\endgroup$
0

Your Answer

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