1:
Z góry przepraszam za zawiłość...
Literacja \(\displaystyle{ A, B, C ,D ,E ,F ,G, H}\) zgodnie z ruchem wskazówek zegara.
Jeżeli ruch zgodnie z ruchem wskazówek utożsamimy z dodawaniem jedynki, a przeciwnie do ruchu wskazówek z odejmowaniem, to naszym celem jest dotarcie do \(\displaystyle{ 4}\) zaczynając od zera. Ponieważ ruchy zgodnie i przeciwnie dają zerowy wkład i jest ich parzysta liczba, a do osiągnięcia jest parzysta liczba, to i parzyście wiele ruchów jest potrzebnych do osiągnięcia czwórki, czyli wierzchołka \(\displaystyle{ E}\).
Ręcznie wyznaczamy \(\displaystyle{ a_{4}=2}\): ciągi \(\displaystyle{ (A,B,C,D,E), (A,H,G,F,E)}\) oraz \(\displaystyle{ a_{6}=8}\) - tutaj mamy \(\displaystyle{ (A, B, D, C, D, E), (A, B, C, B, C, D, E), (A, B, A, B, C, D, E), (A, B, A, H, G, F, E)}\) i symetrycznie w przeciwną stronę.
Zauważmy teraz, że \(\displaystyle{ a_{2n}=4a_{2n-2}-2a_{2n-4}}\), gdyż:
Literacja \(\displaystyle{ A, B, C ,D ,E ,F ,G, H}\) zgodnie z ruchem wskazówek zegara.
Jeżeli ruch zgodnie z ruchem wskazówek utożsamimy z dodawaniem jedynki, a przeciwnie do ruchu wskazówek z odejmowaniem, to naszym celem jest dotarcie do \(\displaystyle{ 4}\) zaczynając od zera. Ponieważ ruchy zgodnie i przeciwnie dają zerowy wkład i jest ich parzysta liczba, a do osiągnięcia jest parzysta liczba, to i parzyście wiele ruchów jest potrzebnych do osiągnięcia czwórki, czyli wierzchołka \(\displaystyle{ E}\).
Ręcznie wyznaczamy \(\displaystyle{ a_{4}=2}\): ciągi \(\displaystyle{ (A,B,C,D,E), (A,H,G,F,E)}\) oraz \(\displaystyle{ a_{6}=8}\) - tutaj mamy \(\displaystyle{ (A, B, D, C, D, E), (A, B, C, B, C, D, E), (A, B, A, B, C, D, E), (A, B, A, H, G, F, E)}\) i symetrycznie w przeciwną stronę.
Zauważmy teraz, że \(\displaystyle{ a_{2n}=4a_{2n-2}-2a_{2n-4}}\), gdyż:
- skoro ciąg ma się kończyć literami \(\displaystyle{ C, D, E}\), to dwiema poprzednimi moga być tylko \(\displaystyle{ A, B}\) lub \(\displaystyle{ C, D}\). Analogicznie dla końcówki \(\displaystyle{ G, F ,E}\); daje to łącznie cztery sposoby,
- w dwóch przypadkach z poprzedniego punktu (tam, gdzie krążymy w kółko) tracimy dwie możliwości wiodące w \(\displaystyle{ 2n-4}\) krokach;
\(\displaystyle{ \begin{cases} a_{2n}=4a_{2n-2}-2a_{2n-4} \\ a_4=2\\ a_6=8 \end{cases}}\)
Podstawiamy \(\displaystyle{ b_n=a_{2n}}\) i mamy\(\displaystyle{ \begin{cases} b_{n}=4b_{n-1}-2b_{n-2} \\ b_2=2\\ b_3=8 \end{cases}}\).
Rozwiązujemy ją standardowo, tj równaniem charakterystycznym itp. Pomijam rutynę. Wynik końcowy to\(\displaystyle{ b_n=\frac{1}{\sqrt{2}}\left((2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}\right)}\)
i jak się przyjrzymy uważnie, pokrywa się to z równością z tezy.