$A$ 和 $E$ 为正八边形的一组相对顶点．一只青蛙从 $A$ 点开始跳跃，如果青蛙在任一个不是 $E$ 的顶点，那么它可以跳到两个相邻顶点中的任一个，当它跳到 $E$ 点 时就停在那里，设 ${e}_{n}$ 为经过 $n$ 步达到 $E$ 点的不同路线的条数．求证：${e}_{2n-1}=0$，
${{e}_{2n}}=\dfrac{1}{\sqrt{2}}({{x}^{n-1}}-{{y}^{n-1}}),n=1,2,3,\cdots $，其中 $x=2+\sqrt{2},y=2-\sqrt{2}$．
注意：一个 $n$ 步的路线是指顶点的一个序列 $({P}_{0},P_1\cdots,{P}_{n})$ 满足：
（1）${P}_{0}=A,{P}_{n}=E$；
（2）对每个 $i(0\leqslant i\leqslant n-1),{P}_{i}\ne E$；
（3）对每个 $i(0\leqslant i\leqslant n-1)$，${P}_{i}$ 与 ${P}_{i+1}$ 是正八边形的相邻顶点．（联邦德国）
${{e}_{2n}}=\dfrac{1}{\sqrt{2}}({{x}^{n-1}}-{{y}^{n-1}}),n=1,2,3,\cdots $，其中 $x=2+\sqrt{2},y=2-\sqrt{2}$．
注意：一个 $n$ 步的路线是指顶点的一个序列 $({P}_{0},P_1\cdots,{P}_{n})$ 满足：
（1）${P}_{0}=A,{P}_{n}=E$；
（2）对每个 $i(0\leqslant i\leqslant n-1),{P}_{i}\ne E$；
（3）对每个 $i(0\leqslant i\leqslant n-1)$，${P}_{i}$ 与 ${P}_{i+1}$ 是正八边形的相邻顶点．（联邦德国）
【难度】
【出处】
1979年第21届IMO试题
【标注】
【答案】
略
【解析】
证法一设从 $A$ 出发经过 $n$ 步到达 $B,C,D,A$ 的路线个数分别记为 $b_n,c_n,d_n,a_n$．由对称性，由 $A$ 出发经过 $n$ 步到达 $H,G,F$ 的路线个数也分别是 $b_n,c_n,d_n$．因此有
$e_n=2d_{n-1}$ ①
$c_n=b_{n-1}+d_{n-1}$ ②
$b_n=c_{n-1}+a_{n-1}$ ③
$a_n=2b_{n-1}$ ④
$d_n=C_{n-1}$ ⑤
由上述关系，得
$\begin{aligned}
e_n&=2d_{n-1}\\
&=2c_{n-2}\\
&=2(b_{n-3}+d_{n-3})\\
&=2(c_{n-4}+a_{n-4}+d_{n-3})\\
&=2(2d_{n-3}+2b_{n-5})\\
&=2[2d_{n-3}+2(d_{n-3}-d_{n-5})]\\
&=8d_{n-3}-4d_{n-5}\\
&=4e_{n-2}-2e_{n-4}
\end{aligned}$
由于 $e_1=e_2=e_30,e_4=2$，这些都适合要证明的计数公式．
下面用第二数学归纳法证明这个命题．假定命题对一切 $n\leqslant k$ 已经成立，那么
$e_{2k+1}=4e_{2k-1}-2e_{2k-3}=0$；
$\begin{aligned}
e_{2k+2}&=4e_{2k}-2e_{2k-2}\\
&=\dfrac{4}{\sqrt{2}}(x^{k-1}-y^{k-1})-\dfrac{2}{\sqrt{2}}(x^{k-2}-y^{k-2})\\
&=\dfrac{1}{\sqrt{2}}[(x+y)(x^{k-1}-y^{k-1})-xy(x^{k-2}-y^{k-2})]\\
&=\dfrac{1}{\sqrt{2}}(x^k-y^k)
\end{aligned}$
证毕．
证法二
青蛙不能在跳 $4$ 步之内到达 $E$，故 $e_1=e_2=e_3=0$；易知 $e_4=2$．
从 $A$ 出发作奇数次跳，青蛙只可能到达 $B,D,F,H$ 诸点，不可能到达 $E$，故 $e_{2n-1}=0$．
现用 $c_n$ 表示从 $C$ 点开始跳 $n$ 步最后到 $E$ 点的路线数（这与从 $G$ 点开始一样），易知 $c_2=1$．
青蛙从 $A$ 点起跳，$2$ 步后有四种可能：$A\rightarrow B\rightarrow C,A\rightarrow B\rightarrow A ,A\rightarrow B \rightarrow G,A\rightarrow H\rightarrow A$．故从 $A$ 到 $E$ 跳 $n$ 步的路线数等于从 $C$ 到 $E$ 跳 $n-2$ 步和从 $A$ 到 $E$ 跳 $n-2$ 步路数线之和的两倍，即
$e_n=2(c_{n-2}+e_{n-2})$ ①
当青蛙从 $C$ 开始跳了若干（$>2$）步，前两次跳，要么落在 $A$ 点，要么落在 $C$ 点．因此 $C_n(n>2)$，等于从 $A$ 起跳 $n-2$ 步到 $E$ 的路线数加上从 $C$ 起跳跳 $n-2$ 次到 $E$ 点的路线数的两倍（因为前两跳可能为 $C\rightarrow B\rightarrow C$ 或 $C\rightarrow D\rightarrow C$）．故
$c_n=2c_{n-2}+e_{n-2},n>2$ ②
易知 $c_{2n-1}=e_{2n-1}=0$，故我们只对 $c_{2n}$ 和 $e_{2n}$ 感兴趣．① 和 ② 用矩阵表示就是
$\begin{pmatrix}
e_{2n} \\
c_{2n}
\end{pmatrix}=\begin{pmatrix}2 & 2 \\
1 & 2
\end{pmatrix}\begin{pmatrix}e_{2n-2} \\
c_{2n-2}
\end{pmatrix}$
$\begin{pmatrix}
e_2 \\
c_2
\end{pmatrix}=\begin{pmatrix}0 \\
1
\end{pmatrix}$
$\begin{pmatrix}
2 & 2 \\
1 & 2
\end{pmatrix}$ 的特征方程为
$\begin{vmatrix}
2-\lambda & 2 \\
1 & 2-\lambda
\end{vmatrix}=\lambda^2-4\lambda+2=0$
其特征值为 $\lambda_1=2+\sqrt{2},\lambda_2=2-\sqrt{2}$．
为求特征向量 $\overline{v_1},\overline{v_2}$，也就是求解
$\begin{pmatrix}
2 & 2 \\
1 & 2
\end{pmatrix}\begin{pmatrix}\alpha_i \\
\beta_i
\end{pmatrix}=\lambda_i\begin{pmatrix}\alpha_i \\
\beta_i
\end{pmatrix},i=1,2$
解得
$\dfrac{\alpha_1}{\beta_1}=\sqrt{2},\dfrac{\alpha_2}{\beta_2}=-\sqrt{2}$
令 $\overline{v_1}=\dfrac{1}{\sqrt{2}}\begin{pmatrix}
1 \\
\dfrac{1}{\sqrt{2}}
\end{pmatrix},\overline{v_2}=\dfrac{1}{\sqrt{2}}\begin{pmatrix}-1 \\
\dfrac{1}{\sqrt{2}}
\end{pmatrix}$
则 $\dfrac{1}{\sqrt{2}}\begin{pmatrix}
0\\
1
\end{pmatrix}=\lambda_1\overline{v_1}+\lambda_2\overline{v_2}$
$\begin{pmatrix}
e_{2n} \\
c_{2n}
\end{pmatrix}=\begin{pmatrix}2&2 \\
1&2
\end{pmatrix}^{n-1}\begin{pmatrix}e_{2} \\
c_{2}
\end{pmatrix}=\lambda^{n-1}_1\overline{v_1}+\lambda^{n-1}_2\overline{v_2}$
由此易得
$\begin{aligned}
e_{2n}&=\dfrac{1}{\sqrt{2}}[(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}]\\
&=\dfrac{1}{\sqrt{2}}(x^{n-1}-y^{n-1})
\end{aligned}$
答案
解析
备注
