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.

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

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

  • $\begingroup$ 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. $\endgroup$
    – user473047
    Commented Jan 20, 2022 at 16:45
  • $\begingroup$ @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. $\endgroup$ Commented Jan 20, 2022 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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