By this paper, it can be shown that for $n>0$ and $N\in\mathbb{N}$ $$\sum_{k=0}^n\binom{Nn}{Nk}=\frac{2^{Nn}}{N}\sum_{k=0}^{N-1}(-1)^{kn}\cos^{Nn}\left(\frac{k\pi}{N}\right)$$

Now, for a recursive sequence defined here, $$A_n(N)=-\sum_{k=0}^{n-1}\binom{Nn}{Nk}A_k(N); A_0(N)=1$$

and so


From here it can be easily obtained that $A_1(N)=-1$. Now I originally wanted to show that for certain values, we have that

$$A_n(N)+1\equiv 0\pmod{N+1}$$

But this seems to be only true for certain values of $N$, where $N=2,3,4,6$. I determined this by an induction argument, whose base case is above. For all $0<k<m$, we assume $A_m(N)+1\equiv 0\pmod{N+1}$. This means that $A_m(N)\equiv N\equiv -1\pmod{N+1}$ and thus $A_m(N)=(N+1)q-1$ for $q\in\mathbb{Z}$. Substituting into the above recursion yields


The first RHS sum is necessarily divisible by $N+1$, so the second sum in question would have to be divisible by $N+1$. However this is not always the case. To see its divisibility by $2,3,4$ and $6$, note that


And from this form, we can show the validity of divisibilities for $N=2,3,4,6$ by cases (replacing $N$ and working out the residue under modulus $(N+1)$)

My question is this. I KNOW that it is not true for all $N$ through a proof presented here. Is there a way to either

1) Find more values of $N$ where it holds

2) if not, prove that for the remaining values of $N$, the hypothesis is wrong?

The values of $N$ chosen $(2,3,4,6)$ are based due to the fact the formula above involves cosines and take on simple values to calculate algebraically. I don't know how to show that it is invalid for the remaining or how to find other values of $N$. Can anyone help guide the way?

EDIT: So I used Mathematica to do a calculation of the divisibility up to $N=50$. Using the binomial sum instead of the cosine sum, I was able to see that for the first 50 numbers of each recursion for $N$, the values of $N$ that seem to produce the divisibility results are those numbers that are prime powers minus 1, $p^\alpha$, for prime $p$ and positive integer $\alpha$. This list is found as A181062. Can anyone confirm this?

  • 1
    $\begingroup$ So the question is "Am I correct to conjecture that $$\sum_{k=1}^{m-1}\binom{Nm}{Nk} \equiv 0 \pmod {N+1}$$ when $N = p^\alpha - 1$ and $p$ is prime?"? $\endgroup$ Aug 28, 2018 at 10:27
  • $\begingroup$ That is correct. $\endgroup$ Aug 28, 2018 at 10:33
  • 1
    $\begingroup$ The linked PDF has a version in terms of $N$th roots of unity. A number-theoretic version (i.e. using $N$th roots of unity over a finite field) seems like an interesting angle of attack, but $\mathbb{GF}(p^\alpha)$ has characteristic $p$ so this only seems to give the equivalence modulo $p$ rather than $p^\alpha$. Maybe someone else can fill the gap. $\endgroup$ Aug 29, 2018 at 21:10
  • 3
    $\begingroup$ This question is answered here: math.stackexchange.com/questions/2887978/… $\endgroup$ Aug 31, 2018 at 12:09

2 Answers 2


An interesting special case is when $N+1$ is prime. In that case we prove that $\binom{Nm}{Nk}$ is divided by $N+1$ when $m\le N+1$. By expanding the terms we obtain$$\binom{Nm}{Nk}=\dfrac{Nm(Nm-1)\cdots (Nk+1)}{(Nm-Nk)(Nm-Nk-1)\cdots 2\cdot 1}$$If $N+1$ is prime then the only numbers $x$ such that $\gcd(N+1,x)>1$ are the integer multiples of it i.e. $$x=(N+1)\cdot l\qquad,\qquad l=1,2,3,\cdots$$notice that if $m\le N+1$ there are $m-k$ multiples of $N+1$ among $Nm,Nm-1,\cdots Nk+1$ and $m-k-1$ such multiples among $Nm-Nk,Nm-Nk-1,Nm-Nk-2,\cdots 2,1$ (this is a simple counting) therefore $$\binom{Nm}{Nk}=\dfrac{Nm(Nm-1)\cdots (Nk+1)}{(Nm-Nk)(Nm-Nk-1)\cdots 2\cdot 1}=\dfrac{a(N(m-1)+m-1)(N(m-2)+m-2)\cdots (Nk+k)}{b(N(m-k-1)+m-k-1)\cdots (N+1)N\cdots 2\cdot 1}=\dfrac{a'}{b'}(N+1)$$this is because after cancelling the multiples of $N+1$ from both numerator and denominator there still exists one $N+1$ which can't be cancelled out any further and both $a'$ and $b'$ are coprime with $N+1$. Since $\dfrac{a'}{b'}(N+1)$ is an integer, it turns out that $b'|a'$ since $\gcd(b',N+1)=1$ by Euclid's lemma. This completes the proof on $$N+1|\binom{Nm}{Nk}\qquad,\qquad {N+1\text{ is a prime}\\ m\le N+1\\1\le k\le m-1}$$by a simple substitution this means that$$N+1|A_m(N)+1\qquad,\qquad {N+1\text{ is a prime}\\ m\le N+1\\1\le k\le m-1}$$P.S. finding all such $N$s is really hard so i think we need to bear with special and sufficient cases.


The following should have been a comment but i do not have enough points for a comment. I am just giving a different perspective here..The answer is not given..

Let $N=p^{a}$ for some prime $p$ and positive integer $a$. Let $p > n$. Then \begin{equation} (1+x)^{Nn} \mod p = \sum_{k=0}^{n} {Nn \choose Nk} x^{Nk} \mod p \end{equation}

  • $\begingroup$ Shouldn't the bounds of sigma be from $0$ to $Nn$? Further I suspect. How did you write this relation? $\endgroup$ Aug 31, 2018 at 15:04
  • $\begingroup$ You can prove that ${Nn \choose i}$ is divisible by $p$ when $i$ is not a multiple of $N$ under the conditions i specified. $\endgroup$
    – Balaji sb
    Aug 31, 2018 at 16:06
  • $\begingroup$ Hi. Sorry but neither of these really answers my question. The link mentioned above to the other problem gives the solution I am looking for. $\endgroup$ Sep 1, 2018 at 1:49

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.