著色問題

[armopen]

請教 thepiano 老師下面的問題，謝謝您的幫忙.

我主要卡在看不懂書上的解法，原題如下：

用 k 種顏色來塗下圖之 n 個區域，每一區域一色，相鄰區域異色，顏色可以重複取用，不一定

k 種顏色全用，求證塗法 = (k- 1) (-1)^n + (k - 1)^n.

書上解法： 設用 k 顏色塗下列 n 個區域，相鄰異色塗法有 a_n，則

a_n + a_(n-1) = k．(k - 1)^(n-1) (為什麼？)

註： 原題目的圖形連結如下：

http://imajr.com/e89197e889b2e5958fe9a18c.bmp-1444887

[thepiano]

http://forum.nta.org.tw/examservice/sho ... hp?t=42668

[M9331707]

我的想法是
第1塊與第(n-1)塊同色:有(a_n-2)x1x(k-1)種
第1塊與第(n-1)塊異色:有(a_n-1)x(k-2)種
所以, a_n=(k-2)xa_n-1+(k-1)xa_n-2種
接下去利用特徵方程式求出兩根為(-1)與(k-1)
但初始值a_1=k,a_2=k(k-1)嗎?!