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.
 A: Disclaimer: The following is more of a long comment than an answer. I will update it should I find out more.
Since saying that $d_k$ is $0$ or $2$ modulo $4$ is the same as saying that $d_k$ is even, allow me to rephrase your problem. Define
$$
\begin{align}
c_n &= 1 + \binom{2n+1}{1} c_{n-1} + \dotsc + \binom{2n+1}{n}c_0\\
c_0 &= 1
\end{align}
$$
so that $d_{2n+1} = 2c_n$ for every $n \geq 0$. Then your question is equivalent to asking whether
$$
c_n \text{ is even } \quad \text{iff} \quad n \equiv 1 \pmod 3.
$$
This could be useful because, as a consequence of Lucas's theorem, $\binom{k}{i}$ is even if and only if at least one of the binary digits of $i$ is greater than the corresponding digit of $k$. In other words, $\binom{k}{i}$ is even if and only if the binary expansions of $k-i$ and $i$ have a $1$ in the same place (see also this answer on MSE). I used this to write some code to compute $c_n$ reasonably fast and checked that your conjecture holds at least for the first $10000$ terms of the sequence, but I don't have a proof, yet.
It might also be useful to note that the odd binomial coefficients, when arranged in Pascal's triangle, form an approximation of Sierpinski's triangle (you can find a proof here).
A: 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.
