Example 3 Color each vertex of an $n(n \geqslant 3)$-sided polygon with one color, such that the endpoints of the same edge have different colors. If there are $m(m \geqslant 3)$ colors available, then the total number of different coloring methods is
$$
b_{n}=(m-1)\left[(m-1)^{n-1}+(-1)^{n}\right] .
$$
```
1 Example 3's two recurrence equations have the first recurrence equation as follows:
b
When n=3, as shown in Figure 2(a), A1 has m colorings, A2 has m-1 colorings, and A3 has m-2 colorings. Thus,
When n=4, as shown in Figure 2(b), connecting A1 and A3 divides the quadrilateral A1A2A3A4 into two triangles. If A1 and A3 are different colors, then triangle A1A2A3 has b3 colorings, and A4 has m-2 colorings; if A1 and A3 are the same color, then A1 has m colorings, A2 and A3 each have m-1 colorings. Thus,
b4 = b3(m-2) + m(m-1)^2
= m(m-1)[(m-2)^2 + (m-1)]
= m(m-1)(m^2 - 3m + 3)
When n≥5, as shown in Figure 2(c), connecting A1 and An-1 divides the n-sided polygon into an (n-1)-sided polygon and a triangle. If A1 and An-1 are different colors, the (n-1)-sided polygon has (m-1)bn-1 colorings, and An has m-1 colorings different from A1, resulting in
(m-1)bn-1
Combining the two cases, the recurrence relation is
bn = (m-1)bn-1 + (m-1)bn-2
The second recurrence equation is as follows:
When n>3, A1 has m colorings, A2 must be a different color from A1, so it has m-1 colorings, and A3, A4, ..., An-1 each have m-1 colorings. Finally, consider An; if it is a different color from An-1, it also has m-1 colorings, totaling
To ensure An is a different color from A1,
but this calculation can be divided into two categories:
(1) An is a different color from A1, which meets the requirement, with
(2) An is the same color as A1, which does not meet the requirement, but can be merged into one point, resulting in
colorings. Thus,
b1
These two recurrence equations, though different in form, can be transformed into each other.
From equation (1), we have
bn + bn-1 = (m-1)(bn-1 + bn-2)
This indicates that c = cn = bn-1 + bn is a geometric sequence with a common ratio q = 1, and the recurrence can derive equation (2).
Conversely, from equation (2), we have
and (m-1)(bn-1 + bn-2) = m(m-1)^(n-1)
Subtracting these gives equation (1).
Solution 1: Characteristic Equation Method
\sum
Then (-1)^n bn + b1 = (1-m)^n - (1-m)
Thus, bn = (m-1)^n + (m-1)(-1)^n
Solution 6: Iteration
From equation (2), iterating step by step gives
bn = m(m-1)^(n-1) - bn-1
= m(m-1)^(n-1) - [m(m-1)^(n-2) - bn-2]
= ...
= m(m-1)^(n-1) - m(m-1)^(n-2) + ... + (-1)^(n-4)[m(m-1)^3 - b3]
= m(m-1)^(n-1) - m(m-1)^(n-2) + ... + (m-1)^2 + (-1)^(n-2)m(m-1)
= (-1)^(n-1)m[(1-m)^(n-1) + (1-m)^(n-2) + ... + (1-m)^2 + (1-m)]
= (m-1)^n + (m-1)(-1)^n
Note: This iteration process can be rewritten as an identity.
Solution 7: From equation (2) and b1 = 0, we have
= (-1)^(n-1)m[(1-m)^(n-1) + (1-m)^(n-2) + ... + (1-m)^2 + (1-m)]
= (m-1)^n + (m-1)(-1)^n
```