Example 5 Given an integer $n \geqslant 2$. For the set of integer points in the Cartesian coordinate system
$$
A=\{(a, b) \mid a, b \in\{1,2, \cdots, n\}\}
$$

each point is colored one of three colors: red, yellow, or blue, and it satisfies: for any $a, b \in\{1,2, \cdots, n-1\}$, if $(a, b)$ and $(a+1, b)$ are the same color, then $(a, b+1)$ and $(a+1, b+1)$ are also the same color. Find the total number of different coloring methods. ${ }^{[3]}$
(2015, China Southeast Mathematical Olympiad)
For $k=1,2, \cdots, n$, define the set of integer points
$$
A_{k}=\{(k, b) \mid b \in\{1,2, \cdots, n\}\} \text {. }
$$

Color $A_{1}, A_{2}, \cdots, A_{n}$ sequentially (to complete the coloring of $A$). Let the number of ways to color $A_{k}$ during these $n$ steps be denoted as $N_{k}(k=1,2, \cdots, n)$.

First, color $A_{1}$: Since each integer point $(1, b)$ $(b=1,2, \cdots, n)$ has three coloring options, we have $N_{1}=3^{n}$.
Assume that $A_{1} \cup \cdots \cup A_{r}(1 \leqslant r \leqslant n-1)$ has been colored.
Next, color $A_{r+1}$.
If for each $s=1,2, \cdots, n$, $(r+1, s)$ and $(r, s)$ are different colors, then each point in $A_{r+1}$ has two coloring options, resulting in $2^{n}$ ways to color $A_{r+1}$ in this case.

Now consider the following scenario: For some $s(1 \leqslant s \leqslant n)$, $(r+1, s)$ and $(r, s)$ are the same color, but there is no positive integer $u$ less than $s$ such that $(r+1, u)$ and $(r, u)$ are the same color. In this case, the $s-1$ points $(r+1, u)(1 \leqslant u \leqslant s-1)$ each have two coloring options (if $s=1$, there are no points to color, which is considered one way); noting that $(r+1, s)$ and $(r, s)$ are the same color, and according to the coloring rule, it follows that $(r+1, v)$ and $(r, v)$ are the same color, where $v$ takes the values $s+1, s+2, \cdots, n$ sequentially. In this case, there are $2^{s-1}$ ways to color $A_{r+1}$.
In summary, the number of ways to color $A_{r+1}$ is
$$
N_{r+1}=2^{n}+\sum_{s=1}^{n} 2^{s-1}=2^{n+1}-1 \text {. }
$$

By the multiplication principle, the number of ways to color $A$ is
$$
N_{1} N_{2} \cdots N_{n}=3^{n}\left(2^{n+1}-1\right)^{n-1} \text {. }
$$

[Note] The solution does not explicitly show a recurrence relation, but in fact, when adding a column to the right of the set of integer points with $n$ rows and $r$ columns, expanding it to a set of integer points with $n$ rows and $r+1$ columns, the number of coloring ways is multiplied by $2^{n+1}-1$. In other words, under the conditions of this problem, the application of the multiplication principle in the final step is based on a simple structural recurrence relation.