Malujemy płot. Każdą sztachetę możemy pomalować jednym z pięciu kolorów: białym, czerwonym, zielonym, niebieskim lub żółtym. Biała sztacheta może wystąpić obok dowolnej sztachety, ale kolorowa sztacheta nie może wystąpić obok innej kolorowej sztachety innego koloru. Na ile sposobów możemy pomalować płot składający się z \(\displaystyle{ n}\) sztachet? Należy ułożyć odpowiednie równanie rekurencyjne i rozwiązać je.
Proszę o sprawdzenie poniższego rozwiązania:
Zero sztachet możemy pomalować na jeden sposób. Jedną sztachetę możemy pomalować na \(\displaystyle{ 5}\) sposobów. Jeśli są dwie sztachety to jeśli pierwszą pomalujemy na biało to pomalowanie drugiej sztachety sprowadzamy do przypadku z jedną sztachetą pomalowaną dowolnie, a jeśli pierwszą sztachetę pomalujemy na kolorowo to jeśli drugą pomalujemy na biało to pomalowanie pozostałych zera sztachet sprowadzimy do przypadku pomalowania zera sztachet, a jeśli drugą pomalujemy na kolorowo to mamy cztery możliwości. Czyli:
\(\displaystyle{ S_0=1}\)
\(\displaystyle{ S_1=5}\)
\(\displaystyle{ S_2=S_1+4 \cdot S_0+4}\) i analogicznie dalej
jeśli mamy trzy sztachety to jeśli pierwszą pomalujemy na biało to pozostałe dwie sztachety sprowadzamy do przypadku dwóch sztachet, a jeśli pierwszą pomalujemy na kolorowo, to jeśli drugą pomalujemy na biało to sprowadzamy do przypadku jednej sztachety, a jeśli drugą pomalujemy na kolorowo i trzecią na biało to sprowadzamy do zera sztachet i jeśli wreszcie trzecią też pomalujemy na kolorowo to mamy cztery możliwości.
\(\displaystyle{ S_3=S_2+4S_1+4S_0+4}\) i ten schemat się powtarza więc dalej, ogólnie dostajemy, że:
\(\displaystyle{ S_{n-1}=S_{n-2}+4S_{n-3}+4S_{n-4}+...+4S_1+4S_0+4}\)
\(\displaystyle{ S_{n}=S_{n-1}+4S_{n-2}+4S_{n-3}+...+4S_1+4S_0+4}\)
Odejmując te równości stronami dostaniemy:
\(\displaystyle{ S_n-S_{n-1}=S_{n-1}+3S_{n-2}}\) czyli:
\(\displaystyle{ S_n=2S_{n-1}+3S_{n-2}}\)
No i teraz trzeba rozwiązać to równanie rekurencyjne. Podstawiam \(\displaystyle{ S_n=q^n}\) i liczę:
\(\displaystyle{ q^n-2q^{n-1}-3q^{n-2}=0}\). Rozwiązania to \(\displaystyle{ q_1=-1,q_2=3}\). Przewidujemy rozwiązanie w postaci: \(\displaystyle{ s_n=c(-1)^n+d \cdot 3^n}\) i podstawiamy warunki początkowe. Otrzymujemy, że: \(\displaystyle{ S_n=(-1/2)(-1)^n+ \frac{3}{2} \cdot 3^n}\).
Czy tak jest dobrze?