3. (7 points) Four mole burrows $A, B, C, D$ are connected sequentially by three tunnels. Each minute, the mole runs through a tunnel to one of the adjacent burrows. In how many ways can the mole get from burrow $A$ to $C$ in 12 minutes?

![](https://cdn.mathpix.com/cropped/2024_05_06_d5d5613c0f147d056827g-38.jpg?height=103&width=834&top_left_y=288&top_left_x=608)
Answer: 144

Solution: After an even number of minutes, the mole can be only at vertices $A$ and $C$. Let $a_{k}$ and $c_{k}$ denote the number of paths of length $2 k$ leading from $A$ to $A$ and from $A$ to $C$, respectively. Note that the equalities $c_{k+1}=a_{k}+2 c_{k}, a_{k+1}=a_{k}+c_{k}$ hold. From this, $c_{k+2}=a_{k+1}+$ $2 c_{k+1}=a_{k}+c_{k}+2 c_{k+1}=c_{k+1}-2 c_{k}+c_{k}+2 c_{k+1}=3 c_{k+1}-c_{k}$.

| $C_{0}$ | $C_{1}$ | $C_{2}$ | $C_{3}$ | $C_{4}$ | $C_{5}$ | $C_{6}$ | $C_{7}$ | $C_{8}$ | $C_{9}$ | $C_{10}$ | $C_{11}$ | $C_{12}$ | $C_{13}$ | $C_{14}$ | $C_{15}$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 0 | 1 | 3 | 8 | 21 | 55 | 144 | 377 | 987 | 2584 | 6765 | 17711 | 46368 | 121393 | 317811 | 832040 |