9. Let $f, g: \mathbf{N} \rightarrow \mathbf{N}, f(n)=2 n+1, g(1)=3$ and
$$
g(n) \geqslant f[g(n-1)], \forall n \geqslant 2 .
$$

Find $g(n)$.
9. Given $f(n)=2 n+1$, by taking $n=1,2,3, \cdots$ in (1), we can find
$$
\begin{array}{l} 
g(1) \geqslant 3, \\
g(2) \geqslant 2 g(1)+1 \geqslant 3 \times 2+1 \\
g(3)=2 g(2)+1 \geqslant 2 \cdot(3 \times 2+1)+1 \geqslant 3 \times 2^{2}+2+1, \\
g(4) \geqslant 2 g(3)+1=2 \cdot\left(3 \times 2^{2}+2+1\right)+1 \geqslant 3 \times 2^{3}+2^{2}+2+1 \\
\cdots \cdots \\
g(n) \geqslant 3 \times 2^{n-1}+2^{n-2}+\cdots+2+1 \\
=3 \times 2^{n-1}+2^{n-2}\left(1+\frac{1}{2}+\frac{1}{2^{2}}+\cdots+\frac{1}{2^{n-2}}\right) \\
=3 \times 2^{n-1}+\frac{2^{n-2}\left[1-\left(\frac{1}{2}\right)^{n-1}\right]}{1-\frac{1}{2}} \\
=3 \times 2^{n-1}+\frac{2^{n-2}-\frac{1}{2}}{\frac{1}{2}} \\
=3 \times 2^{n-1}+2^{n-1}-1
\end{array}
$$

Now we prove this conclusion is correct using mathematical induction.

Obviously, substituting $n=1$ into (2), we get $g(1) \geqslant 3$.
Assume (2) holds for $n=k$, then for $n=k+1$.
$$
g(k+1) \geqslant 2 g(k)+1 \geqslant 2\left(3 \times 2^{k-1}+2^{k-2}+\cdots+2+1\right)+1=2\left(2^{k+1}-1\right)+1=2^{k+1}+1-1,
$$

Thus, by mathematical induction, the formula is proven to be correct.