Why is $S_{n,3} = \frac{1}{6}(3^n - 3\cdot2^n+3)$? (Stirling) 
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..
 A: 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}
$
A: 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.
