Does anyone have ideas about how to simplify this combinatorial expression (mod 2)?

Question

Fix $k > 0$ for $\lceil \frac{2k+1}{3} \rceil \le j \le k$,

$$ \sum_{i = 0}^{2j-k-1} \binom{j}{i} + \sum_{b = \lceil \frac{k+1}{2} \rceil}^{\lfloor \frac{2k-j}{2} \rfloor} \left( \sum_{l = 0}^{2b-k-1} \binom{b}{l} \right) \binom{j-b-1}{2j-(2k+1)+b}$$

I think that this expression (mod 2) should be 1 when $j=k$ and 0 otherwise. I can show that it is 1 when $j = k$ and have checked the other cases for relatively small values of $k$, but have been unable to show in general that when $j \not= k$ the expression is 0 mod 2.

Answer 1

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