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 discrete Fourier transform 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}$.

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 discrete Fourier transform 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}$; this case is $a = 2, d = 0$.

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 using the Laplace transform, finite differences, or a combinatorial argument. It allows us to evaluate the sums $\displaystyle \sum {n \choose ak+d}$ by setting $f(x) = \frac{x^d}{1 - x^a}$.

Finally, there is a nice interpretation of the above sums in graph-theoretic terms. Consider the family of undirected cyclic graphs $C_a$, consisting of $a$ vertices arranged in a regular $a$-gon with an edge between adjacent vertices. Labeling the vertices $0, 1, 2, ... a-1$, the probability of starting at vertex $0$ and ending at vertex $2d-a$ in $n$ steps is precisely

$$\frac{1}{2^n} \sum {n \choose ak+d}.$$

This is because a choice of whether to move left or right for each of the $n$ steps determines a subset of $\{ 1, 2, ... n \}$ whose cardinality $\bmod a$ determines your final location. Now one can compute these probabilities by computing the eigenvalues of the adjacency matrix of $C_a$ and even compute mixing times using standard graph-theoretic techniques. (Of course one may reintroduce the parameter $p$ into the adjacency matrix to model a random walk in which preference is given to moving to the left or right.)