Skip to main content
2 of 2
added 23 characters in body; deleted 26 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

First we may notice that $$\sum_{i=0}^m \binom{n}{i} = [x^m]\ \frac{(1+x)^n}{1-x} \equiv_2 [x^m]\ \frac{(1+x)^n}{1+x} = [x^m]\ (1+x)^{n-1} = \binom{n-1}m,$$ which was already pointed out by @FedorPetrov in the comments.

Then modulo 2 the given expression is congruent to $$(\star)\qquad \binom{j-1}{2j-k-1} + \sum_b \binom{b-1}{2b-k-1} \binom{j-b-1}{2j-(2k+1)+b}$$

Next, we notice that $\binom{b-1}{2b-k-1}=\binom{b-1}{k-b}$ has the generating function $F_k(x):=\frac{C(-x)^{-k}-(-xC(-x))^k}{\sqrt{1+4x}}\equiv_2 C(x)^{-k}+(xC(x))^k$, namely $\binom{b-1}{k-b}=[x^{k-b}]\ F_k(x)$, where $C(x):=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for Catalan numbers.

Similarly, $\binom{j-b-1}{2j-(2k+1)+b} = [x^{2j-(2k+1)+b}]\ F_{3j-2k-1}(x)$. Noticing that $3j-2k-1<k$, we conclude that the sum in $(\star)$ is congruent to the coefficient of $x^{2j-k-1}$ in $$F_k(x)\cdot F_{3j-2k-1}(x)\equiv_2 C(x)^{-(3j-k-1)}+(xC(-x))^{3j-k-1}+x^{3j-2k-1}C(x)^{3j-3k-1}+x^{k}C(x)^{3k-3j+1},$$ that is $\binom{j-1}{2j-k-1}+0+\binom{2(k-j)}{k-j}+0$.

All in all, modulo 2 the expression $(\star)$ is congruent to$\binom{2(k-j)}{k-j}$, which is congruent to 1 iff $k=j$.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152