~Teachingcenter的醫學筆記~

一個圓被半徑分割成n等份用k種顏色來塗，每一區域塗一色，相鄰異色，顏色可以重複，不一定k種顏色全用，求證塗法為(k-1)(-1)^n+(k-1)^n

由第 1 區開始圖顏色，有 k 種顏色可以用，

第 2 區必須跟第 1 區異色，所以有 k-1 種顏色可以用，

第 3 區必須跟第 2 區異色，所以有 k-1 種顏色可以用，
‧
‧
‧
第 n-1 區必須跟第 n-2 區異色，所以有 k-1 種顏色可以用，

第 n 區必須跟第 n-1 區異色，所以有 k-1 種顏色可以用。

所以以上共有 k(k-1)^{n-1} 種塗色法。

可是這個數據並不是 a_n ，因為第 n 區可能跟第 1 區同色或是異色，

所以這個數據包含有 n 個區域相鄰塗異色，以及 n-1 個區域相鄰塗異色(第 n 區與第 1 區同色)的情況，

所以這個數據是 a_n + a_{n-1}，故 a_n + a_{n-1} = k(k-1)^{n-1} 　for all n>=3，

再加上遞迴關係式的初始條件 a_2 = k(k-1) 與 a_3=k(k-1)(k-2) ，可以求出 a_n (以 n 及 k 表示)。

引用自：http://math.pro/db/thread-499-1-1.html