Problem 6

Let A and E be opposite vertices of a regular octagon. A frog starts at A and jumps to an adjacent vertex until it reaches E and stops. If a_n counts paths of exactly n jumps ending at E, prove

a_{2n-1}=0

and

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

for

n=1,2,3,\ldots

Step 3 of 5: Step 3

Previous step Next step

a_{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}

Detailed analysis

Let b_m count paths of length m from a neighboring vertex C to E. The two-step transitions give $a_{2n}=2a_{2n-2}+2b_{2n-2}$ and $b_{2n}=2b_{2n-2}+a_{2n-2}$ . Eliminating b yields $u_n=4u_{n-1}-2u_{n-2}$ for $u_n=a_{2n}$ .