Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4).
The story becomes even more interesting if one asks about number of subsets of n-element set with $r\bmod 5$ elements. Denote this number by, say, $P_n (r \bmod 5)$.
An experiment shows that for small $n$, $P_n(r \bmod 5)-P_n(r' \bmod 5)$ is always a Fibonacci number (recall that for "$r \bmod 3$" corresponding difference is always 0 or 1 and for "$r \bmod 2$" they are all 0). It's not hard to prove this statement by induction but as always inductive proof explains nothing. Does anybody have a combinatorial proof? (Or maybe some homological proof — I've heard one for "$r \bmod 3$"-case.)
And is there some theorem about $P_n(r \bmod l)$ for arbitrary $l$ (besides that it satisfies some recurrence relation of degree growing with $l$)?