Some general remarks.  There is a family of linear operators $\phi_{a,d}$ which, given a generating function $f(x) = \sum f_n x^n$, returns the generating function $\sum f_{an+d} x^n$.  Observe that, for $\zeta$ a primitive $a^{th}$ root of unity,

$$f(\zeta^k x) = \sum_{i=0}^{a-1} \zeta^{ki} \phi_{a,i}(f(x)).$$

This is precisely the <a href="http://en.wikipedia.org/wiki/Discrete_Fourier_transform">discrete Fourier transform</a> matrix of order $a$, and inverting it tells us how to write down these operators $\phi_{a,d}$ explicitly and in particular to compute all sums of the form $\displaystyle \sum {n \choose ak+d}$.  

In this particular case there is a dirty trick I like to employ.  Given a generating function $f(x) = \sum f_n x^n$, the generating function $g(x) = \sum g_n x^n$ where

$$g_n = \sum_{k=0}^{n} {n \choose k} f_k$$

satisfies

$$g(x) = \frac{1}{1 - x} f \left( \frac{x}{1 - x} \right).$$

One may deduce this either by performing and inverting a Laplace transform or combinatorially.  Either way, it allows us to evaluate the sums $\displaystyle \sum {n \choose ak+d}$ by setting $f(x) = \frac{x^d}{1 - x^a}$.