Problem, indirgemeli diziler için iyi bir uygulamadır.
$n$ tane dilim $k$ tane renk ile istenen özellikte $a_n$ farklı yolla boyanabiliyor olsun. $n=1,2,3$ durumlarını incelemek kolaydır: $a_1=k$, $a_2=k(k-1)$, $a_3=k(k-1)(k-2)$ olur.
$n\geq 4$ durumunu inceleyelim. $i=1,2,\dots, n-1$ olmak üzere $i$-inci dilim ile $i+1$-inci dilim farklı renkte olacak şekilde tüm boyamaların sayısı $k\cdot (k-1)^{n-1}$ dir. Bu tüm durumların içinde $n$-inci dilim ile $1$-inci dilimin aynı renkte olduğu istenmeyen durumlar da vardır.
Bu istenmeyen durumları hesaplayalım: $n-1$-inci dilim ile $n$-inci dilim farklı renkte ve $n$-inci dilim ile $1$-inci aynı renkte olduğundan $n-1$-inci dilim ile $1$-inci dilim farklı renktedir. O halde bu ilk $n-1$ dilimde, ardışık dilimler farklı renkte olacak biçimde boyanma sayısı $a_{n-1}$ olur.
İstenen durumların sayısı ile istenmeyen durumların sayısı toplanıp tüm durumların sayısına eşitlenirse $n \geq 4$ için
$$ a_n + a_{n-1} = k(k-1)^{n-1} \tag{1}$$
indirgeme bağıntısı elde edilir. Homojen doğrusal indirgemeli dizinin karakteristik denklemi $r+1=0$ olup bir kök $r_1=-1$ dir. Ayrıca $(1)$ deki homojen olmayan bağıntı, homojen hale getirilmek istenirse karakteristik denklem için bir kök de $r_2=k-1$ olacaktır. İndirgemeli dizilerin çözüm teorisinden bunu biliyoruz. Fakat bilmesek bile $(1)$ de $n$ yerine $n+1$ yazıldıktan sonra ikinci mertebeden homojen denklem elde etmek zor değildir. Dolayısıyla $(1)$ bağıntısını $n\geq 4$ için
$$ a_n=C_1r_1^n + C_2r_2^n = C_1(-1)^n + C_2(k-1)^n \tag{2} $$
biçiminde açık halde ifade edebiliriz. $C_1$, $C_2$ sabitlerini belirlemek gerekiyor.
$n=4$ için $a_4 + a_3 = k\cdot (k-1)^3$ olup $a_4= k\cdot (k-1)^3 - k\cdot (k-1)\cdot (k-2)$
$n=5$ için $a_5 + a_4 = k\cdot (k-1)^4$ olup $a_5= k\cdot (k-1)^4 - k\cdot (k-1)^3 + k\cdot (k-1)\cdot (k-2)$
yazılır. $(2)$ de $n=4$ ve $n=5$ yazılarak $C_1$, $C_2$ değerleri çözülürse $C_1 = k-1$, $C_2=1$ elde edilir. Dolayısıyla $n\geq 4$ için
$$ a_n = (k-1)(-1)^n + (k-1)^n \tag{3}$$
formülü elde edilir.
