Step aside

Let $E_n$ be the expected number of steps that Brilli must take to reach a distance $N$ from his starting point, given that he is currently a distance of $n$ from his starting point. Then we have the equations $E_n \; = \; 1 + \tfrac12(E_{n+1} + E_{n-1}) \hspace{2cm} 1 \le n \le N-1$ together with the boundary conditions $E_0 \; = \; 1 + E_1 \hspace{2cm} E_N \; = \; 0$ Solving these equations, we obtain $E_n \; = \; N^2 - n^2 \hspace{2cm} 0 \le n \le N$ and hence $E_0 = N^2$ . With $N=2016$ , this makes the answer $2016^2 = \boxed{4064256}$ .