科普：环形染色公式（中间不染色）的推导

我们先把他当链做：这样有 $m (m-1)^{n-1}$ 种做法。

在变成环，分类讨论：

1. $1$ 和 $n$ 相同这样就有 $f_{n-1}$ 种方案

2. 反之，为 $f_n$ 种做法

所以 $f_n+f_{n-1}=m(m-1)^{n-1}$ 。

还可以化：

$$f_n+f_{n-1}=m(m-1)^{n-1}=(m-1+1)(m-1)^{n-1}=(m-1)^n+(m-1)^{n-1} $$

移项，得

$$f_n-(m-1)^n=-(f_{n-1}-(m-1)^{n-1})$$

我们令 $b_n={f_n-(m-1)^n}$，你会发现

$\large \frac{b_n}{b_{n-1}}=-1$，所以 $b$ 是个等比数列。

当 $n=2$ 时，显然，$f_2=m(m-1)$，则

$$b_2=f_2-(m-1)^2=m(m-1)-(m-1)^2=m-1$$

所以 $b_n=b_2 \times (-1)^{n-2} = (-1)^n\times (m-1)$

又因为 $f_n=b_n+(m-1)^n$，

所以 $f_n=(m-1)^n+(-1)^n\times(m-1)$。