Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume for simplicity that when $k>n$ we have ${n\choose k}=0$.

It is well-known that $\sum_k {n\choose 2k}=\sum_k {n\choose 2k+1}=2^{n-1}$ , i.e. the sum of the odd places in each row in Pascal's triangle is equal to the sum of the even places, and both are even numbers (and actually powers of 2).

I'm interested in the sums $S_p^a=\sum_k{n\choose p\cdot k+a}$ where $p$ is an odd prime and $a\in\mathbb{Z}_p$. In particular I noted that for $p=3$ and every $n$, exactly two of the sums $S^a_3$ are equal (and both are odd) and the third sum is even, and the absolute value of the difference of their values is 1.

First question (concrete): This fact seems to be easy enough to prove by a frontal assault; is it a well-known result? Are there nice proofs for it?

Second question (somewhat vague): What can be said in general about $S^a_p$, for a fixed $p$ and $n$? It seems that in that case as well some of the sums are equal - which? What can be said about their values modulo 2? What interesting facts in general these sums have?

share|cite|improve this question
I think the keyword to search for is "lacunary sum". See this question and this question. – Zev Chonoles Jun 13 '12 at 14:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.