Uluslararası Matematik Olimpiyatı 1979 Soru 6

[ERhan ERdoğan]

$A$ ve $E$ düzgün bir sekizgenin karşı iki köşesi olsun. Bir kurbağa, $A$ dan başlayarak zıplıyor. Kurbağa, sekizgenin $E$ hariç her köşesinden, komşu köşelerden birine zıplayabiliyor. $E$ ye gelince ise zıplamayı bırakıyor. $a_n$ ile tam olarak $n$ zıplama sonucu $E$ ye gelebilmeyi mümkün kılan farklı yolların sayısını gösterelim. $x=2+\sqrt 2$ ve $y=2-\sqrt 2$ olmak üzere; $a_{2n-1}=0$ ve her $n=1,2,3,\dots$ için $$a_{2n} = \dfrac{1}{\sqrt 2}(x^{n-1}-y^{n-1})$$ olduğunu kanıtlayınız.
Not: $n$ zıplamalı bir yol, köşelerden oluşan bir $(P_0,\dots, P_n)$ dizisi olup aşağıdaki koşulları sağlar:

• $P_0 = A$, $P_n=E$,
• her $0\leq i \leq n-1$ için, $P_i \neq E$,
• her $0\leq i \leq n-1$ için, $P_i$ ile $P_{i+1}$ komşudur.