Finding general expression in terms of number of steps

Question

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 a(n) be the number of distinct paths of exactly n jumps ending at E. Find a(n)

Is it right if I conclude that number of steps has to be an even number ? Also I don't know how to go further with that except I think recursion is involved.

P.S. I'm having trouble solving questions in probability and combinatorics where recursions are involved like finding expected value ones. Can you provide me suggest me some links/books through which I can understand it better. Thanks

Answer 1

First of all, let me note that this exact problem (finding and proving a closed form for $a(n)$) is IMO 1979 Q6, and $a(2n)$ is in the OEIS as A060995. The solution below is entirely mine; I did not see others' answers while writing it.

The frog moves along this octagon:

B--C--D
|     |
A     E
|     |
H--G--F

We can flatten the octagon out, since the frog stops when it reaches E. Now the set-up looks like a line (I've disambiguated the two E's into X and Y):

X--D--C--B--A--H--G--F--Y

After taking an odd number of steps, the frog must be on D, B, H or G; after an even number of steps it must be on one of the other vertices – X, C, A, G or Y. In other words, the frog must take an even number of steps to reach its goal, as you expected. Accordingly we can treat the steps in pairs, where after each pair the frog has either stayed put (which can be done in two ways), moved two spaces left (one) or moved two spaces right (one).

Let $C_{2n},A_{2n},G_{2n}$ denote the number of ways the frog can reach the respective vertices after $2n$ steps. They satisfy the characteristic equations $$\begin{align} C_n&=2C_{n-2}+A_{n-2}\\ A_n&=C_{n-2}+2A_{n-2}+G_{n-2}\\ G_n&=A_{n-2}+2G_{n-2} \end{align}\\ C_0=0,A_0=1,G_0=0$$ which can be represented in matrix form as $$\begin{pmatrix}C_{2n}\\A_{2n}\\G_{2n}\end{pmatrix}= \begin{pmatrix}2&1&0\\1&2&1\\0&1&2\end{pmatrix}^n\begin{pmatrix}0\\1\\0\end{pmatrix}$$ The $a(n)$ in the question is $C_{n-2}+G_{n-2}$, or alternatively $2C_{n-2}$ since the set-up is symmetric around A. Diagonalising the square matrix yields a closed form for $C_{2n}$: $$C_{2n}=\frac{(2+\sqrt2)^n-(2-\sqrt2)^n}{2\sqrt2}$$ Therefore $a(0)=0$, $$a(2n)=\frac{(2+\sqrt2)^{n-1}-(2-\sqrt2)^{n-1}}{\sqrt2},\ n>0$$ and $a(2n+1)=0$.

---

Many combinatorial problems like this, where a closed form is requested for the number of ways to traverse a graph, can be solved by a similar process:

1. Assign sequences that represent the number of ways you can reach each place you can be and write the necessary characteristic equations.
2. Most of the time, these equations are linear, which means they can be rewritten as a matrix.
3. Diagonalising the matrix yields the required closed form.

Answer 2

Let us place $A$ at position $0$, and $E$ at position $-4,4$ respectively. Now let $3^-_n,2^-_n,1^-_n,0_n,1_n,2_n,3_n$ denote the number of ways to have ended up at position $-3,-2,-1,0,1,2,3$ respectively in $n$ steps. Clearly we have the seeds: $$ \begin{align} 3^-_0&=0\\ 2^-_0&=0\\ 1^-_0&=0\\ 0_0&=1\\ 1_0&=0\\ 2_0&=0\\ 3_0&=0\\ \end{align} $$ and the recurrence relations $$ \begin{align} 3^-_{n+1}&=2^-_n\\ 2^-_{n+1}&=3^-_n+1^-_n\\ 1^-_{n+1}&=^-2_n+0_n\\ 0_{n+1}&=1^-_n+1_n\\ 1_{n+1}&=0_n+2_n\\ 2_{n+1}&=1_n+3_n\\ 3_{n+1}&=2_n \end{align} $$ so basically we can express it as follows: $$ \begin{pmatrix} 3^-_n\\ 2^-_n\\ 1^-_n\\ 0_n\\ 1_n\\ 2_n\\ 3_n \end{pmatrix} = \begin{pmatrix} 0&1&0&0&0&0&0\\ 1&0&1&0&0&0&0\\ 0&1&0&1&0&0&0\\ 0&0&1&0&1&0&0\\ 0&0&0&1&0&1&0\\ 0&0&0&0&1&0&1\\ 0&0&0&0&0&1&0 \end{pmatrix}^n \begin{pmatrix} 0\\ 0\\ 0\\ 1\\ 0\\ 0\\ 0\\ \end{pmatrix} $$ and finally $a(n)=3^-_{n-1}+3_{n-1}$.