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
$$A_n(N)+1=-\sum_{k=1}^{n-1}\binom{Nn}{Nk}A_k(N)$$
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
$$A_m(N)+1=-\sum_{k=1}^{m-1}\binom{Nm}{Nk}[(N+1)q-1]=-(N+1)\sum_{k=1}^{m-1}\binom{Nm}{Nk}q+\sum_{k=1}^{m-1}\binom{Nm}{Nk}$$
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
\begin{eqnarray*}\sum_{k=1}^{m-1}\binom{Nm}{Nk}&=&\sum_{k=0}^{m}\binom{Nm}{Nk}-\binom{Nm}{0}-\binom{Nm}{Nm}\\&=&\frac{2^{Nm}}{N}\sum_{k=0}^{N-1}(-1)^{km}\cos^{Nm}\left(\frac{k\pi}{N}\right)-2\end{eqnarray*}
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?