$3 \cdot 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]$
$$
\begin{aligned}
& =[x]+\left[\alpha+\frac{1}{2}\right], \\
{[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,
$\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
$$

Since for a fixed natural number $n$, when $k$ is sufficiently large, $n<2^{k},\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 .
$$