Example 2-40 An octagon, as shown in Figure 2-10. A drunk man starts from point 1, wandering along the edges of the octagon. Except for point 5, at each vertex he has two choices: move forward to the next station or move backward to the previous station. Reaching a station counts as one step, and he stops when he reaches point 5. Try to find, starting from point 1, how many paths there are to reach point 5 in $n$ steps.
Let $a_{n}$ denote the number of paths from point 1 to point 5 in $n$ steps, and $b_{n}$ denote the number of paths from point 3 or 7 to point 5 in $n$ steps. Starting from point 1 or 3, it must take an even number of steps to reach point 5.

Since $1 \rightarrow 2 \rightarrow 1, 1 \rightarrow 8 \rightarrow 1, 1 \rightarrow 2 \rightarrow 3, 1 \rightarrow 8 \rightarrow 7, 3 \rightarrow 2 \rightarrow 3, 3 \rightarrow 4 \rightarrow 3, 3 \rightarrow 2 \rightarrow 1$, we have
$$
\begin{array}{l}
a_{2 n}=2 a_{2 n-2}+2 b_{2 n-2} \\
b_{2 n}=a_{2 n-2}+2 b_{2 n-2} \\
a_{2}=0, \quad a_{4}=2, \quad b_{2}=1 \\
a_{2 n+1}=b_{2 n \pm 1}=0
\end{array}
$$

Let $A_{n}=a_{2 n}, B_{n}=b_{2 n}$, then we get
$$
\begin{array}{l}
x: B_{1}=A_{0}+2 B_{0} \\
x^{2}: B_{2}=A_{1}+2 B_{1} \\
x^{3}: B_{3}=A_{2}+2 B_{2} \\
\text { +) } \quad \text { ! } \\
H(x)-\frac{1}{2}=x G(x)+2 x H(x) \\
\end{array}
$$

Solve the system of equations
$$
\begin{aligned}
& \left\{\begin{array}{l}
(1-2 x) G(x)-2 x H(x)=0 \\
x G(x)-(1-2 x) H(x)=-\frac{1}{2}
\end{array}\right. \\
D= & \left|\begin{array}{cc}
1-2 x & -2 x \\
x & -(1-2 x)
\end{array}\right|=-(1-2 x)^{2}+2 x^{2} \\
= & {[1-(2-\sqrt{2}) x][1-(2+\sqrt{2}) x] } \\
G(x)= & \frac{1}{[1-(2+\sqrt{2}) x][1-(2-\sqrt{2}) x]}\left|\begin{array}{cc}
0 & -2 x \\
-\frac{1}{2} & -1+2 x
\end{array}\right| \\
= & \frac{x}{[1-(2-\sqrt{2}) x][1-(2+\sqrt{2}) x]} \\
= & \frac{A}{[1-(2-\sqrt{2}) x]}+\frac{B}{1-(2+\sqrt{2}) x}
\end{aligned}
$$
$$
\begin{aligned}
A_{n} & =A(2-\sqrt{2})^{n-1}+B(2+\sqrt{2})^{n-1} \\
A_{1} & =0, \quad A+B=0 \\
A_{2} & =2, \quad(A+B)-\sqrt{2}(A-B)=2, \quad A-B=-\sqrt{2} \\
A & =-\frac{1}{\sqrt{2}}, \quad B=+\frac{1}{\sqrt{2}} \\
a_{2 n} & =A_{n}=\frac{1}{\sqrt{2}}\left\{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}\right\}
\end{aligned}
$$

Solution method two: From
$$
\left\{\begin{array}{l}
a_{2 n}=2 a_{2 n-2}+2 b_{2 n-2} \\
b_{2 n}=a_{2 n-2}+2 b_{2 n-2}
\end{array}\right.
$$

By ( * ) we get
$$
\begin{array}{l}
2 b_{2 n-2}=a_{2 n}-2 a_{2 n-2} \\
b_{2 n}=\frac{1}{2}\left[a_{2 n+2}-2 a_{2 n}\right]
\end{array}
$$

Substitute into ( ** ) we get
$$
\frac{1}{2}\left[a_{2 n+2}-2 a_{2 n}\right]=a_{2 n-2}+a_{2 n}-2 a_{2 n-2}=a_{2 n}-a_{2 n-2}
$$

or

Let $d_{n}=a_{2 n}$, then we get

Characteristic equation
$$
\begin{array}{c}
a_{2(n+1)}-4 a_{2 n}+2 a_{2(n-1)}=0 \\
d_{n+1}-4 d_{n}+2 a_{n-1}=0
\end{array}
$$
$$
\begin{array}{c}
x^{2}-4 x+2=0, \quad[x-(2+\sqrt{2})][x-(2-\sqrt{2})]=0 \\
a_{2 n}=d_{n}=A(2+\sqrt{2})^{n}+B(2-\sqrt{2})^{n}
\end{array}
$$

According to $a_{2}=0$ and $a_{4}=2$, we get $d_{1}=0, d_{2}=2$.
$$
\begin{array}{l}
A(2+\sqrt{2})+B(2-\sqrt{2})=2(A+B)+\sqrt{2}(A-B)=0 \\
A(2+\sqrt{2})^{2}+B(2-\sqrt{2})^{2}=4(A+B)+4 \sqrt{2}(A-B)+2(A+B)=2 \\
\left\{\begin{array}{l}
2(A+B)+\sqrt{2}(A-B)=0 \\
6(A+B)+4 \sqrt{2}(A-B)=2
\end{array}\right.
\end{array}
$$

Solving the system of equations, we get
and
$$
\begin{array}{c}
\left\{\begin{array}{l}
A+B=-1 \\
A-B=2 / \sqrt{2}
\end{array}\right. \\
2=(2-\sqrt{2})(2+\sqrt{2})
\end{array}
$$

So
$$
\left\{\begin{array}{l}
A=\frac{1}{\sqrt{2}}\left(\frac{1}{2+\sqrt{2}}\right) \\
B=-\frac{1}{\sqrt{2}}\left(\frac{1}{2-\sqrt{2}}\right)
\end{array}\right.
$$