1
$\begingroup$

I am reading this "Amazing properties of binomial coefficients" and particularly problem 1.6 on page 1 and its "Solution 1" on page 7.

What I don't understand is when they recombine sums in the last passage of the proof on page 8 "Now transform the sum from the problem statement: ...".

Anyone can help me? Thank you very much!

$\endgroup$
3
$\begingroup$

We want to show by induction on $n$: If $1\leq j,k\leq p-1$ and $n\equiv k \pmod{p-1}$ then \begin{align*} \binom{n}{j}+\binom{n}{(p-1)+j}+\binom{n}{2(p-1)+j}+\binom{n}{3(p-1)+j}+\cdots\equiv \binom{k}{j} \pmod{p} \end{align*}

The recombination of the sums, OP is asking for, is an essential part of the induction step. To better see what's going on we look at the entire induction step.

We obtain \begin{align*} \sum_{l\geq 0}&\binom{n}{l(p-1)+j}\\ &=\sum_{l\geq 0}\binom{m+(p-1)}{l(p-1)+j}\tag{1}\\ &=\sum_{l\geq 0}\sum_{i=0}^{\min\{l(p-1)+j,p-1\}}\binom{m}{l(p-1)+j-i}\binom{p-1}{i}\tag{2}\\ &\equiv \sum_{l\geq 0}\sum_{i=0}^{\min\{l(p-1)+j,p-1\}}(-1)^i\binom{m}{l(p-1)+j-i}\tag{3}\\ &=\sum_{i=0}^j(-1)^i\binom{m}{j-i}+\sum_{l>0}\sum_{i=0}^{p-1}\binom{m}{l(p-1)+j-i}\tag{4}\\ &=\sum_{i=0}^j(-1)^i\binom{m}{j-i}+\sum_{i=0}^{p-1}\binom{m}{p-1+j-i}+\sum_{i=0}^{p-1}\binom{m}{2(p-1)+j-i}+\cdots\tag{5}\\ &=\left[\color{blue}{\binom{m}{j}}-\binom{m}{j-1}+\cdots-(-1)^j\binom{m}{1}+(-1)^j\binom{m}{0}\right]\\ &\qquad +\left[\color{blue}{\binom{m}{(p-1)+j}}-\binom{m}{(p-1)+j-1}+\cdots+\binom{m}{j}\right]\\ &\qquad +\left[\color{blue}{\binom{m}{2(p-1)+j}}-\binom{m}{2(p-1)+j-1}+\cdots+\binom{m}{(p-1)+j}\right]\tag{6}\\ &\qquad \ \,\vdots\\ &=\color{blue}{\sum_{l\geq 0}\binom{m}{l(p-1)+j}}\\ &\qquad+\left[(-1)^j\binom{m}{0}-(-1)^j\binom{m}{1}+\cdots-\binom{m}{j-1}\right]\\ &\qquad+\left[\binom{m}{j}-\binom{m}{j+1}+\cdots-\binom{m}{(p-1)+j-1}\right]\\ &\qquad+\left[\binom{m}{(p-1)+j}-\binom{m}{(p-1)+j+1}+\cdots+\binom{m}{2(p-1)+j-1}\right]\tag{7}\\ &\qquad \ \,\vdots\\ &=\color{blue}{\sum_{l\geq 0}\binom{m}{l(p-1)+j}}+(-1)^j\sum_{i=0}^m\binom{m}{i}(-1)^i\tag{8}\\ &=\color{blue}{\sum_{l\geq 0}\binom{m}{l(p-1)+j}}+(-1)^j(1-1)^m\\ &=\color{blue}{\sum_{l\geq 0}\binom{m}{l(p-1)+j}}\\ &\equiv \binom{k}{j}\pmod{p}\tag{9} \end{align*} and the induction step is completed.

Comment:

  • In (1) we set $n=m+p-1$.

  • In (2) we apply the Vandermonde's identity. We explicitly set lower and upper index of the inner sum which will be useful in the next steps.

  • In (3) we use $\binom{p-1}{i}\equiv (-1)^i\pmod{p}$ corresponding to problem 1.1.a in the paper.

  • In (4) we split the summand with $l=0$ since the inner sum has upper limit $j$ while in all other cases ($l>0$) the inner sum has upper limit $p-1$.

  • In (5) we write the summands with $l=0,1$ and $l=2$ explicitly.

  • In (6) we expand each of the sums with $l=0,1$ and $l=2$.

  • In (7) we collect the first summand (marked in blue) of each of the sums and write the other summands in reverse order.

  • In (8) we observe that all the terms from the expanded sums are consecutive terms starting with $(-1)^j\binom{m}{0}$ and they can be written as one sum.

  • In (9) we apply the induction hypothesis.

Note: In the paper there is a typo in the derivation of the formula on page 8. In the expression \begin{align*} +\left(\binom{m}{2(p-1)+j}-\binom{m}{2(p-1)+j-1}+\cdots +\binom{m}{\color{blue}{2}(p-1)+j}\right)+\cdots \end{align*} the blue marked factor $\color{blue}{2}$ is not correct and should be deleted. The last summand is $\binom{m}{(p-1)+j}$.

$\endgroup$
  • $\begingroup$ Thank you! This is working with $j =0$ too, right? $\endgroup$ – mbjoe Aug 26 '18 at 6:13
  • $\begingroup$ @mbjoe: You're welcome. I think the range of validity starting with $j=1$ is correct. Note that the simpler formula with $j=0$ in example 1.6 starts with $\binom{n}{p-1}$ and not with $\binom{n}{0}$. Take e.g. the example $p=7,n=12,k=6$ and $j\in\{0,1\}$. $\endgroup$ – Markus Scheuer Aug 26 '18 at 8:06
  • $\begingroup$ Rethinking about it I should replace $j = p-1$ then. By the way I was trying to apply that problem's result to this question. $\endgroup$ – mbjoe Aug 26 '18 at 12:26

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.