How do I count the subsets of a set whose number of elements is divisible by 3? 4?
There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$ for $\omega$ a primitive $r$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.
They show that both sides count the number of closed $n$-walks on $C_r$ beginning at vertex 0, where $C_r$ is the directed cycle on $r$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.
Left-hand side: In order for an $n$-walk to be closed, it has to take $kr$ forward moves and $n-kr$ stationary moves for some $k$.
Right-hand side: The number of closed walks starting at vertex $j$ is the same regardless of the choice of $j$, and so it suffices to prove that the total number of closed $n$-walks on $C_r$ is $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ For each $n$-walk with initial vertex $j$, assign each forward step a weight of $\omega^j$ and each stationary step a weight of $1$. Define the weight of an $n$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $n$-walks starting at $j$ is $(1+\omega^j)^n$, and $\sum_{j=0}^{r-1} (1+\omega^j)^n$ gives the total weight of all $n$-walks on $C_r$. The open $n$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $0$. Thus the open $n$-walks contribute a total of $0$ to the sum $\sum_{j=0}^{r-1} (1+\omega^j)^n$. Since a closed $n$-walk has weight $1$, $\sum_{j=0}^{r-1} (1+\omega^j)^n$ must therefore give the number of closed $n$-walks on $C_r$.
They then make a slight modification of the argument above to give a combinatorial proof of $$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$ where $0 \leq a < r$.
Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $\sum_{k \geq 0} \binom{n}{3k}$ and $\sum_{k \geq 0} \binom{n}{4k}$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.
Fix two elements s1,s2∈S and divide subsets of S into two parts (subsets of S containing only s2)∪(subsets of S which contains s1 if they contain s2). The second part contains equal number of sets for all reminders mod 3 (because Z/3 acts there adding s1, then s2, then removing both of them) -- namely, 2n-2. And for the first part we have a bijection with subsets (edit: with 2 mod 3 elements) of a set with (n-2) elements.
So we get a recurrence relation that gives an answer 2n-2+2n-4+... -- i.e. (2n-1):3 for even and (2n-2):3 for odd n.
Errata. For n=0,1,5 mod 6 one should add "+1" to the answer from the previous paragraph (e.g. for n=6 the correct answer is 1+20+1=22 and not 21).
Let me try to rephrase the solution to make it obvious. For n=2k divide S on k pairs and consider an action of a group Z/3Z on each pair described in a first paragraph. We get an action of (Z/3Z)k on subsets of S, and after removal of it's only fixed point (k-element set consisting of second points from each pair) we get a bijection between subsets which have 0, 1 or 2 elements mod 3. So there are (2n-1):3 sets with i mod 3 elements excluding the fixed point and to count that point one should add "+1" for i=k mod 3.
And for n=2k+1 there are 2 fixed points — including or not (2k+1)-th element of S — with k+1 and k elements respectively.