Solution
= Solution
Give every edge weight one and delete the row and column for $v_n$ from the out-Laplacian. Expanding the resulting banded determinant along its last available row gives
$$
a_n=a_{n-1}+2a_{n-2},
\qquad a_2=1,\quad a_3=3.
$$
The characteristic roots are $2$ and $-1$, and the initial values give
$$
a_n=\frac{2^n-(-1)^n}{3}.
$$
By the directed <matrix-tree theorem>, this determinant is exactly the number of directed spanning trees rooted towards $v_n$.