Let A and E be opposite vertices of an octagon. A frog starts at vertex A. From any vertex except E it jumps to one of the two adjacent vertices. When it reaches E it stops. Let an be the number of distinct paths of exactly n jumps ending at E. Prove that:
a2n-1 = 0
a2n = (2 + Ö2)n-1/Ö2 - (2 - Ö2)n-1/Ö2.
Solution
Each jump changes the parity of the shortest distance to E. The parity is initially even, so an odd number of jumps cannot end at E. Hence a2n-1 = 0.
We derive a recurrence relation for a2n. This is not easy to do directly, so we introduce bn which is the number of paths length n from C to E. Then we have immediately:
a2n = 2a2n-2 + 2b2n-2 for n > 1
b2n = 2b2n-2 + a2n-2 for n > 1
Hence, using the first equation: a2n - 2a2n-2 = 2a2n-2 - 4a2n-4 + 2b2n-2 - 4b2n-4 for n > 2. Using the second equation, this leads to: a2n = 4a2n-2 - 2a2n-4 for n > 2. This is a linear recurrence relation with the general solution: a2n = a(2 + Ö2)n-1 + b(2 - Ö2)n-1. But we easily see directly that a4 = 2, a6 = 8 and we can now solve for the coefficients to get the solution given.