# 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.

• You didn't define $d_k$ for $k$ even. Do the residues in the sequence you wrote only correspond to odd $k$? – A.P. May 11 '17 at 15:23
• @A.P. the sequence is only defined for $k$ odd, then the sequence I wrote correspond to odd $k$. – A. GM May 11 '17 at 15:36

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).

• Thank you for your comment! – A. GM May 17 '17 at 21:39