Let $n \in \mathbb{N}^{*}$. Find the number of polynomials $P$ with coefficients in $\{0,1,2,3\}$ such that $P(2)=$ $n$.
First, note that we can replace $P$ by a formal series since if $P(2) = n$, then only a finite number of coefficients of $P$ (bounded by $\log_{2} n$) will be non-zero, and $P$ will correspond to a polynomial. If we write $P = a_{0} + a_{1} X + \ldots$, we see that the generating series for the number of ways to write $P(2) = n$ is

$$
\begin{aligned}
& \underbrace{\left(1+X+X^{2}+X^{3}\right)}_{\text {contribution of } a_{0}} \underbrace{\left(1+X^{2}+X^{4}+X^{6}\right)}_{\text {contribution of } a_{1}} \underbrace{\left(1+X^{4}+X^{8}+X^{12}\right)}_{\text {contribution of } a_{2}} \cdots \\
& =\frac{1-X^{4}}{1-X} \frac{1-X^{8}}{1-X^{2}} \frac{1-X^{16}}{1-X^{4}} \cdots \\
& =\frac{1}{(1-X)\left(1-X^{2}\right)} \\
& =\frac{1}{2} \frac{1}{(1-X)^{2}}+\frac{1}{4} \frac{1}{1-X}+\frac{1}{4} \frac{1}{1+X}
\end{aligned}
$$

The answer is therefore

$$
\frac{n+1}{2}+\frac{1}{4}+\frac{1}{4}(-1)^{n}=\frac{2 n+3+(-1)^{n}}{4}=\left\lfloor\frac{n}{2}\right\rfloor+1
$$