<s>[INST] Recursive sequence modulo 4 For all odd positive integers $k$, I define a recursive sequence by
$$
d_k=2+ {k\choose 1}d_{k-2} + {k\choose 2}d_{k-4} + \dots +{k\choose \frac{k-1}{2}}d_1\\
d_1=2
$$
I want to study this sequence modulo $4$. By induction, it is easy to see that $d_k$ is either $0$ or $2$. Computing this sequence I get 
$$
2,0,2,2,0,2,2,0,2,2,0,2,2,0,2\dots (\mod 4)
$$
which made me think that
$$
d_k\equiv 0 (\mod 4)\text{  if and only if  } k\equiv 0 (\mod 3)
$$
Do you have an idea how to prove that? I tried to prove but I don't find any nice behavior on the binomial coefficients that helps me.
 [/INST] As in @A.P.'s answer, define
$$ \begin{eqnarray}
c_0 & = & 1 \\
c_n & = & 1 + \sum_{k = 1}^n {2n + 1 \choose k}c_{n - k}
\end{eqnarray} $$
so that $ d_{2n + 1} = 2c_n $. Let's prove by induction that $ c_n $ is even iff $ n \equiv 1 \mod 3 $.
$ \bullet $ Initialisation: $ c_0 = 1 $ is odd.
$ \bullet $ Induction: We have
$$ \begin{eqnarray}
c_n
& = & 1 + \sum_{k = 1}^n {2n + 1 \choose k}c_{n - k} \\
& \equiv & 1 + \sum_{k \in [\![1, n]\!], k \not\equiv n - 1\mod 3} {2n + 1 \choose k} \\
& = & 1 + \frac{\sum_{k = 1}^{2n} {2n + 1 \choose k}}2 - \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \\
& = & 2^{2n} - \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \\
& \equiv & \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \mod 2 \\
& \equiv & \sum_{k \in [\![0, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} + \begin{cases}1 \text{ if $ 3 \mid n - 1 $} \\0 \text{ otherwise}\end{cases} \mod 2
\end{eqnarray} $$
Notice furthermore that $ k \equiv n - 1 \mod 3 \implies 2n + 1 - k \equiv n - 1 \mod 3 $. Hence
$$ \begin{eqnarray}
c_n \equiv \begin{cases}0 \text{ if $ 3 \mid n - 1 $} \\1 \text{ otherwise}\end{cases} \mod 2
& \iff & \sum_{k \in [\![0, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \equiv 1 \mod 2 \\
& \iff & \sum_{k \in [\![0, 2n + 1]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \equiv 2 \mod 4
\end{eqnarray} $$
Now denote
$$ r_{a, m} = \sum_{k \in [\![0, m]\!], k \equiv a\mod 3} {m \choose k} $$
$ r $ behaves like a Pascal triangle rolled around. That is, $ r_{a + 1, m + 1} = r_{a, m} + r_{a + 1, m} $ and $ r_{a + 3, m} = r_{a, m} $. We can thus easily calculate $ r_{0, m}, r_{1, m}, r_{2, m} $ modulo $ 4 $
$$ \begin{eqnarray}
m\quad & r_0 & r_1 & r_2 \\
0\quad & 1    & 0    & 0    \\
1\quad & 1    & 1    & 0    \\
2\quad & 1    & 2    & 1    \\
3\quad & 2    & 3    & 3    \\
4\quad & 1    & 1    & 2   
\end{eqnarray} $$
We see that it enters a cycle of period $ 6 $ starting from $ m = 2 $ and that $ r_{n - 1, 2n + 1} $ is always $ 2 $, as wanted.
Note: The pattern highly suggests that proving $ c_n \equiv c_{n - 1} + c_{n - 2} \mod 2 $ is an option, but I couldn't find a way to make it work.
</s>