Elementary or combinatorial approach to a sum A question appeared recently (now closed) asking for help in evaluating a sum of the form $$S(n)=\sum_{k=0}^\infty\binom{n}{a+rk}$$ for given $a,r$. The question had $a=2, r=4$ and some good answers all of which used complex numbers one way or another.
The question wanted a solution which did not involve complex numbers - I showed how to form a recurrence relation in the particular case, but then conventional methods of solving brought in powers of complex numbers.
So is this, as seems to be the case inevitable, and if so is there a good reason why? Or is there an elementary or combinatorial way of addressing such sums?
Since the question I linked has been closed, and I thought there were a couple of answers there worth recording for posterity, I will also credit answers which show efficient use of complex numbers to compute the sum. But I am most interested in the primary question as to whether there are essentially different methods available. Of course the computation of an answer using complex methods might be part of an explanation of that.
 A: A brief introduction. The binomial theorem allows us to compute sums of the form $\sum_{k\geq 0}\binom{n}{k}z^k$ in a simple way ($(z+1)^n$), so a slick approach for computing $\sum_{k\in\text{AP}}\binom{n}{k}$ is to reduce the last problem to the previous one, by noticing that $\mathbb{1}_{\text{AP}}(k)$, the characteristic function of some arithmetic progression, can be written as a linear combination of $k$-th powers of $r$-th roots of unity, where $r$ is the common difference of the $\text{AP}$. Unluckily, $x^r-1$ completely factors over $\mathbb{R}$ in very few cases.
A worked example. Let us consider the $\text{AP}$ made by numbers of the form $4h+1$. Heuristically, we expect to have about one fourth of the subsets of $[1,2,\ldots,n]$ with a number of elements which belongs to the chosen $\text{AP}$. By the previous observation (discrete Fourier transform) we have
$$ \sum_{k\in\text{AP}}\binom{n}{k} = \sum_{k=0}^{n}\binom{n}{k}\frac{1^{n}-(-1)^{n}-i\cdot i^{n}+i\cdot(-i)^{n}}{4}$$
so the exact value of the LHS is 
$$\frac{1}{4}\left(2^n-i(1+i)^n + i (1-i)^n \right)=\frac{1}{4}\left(2^n+\color{red}{2\sqrt{2}^n\sin\frac{\pi n}{4}} \right).$$
To predict the magnitude of the $\color{red}{\text{deviation}}$ in a purely real/combinatorial fashion is both pretty hard and pretty pointless. Complex numbers are a powerful tool and they provide great tricks (like the residue theorem for the evaluation of real integrals/series), you should not avoid them just because they are named complex. Here it is a corollary of the discrete Fourier transform:
Since $1+e^{\pm \frac{2\pi i}{3}}$ still is a root of unity, for any $\text{AP}$ with common difference $3$ we have
$$ \sum_{k\in\text{AP}}\binom{n}{k} \in\left[\frac{2^n-2}{3},\frac{2^n+2}{3}\right],$$
i.e. the deviation is uniformly bounded.
