20
$\begingroup$

Let $p$ be a prime, and consider $$S_p(a)=\sum_{\substack{1\le j\le a-1\\(p-1)\mid j}}\binom{a}{j}\;.$$ I have a rather complicated (15 lines) proof that $S_p(a)\equiv0\pmod{p}$. This must be extremely classical: is there a simple direct proof ?

$\endgroup$

3 Answers 3

38
$\begingroup$

Let $$P(x)=(1+x)^a-1-x^a=\sum_{1 \le j \le a-1} \binom{a}{j}x^j.$$ Working in a field $F$ where $|\{\mu \in F: \mu^{p-1}=1\}|=p-1$ (roots of unity of order $p-1$ exist), we have $$ \frac{1}{p-1}\sum_{\mu^{p-1}=1}P(x \mu) = \sum_{\substack{1 \le j \le a-1\\(p-1)\mid j}} \binom{a}{j}x^j.$$ We now specialize the field to $\mathbb{F}_p$, and let $x=1$: $$ -\sum_{\mu \in \mathbb{F}_p^{\times}}P( \mu) = \sum_{\substack{1 \le j \le a-1\\(p-1)\mid j}} \binom{a}{j}.$$ To conclude, observe that $P(0)=0$ and $|\mathbb{F}_p| = p$, so $$\sum_{\mu \in \mathbb{F}_p^{\times}} P(\mu) = \sum_{\mu \in \mathbb{F}_p} P(\mu) = \sum_{\mu \in \mathbb{F}_p} ((1+\mu)^a - \mu^a)=0,$$ because $\mu\mapsto \mu+1$ is a permutation of $\mathbb{F}_p$.


A slightly more general congruence is due to Glaisher (1899), as I've found in a survey by Granville, see equation (11) here. The precise reference is Glaisher, J. W. L., "A congruence theorem relating to sums of binomial-theorem coefficients.", Quart. J. 30, 150-156, 349-360, 361-383 (1899). See here for the zbMath review in German. There is no entry in MathSciNet.

Namely, Glaisher proved that for any $0 \le j_0 \le p-1$ we have $$\sum_{\substack{1 \le j \le a \\ j \equiv j_0 \bmod (p-1)}} \binom{a}{j} \equiv \binom{k}{j_0} \bmod p$$ where $k$ is any positive integer with $k \equiv a \bmod p$ Applying this with $j_0=0$ and $k=a$, and observing that the term $j=a$ contributes $1 \bmod p$, your result follows. Clicking on equation (11) in the link above leads to a detailed proof which utilizes Lucas' theorem.

$\endgroup$
14
$\begingroup$

Here's a straightforward proof, using generating functions, though it's not as elegant as Ofir's. We have $$ \sum_{a=0}^\infty\binom{a}{j}x^a =\frac{x^j}{(1-x)^{j+1}}. $$ Setting $j=(p-1)k$ and summing on $k$ gives $$ \sum_{a=0}^\infty x^a \sum_{p-1\mid j}\binom{a}{j} = \frac{(1-x)^{p-1}}{(1-x)^p -x^{p-1}(1-x)}. $$ We subtract $\sum_{a=0}^\infty x^a \binom{a}{0} = 1/(1-x)$ and $$\sum_{\substack{p-1\mid a\\ a>0}}x^a\binom{a}{a} = \frac{x^{p-1}}{1-x^{p-1}}$$ to get $$ \sum_{a=0}^\infty S_p(a) x^a = \frac{(1-x)^{p-1}}{(1-x)^p -x^{p-1}(1-x)} -\frac{1}{1-x} -\frac{x^{p-1}}{1-x^{p-1}}. $$ Modulo $p$, we may replace $(1-x)^{p-1}$ with $(1-x^p)/(1-x)$ and $(1-x)^p$ with $1-x^p$, obtaining \begin{align*} \sum_{a=0}^\infty S_p(a) x^a &\equiv \frac{(1-x^p)/(1-x)}{1-x^p -x^{p-1}(1-x)} -\frac{1}{1-x} -\frac{x^{p-1}}{1-x^{p-1}}\pmod{p}\\ &=0. \end{align*}

$\endgroup$
3
$\begingroup$

Actually, a further extension was given in my paper Combinatorial congruences and Stirling numbers [Acta Arith. 126 (2007), 387-398]. Now I state Corollary 1.3 (a consequence of Theorem 1.1) in the 2007 paper of mine.

Let $p$ be a prime. If $l,l',m$ are positive integers with $l'\ge l>m/p$ and $l'\equiv l\pmod {(p-1)p^{\lfloor\log_p m\rfloor}}$, then $$\sum_{j\equiv r\pmod {p-1}}\binom{l'}j S(j,m) \equiv\sum_{j\equiv r\pmod {p-1}}\binom{l}j S(j,m)\pmod p,$$ where $S(j,m)$ denotes the Stirling number of the second kind.

In the case $m=1$, this yields Glaisher's result.

$\endgroup$

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.