Example 3 Let $g(k)$ denote the greatest odd divisor of the positive integer $k$
$$
\begin{aligned}
\text { (for example, } g(3) & =3, g(20)=5) . \text { Find } \\
f(n) & =g(1)+g(2)+g(3)+\cdots+g\left(2^{n}\right) .
\end{aligned}
$$
For odd $k$, we have $g(k)=k$.
For any $k \in \mathbf{Z}_{+}$, we have
$$
g(2 k)=g(k) \text {. }
$$
$$
\begin{array}{l}
\text { Then } f(n)=1+3+5+\cdots+\left(2^{n}-1\right)+ \\
g(2)+g(4)+\cdots+g\left(2^{n}\right) \\
=\frac{\left(1+2^{n}-1\right) 2^{n-1}}{2}+g(1)+g(2)+\cdots+g\left(2^{n-1}\right) \\
=4^{n-1}+f(n-1) .
\end{array}
$$

Notice that,
$$
\begin{array}{l}
f(2)-f(1)=4, \\
f(3)-f(2)=4^{2}, \\
\ldots . .
\end{array}
$$
$$
f(n)-f(n-1)=4^{n-1} \text {. }
$$

Adding all these equations, we get
$$
f(n)-f(1)=4+4^{2}+\cdots+4^{n-1} \text {. }
$$

Since $f(1)=g(1)+g(2)=1+1=2$, we have
$$
f(n)=\frac{4^{n}-4}{3}+2=\frac{4^{n}+2}{3} .
$$