$4 \cdot 216$ Try to find the number of all such positive integers: in their representation in base $n$, all digits are different, and each digit, except the leftmost one, differs from some digit to its left by $\pm 1$ (express the answer as a simple explicit function of $n$), and prove your conclusion.
[Solution] Although 0 cannot be the first digit, we first do not consider whether the first digit is 0, and define $F(n)$ as the number of positive integers that meet the conditions in the $n$-ary system, including those with the first digit being 0. For example,
$$\begin{array}{l}
F(1)=1,[0] \\
F(2)=4,[0,1,01,10] \\
F(3)=11,[0,1,2,01,10,12,21,012,102,120,210]
\end{array}$$

Now we establish the recurrence relation for $F(n+1)$.
Since the rightmost digit in a number string in the $(n+1)$-ary system can only be the largest or smallest digit in the string, we categorize them into three types:
(1) Single digits: $0,1,2, \cdots, n$;
(2) Append a digit to the right of each $n$-ary number string, which is one more than the largest digit in the original string.
(3) Add 1 to each digit of each $n$-ary number string, then append a digit to the right, which is one less than the smallest digit on the left.

Thus, we have $F(n+1)=n+1+2 F(n)$,
i.e., $\square$
$$F(n+1)+(n+3)=2[F(n)+n+2]$$

Therefore, $F(n+1)+(n+3)=2^{n}[F(1)+1+2]$.
Since $F(1)=1$,
we have $F(n+1)+n+3=2^{n+2}$.
Thus, $F(n)=2^{n+1}-n-2$.
Since numbers with 0 as the first digit are not allowed, such numbers in the $n$-ary system are
$$0,01, \cdots, 012 \cdots(n-1)$$

Therefore, the number of positive integers that meet the conditions is:
$$F(n)=2^{n+1}-2 n-2$$