2
$\begingroup$

I would like to show the following identity: for all $n, q \geq 0$,

$$\sum_k \binom{2k}{4k-2n} \binom{n+3q}{2k+2q+1} \equiv \binom{n+3q}{2q-1} \pmod{2}.$$

This has been computer-tested for all $n, q \leq 100$.

Remarks:

  • My convention is that the binomial coefficient $\binom{m}{n}$ is nonzero only if $m \geq n \geq 0$.
  • If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] \, \frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] \, (1+y)^{n+3q}$.
  • The identity is not true without modulo $2$.
$\endgroup$
3
$\begingroup$

Here is a tentative proof:

We first notice that by Kummer theorem $\binom{2n}{2m} \equiv \binom{n}{m} \bmod 2$, so that it suffices to show that $$ S_q(n) \equiv T_q(n) \pmod 2$$ where \begin{align*} S_q(n):=&\sum_k \binom{k}{n-k}\binom{n+3q}{2k+2q+1}\\ T_q(n):=&\binom{n+3q}{2q-1}. \end{align*}

From here, the symbol $\sim$ means has the same parity as.

We have $\binom{a+1}{b+1}\sim \binom{a}{b+1}+\binom{a}{b}$ but also $\binom{a+2}{b+2}\sim \binom{a+2}{b}+\binom{a}{b}$.

We have \begin{align*} T_q(n+2)&\sim \binom{n+3q+2}{2q-1} \sim \binom{n+3q}{2q-1}+\binom{n+3q}{2q-3}\\ &\sim T_q(n) +\binom{n+3+3(q-1)}{2(q-1)-1} \\ &\sim T_q(n) +T_{q-1}(n+3) \\ T_q(n+3)&\sim T_{q+1}(n+2)+ T_{q+1}(n) \end{align*} On the other hand, we have \begin{align*}S_q(n+3)& \sim \sum_k \binom{k}{n+3-k}\binom{n+3q+3}{2k+2q+1}\\ &\sim \sum_k \binom{k}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2(k-1)+2q+3}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ & \sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k\binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\\ &+\sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim S_{q+1}(n+2) +\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2k+2(q+1)-1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2) \\&+\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k\binom{k-1}{n-(k-1)}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ S_q(n+3)&\sim S_{q+1}(n+2)+ S_{q+1}(n) \end{align*}

So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) \sim T_q(n)$, it suffices to show that $ S_q(0) \sim T_q(0)$, $ S_q(1) \sim T_q(1)$ and $ S_q(2) \sim T_q(2)$.

$S_q(0)-T_q(0)$ is clearly an even integer since $$S_q(0)-T_q(0)= \binom{3q}{q+1}-\binom{3q}{q-1}=2 \binom{3q+1}{q-1}.$$

We have $T_q(1)-S_q(1)= \binom{3q+1}{q+2}-\binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2\frac{5q+7}{3q+3}\binom{3q+3}{q-1}$$ which is an even integer since \begin{align*}\binom{3q+3}{q-1}(5q+7) &\equiv \binom{3q+3}{q-1}(2q+4)\pmod {3q+3}\\ &\equiv-\binom{3q+3}{q-1}(q-1)\pmod {3q+3}\\ &\equiv-\binom{3q+2}{q-2}(3q+3)\pmod {3q+3}\\ &\equiv 0\pmod {3q+3}\end{align*}

Also, after some calculation, it can be shown that \begin{align*} T_q(2)-S_q(2) &= \binom{3q+2}{q+3}-\binom{3q+2}{q-1}-\binom{3q+2}{q-3}\\ &= 2 \binom{3q+5}{q-1} \frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}. \end{align*} Then, to complete the proof, we need to show that $$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3)\equiv 0 \pmod {(3q+5)(3q+4)(3q+3)}.$$ We have $$ (54+301q+258q^2+59q^3) \equiv (q-1)(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$

Then $$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3) \equiv (3q+5)\binom{3q+4}{q-2}(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$ Then it suffices to show that $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {(3q+4)(3q+3)}.$$ But $3q+4$ and $3q+3$ are coprime, so we need to show that $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+4}$$ and $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+3}.$$ That is $$ \binom{3q+4}{q-2}(14-q^2)\equiv 0 \pmod {3q+4} \tag1$$ and $$ \binom{3q+4}{q-2}(24-q-q^2)\equiv 0 \pmod {3q+3}.\tag2$$

