Why is $S_{n,3} = \frac{1}{6}(3^n - 3\cdot2^n+3)$? (Stirling)

Question

Why is $S_{n,3} = \frac{1}{6}(3^n - 3\cdot2^n+3)$?

I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$

Where we know $S(n,2)=2S(n-1,2)+1$

We can also see the latter recurrence leads to $S(n,2)=2^{n-1}-1$

So we get $S(n,2)=2s(n-1,2)+2^{n-1}-1$

I am new to Stirling, so I don't know how to continue..

Answer 1

That is a standard linear recurrence for $S(n,3)$ of the form $a(n+1)=ca(n)+b(n)$.

Dividing by $c^{n+1}$, this becomes $a(n+1)/c^{n+1}=a(n)/c^{n}+b(n)/c^{n+1}$.

Letting $d(n)=a(n)/c^{n}$, this become $d(n+1)=d(n)+b(n)/c^{n+1}$ which can readily be solved.

(added after a request)

$d(n+1)=d(n)+b(n)/c^{n+1}$ becomes, using $k$ instead of $n$, $d(k+1)-d(k) =b(k)/c^{k+1}$.

Summing from $0$ to $n-1$,

$\begin{array}\\ d(n)-d(0) &=\sum_{k=0}^{n-1}(d(k+1)-d(k))\\ &=\sum_{k=0}^{n-1}\dfrac{b(k)}{c^{k+1}}\\ &=\sum_{k=0}^{n-1}\dfrac{2^{k-1}-1}{c^{k+1}} \qquad\text{since }b(n) = 2^{n-1}-1\\ &=\sum_{k=0}^{n-1}\dfrac{2^{k-1}}{c^{k+1}}-\sum_{k=0}^{n-1}\dfrac{1}{c^{k+1}}\\ &=\dfrac{1}{2c}\sum_{k=0}^{n-1}\dfrac{2^{k}}{c^{k}}-\dfrac1{c}\sum_{k=0}^{n-1}\dfrac{1}{c^{k}}\\ &=\dfrac{1}{2c}\dfrac{1-(2/c)^n}{1-2/c}-\dfrac1{c}\dfrac{1-(1/c)^n}{1-1/c}\\ &=\dfrac{1-(2/c)^n}{2c-2}-\dfrac{1-(1/c)^n}{c-1}\\ &=\dfrac{c^n-2^n}{2(c-1)c^n}-\dfrac{c^n-1}{(c-1)c^n}\\ &=\dfrac{c^n-2^n-2(c^n-1)}{2(c-1)c^n}\\ &=\dfrac{-c^n-2^n+2}{2(c-1)c^n}\\ \text{so}\\ \dfrac{a(n)}{c^n}-a(0) &=\dfrac{-c^n-2^n+2}{2(c-1)c^n}\\ \text{or}\\ a(n)-a(0)c^n &=\dfrac{-c^n-2^n+2}{2(c-1)}\\ \end{array} $

or

$\begin{array}\\ a(n) &=a(0)c^n+\dfrac{-c^n-2^n+2}{2(c-1)}\\ &=c^n(a(0)-\dfrac1{2(c-1)}-\dfrac{2^n-2}{2(c-1)}\\ &=c^n(a(0)-\dfrac1{2(c-1)}-\dfrac{2^{n-1}-1}{c-1}\\ &=3^n(a(0)-\dfrac1{4}-\dfrac{2^{n-1}-1}{2} \qquad\text{since }c = 3\\ \end{array} $

Answer 2

Since the Sirling numbers of the 2nd kind are the bridge between powers and Falling Factorials $$ x^{\,n} = \sum\limits_{0\, \le \,k\, \le \,n} {S_{\,n,\,k} \,x^{\,\underline {\,k\,} } } = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}x^{\,\underline {\,k\,} } } $$ then $$ \eqalign{ & 3^{\,n} = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}3^{\,\underline {\,k\,} } } = \left\{ \matrix{ n \cr 0 \cr} \right\}1 + \left\{ \matrix{ n \cr 1 \cr} \right\}3 + \left\{ \matrix{ n \cr 2 \cr} \right\}6 + \left\{ \matrix{ n \cr 3 \cr} \right\}6 + 0 \cr & 2^{\,n} = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}2^{\,\underline {\,k\,} } } = \left\{ \matrix{ n \cr 0 \cr} \right\}1 + \left\{ \matrix{ n \cr 1 \cr} \right\}2 + \left\{ \matrix{ n \cr 2 \cr} \right\}2 + 0 \cr & 1 = 1^{\,n} = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}1^{\,\underline {\,k\,} } } = \left\{ \matrix{ n \cr 0 \cr} \right\}1 + \left\{ \matrix{ n \cr 1 \cr} \right\}1 + 0 \cr & 0^{\,n} = \left[ {0 = n} \right] = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}0^{\,\underline {\,k\,} } } = \left\{ \matrix{ n \cr 0 \cr} \right\}1 \cr} $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Solving this linear system gives you the answer.