3. 20 Let $[x]$ denote the greatest integer not exceeding $x$. Try to compute the sum $\sum_{k=0}^{\infty}\left[\frac{n+2^{k}}{2^{k+1}}\right]$ for any positive integer $n$.
[Solution] First, we prove that for all real numbers $x$, the equation
$$\left[x+\frac{1}{2}\right]=[2 x]-[x]$$
holds.

In fact, let $x=[x]+\alpha$, then $0 \leqslant \alpha<1$,
so $\left[x+\frac{1}{2}\right]=\left[[x]+\alpha+\frac{1}{2}\right]$
$$=[x]+\left[\alpha+\frac{1}{2}\right]$$
$$\begin{aligned}
{[2 x]-[x] } & =[2[x]+2 \alpha]-[[x]+\alpha] \\
& =[x]+[2 \alpha]-[\alpha]
\end{aligned}$$

Thus, equation (1) is equivalent to
$$\left[\alpha+\frac{1}{2}\right]=[2 \alpha]-[\alpha]$$

where $0 \leqslant \alpha<1$.
When $0 \leqslant \alpha<\frac{1}{2}$, both sides of the equation are 0, and when $\frac{1}{2} \leqslant \alpha<1$, both sides of the equation are 1. Therefore, equation (2) holds, and thus equation (1) also holds.

From equation (1), we have
$$\begin{aligned}
& {\left[\frac{n+2^{k}}{2^{k+1}}\right]=\left[\frac{n}{2^{k+1}}+\frac{1}{2}\right] } \\
= & {\left[2 \cdot \frac{n}{2^{k+1}}\right]-\left[\frac{n}{2^{k+1}}\right] } \\
= & {\left[\frac{n}{2^{k}}\right]-\left[\frac{n}{2^{k+1}}\right] }
\end{aligned}$$

Therefore,
$$\begin{aligned}
& \sum_{k=0}^{\infty}\left[\frac{n+2^{k}}{2^{k+1}}\right] \\
= & \left([n]-\left[\frac{n}{2}\right]\right)+\left(\left[\frac{n}{2}\right]-\left[\frac{n}{2^{2}}\right]\right)+\left(\left[\frac{n}{2^{2}}\right]-\left[\frac{n}{2^{3}}\right]\right)+\cdots
\end{aligned}$$

Since for a fixed natural number $n$, when $k$ is sufficiently large, $n<2^{k}$, and $\left[\frac{n}{2^{k}}\right]=0$, the above expression becomes
$$\sum_{k=0}^{\infty}\left[\frac{n+2^{k}}{2^{k+1}}\right]=[n]=n$$