第6問

正八角形の対頂点を A,E とする。蛙は A から出発し、E に着くまで隣接頂点へ跳ぶ。ちょうど n 回で E に着く道の数を a_n とすると、

a_{2n-1}=0

および

a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}}

（

n=1,2,3,\ldots

）を証明せよ。

ステップ 1/5: 第1段階

a_{2n-1}=0

詳しい解説

八角形グラフは二部グラフであり、A と E は同じ部分に属するので、A から E への道の長さはすべて偶数である。したがって $a_{2n-1}=0$ 。