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.

  • $\begingroup$ You didn't define $d_k$ for $k$ even. Do the residues in the sequence you wrote only correspond to odd $k$? $\endgroup$ – A.P. May 11 '17 at 15:23
  • $\begingroup$ @A.P. the sequence is only defined for $k$ odd, then the sequence I wrote correspond to odd $k$. $\endgroup$ – 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).

  • 1
    $\begingroup$ Thank you for your comment! $\endgroup$ – A. GM May 17 '17 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.