Evaluate sum similar to the binomial theorem modulo 5 $$\sum_{k=0}^n\binom{2n+1}{2k+1}2^{3k}\bmod 5$$ 
I tried changing $2^{3k}$ into $\sqrt{2^3}^{2k+1}$, then substituting $j=\frac k 2 - 1$ and using the binomial theorem, resulting in $\frac 1 {\sqrt{2^3}}(1+\sqrt{2^3})^{2n+1}-2n+1 \bmod 5$, but this doesn't seem to be right, and I don't know what to do with the $\bmod 5$.
 A: As an alternative to using the field $\Bbb{F}_{25}$ I proffer the following.
Let's denote your sum by $S_n$.
We have the identity (also pointed out by Paolo Leonetti)
$$
f(x,k):=\sum_{2\nmid i,0<i\le k}\binom k i x^i=\frac{(1+x)^k-(1-x)^k}2.
$$
This implies that
$$
S_n=f(\sqrt8,2n+1)=\frac{(1+\sqrt8)^{2n+1}-(1-\sqrt8)^{2n+1}}2.
$$
The polynomial
$$
p(T)=(T-(1+\sqrt8)^2)(T-(1-\sqrt8)^2)=T^2-18T+49
$$
has $(1\pm\sqrt8)^2$ as its zeros. By a standard result on linear recurrences this implies that the sequence $(S_n)$ follow the recurrence relation
$$
S_{n+2}-18S_{n+1}+49S_n=0
$$
for all integers $n\ge0$.
Turning this into a modulo five relation gives
$$
S_{n+2}\equiv 3S_{n+1}+S_n\pmod5.
$$
As $S_0=1$ and $S_1=11$ from this it follows that the remainders modulo five follow the pattern
$$
(1, 1, 4, 3, 3, 2, 4, 4, 1, 2, 2, 3, 1, 1, 4, 3, 3, 2, 4, 4, 1, 2, 2,
  3,\ldots)
$$
that clearly repeats with a period twelve. Periodicity can be proven by induction using the recurrence relation, or by rewriting the recurrence using a matrix.
Many ways to skin this cat.
