连接正$n$边形$(n\ge 4)$的中心与各个顶点形成$n$个全等三角形，用最多$n-2$种颜色为各三角形染色，要求两个相邻的三角形不能同色，记共有涂色方法$R_{n}$种，证明：
$$R_{n} = (n-3)^{n} + (-1)^{n-2} (n-3)$$

解答

首先将这$n$个三角形顺时针依次标号$1,2,\dots ,n$
记$a_{k}(k=2,3,\dots ,n)$表示第k格与第1格颜色相同的概率，则$a_{2}=0$
记$b_{k}(k=2,3,\dots ,n)$表示第k格与第1格颜色不同的概率，则$b_{2}=1$
于是，我们有
\begin{cases}
a_{k}=\frac{1}{n-3}b_{k-1} \\
b_{k}=1-a_{k}
\end{cases}即
$$b_{k}=1-\frac{1}{n-3}b_{k-1}$$于是
\begin{align}
b_{k}-\frac{n-3}{n-2} &= -\frac{1}{n-3}b_{k-1}+1-\frac{n-3}{n-2} \\
&= -\frac{1}{n-3}(b_{k-1}-\frac{n-3}{n-2})
\end{align}进而
$$b_{k}=\frac{1}{n-2}\times (-\frac{1}{n-3})^{k-2}+\frac{n-3}{n-2}$$则
\begin{align}
R_{n} &= (n-2)(n-3)^{n-1}\times b_{n} \\
&= (n-3)^{n} + (-1)^{n-2} (n-3)
\end{align}得证