(1) is equivalent to \begin{align*} \frac{3q+4}{q-2}\binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {3q+4} \\ \binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {q-2}\\ 10\binom{3q+3}{q-3}&\equiv 0 \pmod {q-2}\\ 10\frac{q-2}{3q+4}\binom{3q+4}{q-2}&\equiv 0 \pmod {q-2}\\ 10\binom{3q+4}{q-2}&\equiv 0 \pmod {3q+4}.\\ \end{align*}

But the last line holds true indeed, because we know from here that \begin{align*} \binom{3q+4}{q-2}&\equiv 0 \pmod {\frac{3q+4}{\gcd(3q+4,q-2)}}\\ &\equiv 0 \pmod {\frac{3q+4}{\gcd(10,q-2)}}\end{align*}

There remains to show the validity of (2). We have

$$ \binom{3q+4}{q-2}(24-q-q^2)= (3q+3)\binom{3q+4}{q-4} \frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$ so that we need to show that $$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {(q-2)(q-3)}. $$ That is

$$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-2} $$ and $$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-3}. $$ That is $$ 180\binom{3q+2}{q-4}\equiv 0\pmod {q-2} $$ and $$ 156 \binom{3q+2}{q-4}\equiv 0\pmod {q-3}. $$ That is $$ 180\frac{(q-2)(q-3)}{(3q+4)(q-2)}\binom{3q+4}{q-2}\equiv 0\pmod {q-2} $$ and $$ 156 \frac{q-3}{3q+3}\binom{3q+3}{q-3}\equiv 0\pmod {q-3}. $$

That is $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {(3q+4)(3q+3)} $$ and $$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. $$ That is $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+4} \tag3$$ and $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+3} \tag4$$ and $$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. \tag5$$

For (5) it holds true because we have $156=13\cdot 12$ a multiple of $12$ and from here, we have \begin{align*}\binom{3q+3}{q-3}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-3)}} \\ &\equiv 0\pmod {\frac{3q+3}{\gcd(12,q-3)}} \end{align*} For (3) it holds true because we have $180=18\cdot 10$ a multiple of $10$ and from here, we have \begin{align*}\binom{3q+4}{q-2}&\equiv 0\pmod {\frac{3q+4}{\gcd(3q+4,q-2)}} \\ &\equiv 0\pmod {\frac{3q+2}{\gcd(10,q-2)}} \end{align*}

We have seen that there exist an integer $K$, such that $\binom{3q+3}{q-3}=K\frac{3q+3}{\gcd(12,q-3)}$. Now, with the same argument from here, we have \begin{align*}\binom{3q+3}{q-2}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-2)}} \\ &\equiv 0\pmod {\frac{3q+3}{\gcd(9,q-2)}} \end{align*} so there exists an integer $L$ such that $\binom{3q+3}{q-2}=L\frac{3q+3}{\gcd(9,q-2)}$. Then \begin{align*} 180(q-3)\binom{3q+4}{q-2}&=180(q-3)\left(\binom{3q+3}{q-2}+\binom{3q+3}{q-3}\right)\\ &= (3q+3)\left( \frac{180L(q-3)}{\gcd(9,q-2)}+\frac{180K(q-3)}{\gcd(12,q-3)}\right). \end{align*} The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.

$\endgroup$
  • $\begingroup$ Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction. $\endgroup$ – JHF Nov 21 '18 at 15:54

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.