# Solution to a recurrence relation

Set $$F_k(x) := \sum_{n\geq k} S(n,k)x^n$$. Prove that $$F_1(x) = \frac{x}{1-x}, \space \space \space F_2(x) = \frac{x^2}{(1-x)(1-2x)}$$

Furthermore, show that the function $$F_k(x)$$ satisfy the recurrence relation $$F_k(x) = \frac{x}{1-kx}F_{k-1}(x)$$ and solve this recurrence.

Any ideas how to approach this problem?

• @flawr Stirling number of the second kind. And I don't know even how to attack the problem. – user72151 Nov 14 '15 at 19:18
• Do you know about generating functions? If not it might be still feasible but perhpas somewhat more difficult. I recomment generatingfunctionology a great introduction to generating functions. PS: I just noticed that you can find this exact example in the mentioned book at about page 19. – flawr Nov 14 '15 at 19:20
• There is an extensive discussion of this at the following MSE link. – Marko Riedel Nov 14 '15 at 20:08
• @MarkoRiedel Thanks :) – user72151 Nov 14 '15 at 20:09

## 1 Answer

I prefer the notation $n\brace k$ for your $S(n,k)$. The first step is to observe that ${n\brace 1}=1$ for $n\ge 1$: there is only one partition of $[n]=\{1,\ldots,n\}$ into just one part. Thus,

$$F_1(x)=\sum_{n\ge 1}{n\brace 1}x^n=\sum_{n\ge 1}x^n=x\sum_{n\ge 1}x^{n-1}=x\sum_{n\ge 0}x^n=\frac{x}{1-x}\;.$$

To get $F_2(x)$, we need to figure out what $n\brace 2$ is. Suppose that we partition $[n]$ into two non-empty parts. One of the parts must contain the number $n$; call that part $A$ and the other part $B$. What can the rest of $A$ look like? It can’t be all of $[n-1]$, since then $B$ would be empty, but it can be any other subset of $[n-1]$. Since $[n-1]$ has $2^{n-1}$ subsets, there are $2^{n-1}-1$ possible choices for the rest of $A$ and hence for a $2$-part partition of $[n]$. Thus, ${n\brace 2}=2^{n-1}-1$ for $n\ge 2$, and

\begin{align*} F_2(x)&=\sum_{n\ge 2}{n\brace 2}x^n\\ &=\sum_{n\ge 2}\left(2^{n-1}-1\right)x^n\\ &=\sum_{n\ge 2}2^{n-1}x^n-\sum_{n\ge 2}x^n\\ &=2x^2\sum_{n\ge 0}(2x)^n-x^2\sum_{n\ge 0}x^n\\ &=\frac{2x^2}{1-2x}-\frac{x^2}{1-x}\\ &=\frac{2x^2(1-x)-x^2(1-2x)}{(1-x)(1-2x)}\\ &=\frac{x^2}{(1-x)(1-2x)}\;. \end{align*}

At this point we want the standard recurrence relation satisfied by the Stirling numbers of the second kind,

$${n\brace k}=k{{n-1}\brace k}+{{n-1}\brace{k-1}}\;,$$

substituting it into the definition of $F_k(x)$:

\begin{align*} F_k(x)&=\sum_{n\ge k}{n\brace k}x^n\\ &=k\sum_{n\ge k}{{n-1}\brace k}x^n+\sum_{n\ge k}{{n-1}\brace{k-1}}x^n\\ &=kx\sum_{n\ge k-1}{n\brace k}x^n+x\sum_{n\ge k-1}{n\brace{k-1}}x^n\\ &=kxF_k(x)+xF_{k-1}(x)\;. \end{align*}

Now just solve for $F_k(x)$ in terms of $F_{k-1}(x)$.

• Thanks Brian for the good answer. If you are free can you take a look at the following problem. There seems to be an answer, but I really don't understand anything from that answer. math.stackexchange.com/questions/1528709/… – user72151 Nov 16 '15 at 17:36
• How did you get the recurrence relation formula (${n\brace k}=k{{n-1}\brace k}+{{n-1}\brace{k-1}}\;$) that you have written from the standard formula in Wikipedia, cause it seems a bit different, clearly you have done some algebraic manipulation but I cannot see it. – user72151 Nov 16 '15 at 19:12
• @terett: I simply decreased the upper number by $1$. – Brian M. Scott Nov 16 '15 at 20:12
• @BrianM.Scott Isn't that kind of operation problem? Because now we try to partition $n-1$ element set into $k-1$-partition, instead of the original $n$ element set, so we have one less element I see. – user72151 Nov 16 '15 at 20:19
• @terett: No, it’s not a problem at all. It’s no different in principle from taking a recurrence $a_{n+1}=a_n+a_{n-1}$ and rewriting it as $a_n=a_{n-1}+a_{n-2}$. If you prefer, you can think of it as a substitution. Let $m=n+1$; then the recurrence in Wikipedia becomes ${m\brace k}=k{{m-1}\brace k}+{m\brace{k-1}}$. Now rename $m$ to $n$. – Brian M. Scott Nov 16 '15 at 20:25