MathLabs

第6题

设 A,E 是正八边形的对顶点。青蛙从 A 出发，跳到相邻顶点，抵达 E 后停止。若恰好跳 n 步到达 E 的路径数为 a_n，证明 a2n−1=0a_{2n-1}=0 且 a2n=(2+2)n−1−(2−2)n−12a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}}，其中 n=1,2,3,…n=1,2,3,\ldots。
第 3/5 步：第3步
上一步下一步
a2n=2a2n−2+2b2n−2,b2n=2b2n−2+a2n−2⟹un=4un−1−2un−2a_{2n}=2a_{2n-2}+2b_{2n-2},\quad b_{2n}=2b_{2n-2}+a_{2n-2}\Longrightarrow u_n=4u_{n-1}-2u_{n-2}
详细分析

令 b_m 表示从相邻顶点 C 到 E 的 m 步路径数。两步转移给出 a2n=2a2n−2+2b2n−2a_{2n}=2a_{2n-2}+2b_{2n-2} 与 b2n=2b2n−2+a2n−2b_{2n}=2b_{2n-2}+a_{2n-2}。消去 b 得 un=4un−1−2un−2u_n=4u_{n-1}-2u_{n-2}，其中 un=a2nu_n=a_{2n}。