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

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.

• Modulo 2 we have $\sum_{i=0}^A {N\choose i}\equiv {N-1\choose A}$, this already simplifies your expression Commented Dec 31, 2021 at 11:52

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, 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$$.
• Thank you for your answer. I am having trouble understanding where the generating function $F_k(x)$ is coming from. Could you point me towards a reference or something with some more details about where that is coming from? I can see that this should be equivalent to the generating function for $\binom{(k+1)-r}{r}$, but still don't understand how to get to that answer. Commented Jan 20, 2022 at 16:45
• @user473047: I'm pretty sure this is covered in Concrete Mathematics, but can be also verified directly from the properties of $C(x)$ -- e.g., see mathoverflow.net/q/351445 One can also derive it from scratch using the generating function for binomial coefficients and Lagrange–Bürmann formula. Commented Jan 20, 2022 at 17:22