3. Perica stands on one of the four floors of a building. In one move, he moves to an adjacent floor (the floor above or the floor below, if it exists). In how many ways can Perica make $n$ moves, where $n$ is a given non-negative integer, if he can start on any floor but must end on the last one?
3. Let $A_{i}(n), i \in\{1,2,3,4\}$, denote the number of ways for Perica to start from the $i$-th floor, take $n$ steps, and end on the last floor. The desired number is $B_{n}=\sum_{i=1}^{4} A_{i}(n)$. We directly calculate $B_{0}=\sum_{i=1}^{4} A_{i}(0)=0+0+0+1=1$ and $B_{1}=\sum_{i=1}^{4} A_{i}(1)=0+0+1+0=1$. Further, it is clear that for any $n>1$ the following holds:

$$
\begin{aligned}
& A_{1}(n)=A_{2}(n-1) \\
& A_{2}(n)=A_{1}(n-1)+A_{3}(n-1) \\
& A_{3}(n)=A_{2}(n-1)+A_{4}(n-1) \\
& A_{4}(n)=A_{3}(n-1)
\end{aligned}
$$

Thus, we obtain

$$
\begin{aligned}
B_{n} & =\sum_{i=1}^{4} A_{i}(n)=A_{2}(n-1)+\left(A_{1}(n-1)+A_{3}(n-1)\right)+\left(A_{2}(n-1)+A_{4}(n-1)\right)+A_{3}(n-1) \\
& =A_{2}(n-1)+A_{3}(n-1)+\sum_{i=1}^{4} A_{i}(n-1) \\
& =\left(A_{1}(n-2)+A_{3}(n-2)\right)+\left(A_{2}(n-2)+A_{4}(n-2)\right)+\sum_{i=1}^{4} A_{i}(n-1) \\
& =\sum_{i=1}^{4} A_{i}(n-1)+\sum_{i=1}^{4} A_{i}(n-2)=B_{n-1}+B_{n-2}
\end{aligned}
$$

Therefore, from $B_{0}=1=F_{1}, B_{1}=1=F_{2}$ and the corresponding recurrence relation for Fibonacci numbers, we have $B_{n}=F_{n+1}$.