We wish to show that $\sum_{k} \binom{n}{2k+1}\cdot 5^k$ counts the number of interlaced sequences, consisting of a length $n-1$ binary sequence and a length $n-2$ coloring of fence posts such that no two black posts are adjacent. To do so, we first can make the expression a bit nicer, and more relevant to length-$(n-1)$ sequences, by expanding $\binom{n}{2k+1}$ as $\binom{n-1}{2k}+\binom{n-1}{2k+1}$ by the Pascal recurrence. The sum then becomes $$\sum_{k} \binom{n-1}{2k}\cdot 5^k+\binom{n-1}{2k+1} \cdot 5^k=\sum_{m} \binom{n-1}{m} \cdot 5^{\lfloor m/2 \rfloor}.$$

Notice that this can be thought of as a sum of exactly $2^{n-1}$ powers of $5$, where the power $5^{\lfloor m/2 \rfloor}$ occurs exactly $\binom{n-1}{m}$ times in the sum for all $m\ge 0$. It therefore suffices to sort the interlaced sequences into $2^{n-1}$ disjoint collections such that exactly $\binom{n-1}{m}$ of them have size $5^{\lfloor m/2\rfloor}$ for each $m$.

Let a white sequence be an interlaced sequence such that all the fence posts are colored white, such as: $$1 \square \, 0 \, \square \, 1\, \square \, 1\, \square \, 1$$ Given a white sequence $S$, let $m$ be the number of $1$’s in its binary sequence. We say another interlaced sequence $T$ is a buddy of $S$ if it can be formed by pairing off the $1$’s in $S$ starting from the left to form $\lfloor m/2 \rfloor$ pairs, and then for each pair, consider the fence post $p$ just before the right hand $1$ of the pair and perform one of the following operations:

1. Keep $p$ white
2. Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $0$
3. Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $1$
4. Color $p$ black and change the adjacent digits on the left and right of $p$ to $1$ and $0$
5. Color $p$ black and change the adjacent digits on the left and right of $p$ to $1$ and $1$

For instance, the following is a buddy of the white sequence above, by using option 4 on the first pair of $1$’s and option 2 on the second:

$$1 \, \square \, 1 \, \blacksquare \, 0 \, \square \, 0\, \blacksquare\, 0 $$

Notice that the black fence posts formed in this way must be separated by at least one white fence post, since each is between some consecutive (though not necessarily adjacent) pair of $1$’s. Thus all buddies of a white sequence are valid interlaced sequences.

Since there are $5$ possibilities above for each pair of $1$’s in $S$, there are $5^{\lfloor m/2 \rfloor}$ buddies of $S$. Additionally, given any interlaced sequence $T$, there is a unique white sequence $S$ that it is buddies with, constructed as follows: Consider the black fence posts $p$ of $T$ and, from left to right, change $p$ to white and make the digit to the the right of $p$ be $1$ and change the digit on the left so as to make the parity of the $1$’s up to that point odd. Finally, note that no two white sequences are buddies with each other.

It follows that the buddies relation sorts the interlaced sequences into subcollections of $5^{\lfloor m/2 \rfloor}$ collections each, where $m$ is the number of $1$’s in the unique white sequence in the subcollection. Since there are exactly $\binom{n-1}{m}$ white sequences having exactly $m$ $1$’s, the result follows.