Counting subsets with r mod 5 elements

Question

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\mod 5$ elements. Denote this number by, say, $P_n (r \mod 5)$.

An experiment shows that for small $n$, $P_n(r \mod 5)-P_n(r^{\prime} \mod 5)$ is always a Fibonacci number (recall that for "$r \mod 3$" corresponding difference is always 0 or 1 and for "$r \mod 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 \mod 3$"-case.)

And is there some theorem about $P_n(r \mod l)$ for arbitrary $l$ (besides that it satisfies some recurrence relation of degree growing with $l$)?

Answer 1

(Sketch of a bijective solution.)

Recall that binomial coefficients count number of walks with steps (+1,+1) and (+1,-1) from the origin to different points (e.g. the number of walks to the point (2n,0) is $\binom{2n}{n}$). Consider the following involution on the set of all such walks: if the path intersects with the line y=l-1 or the line y=-1, reflect its part starting from the first intersection point (w.r.t. corresponding line).

This involution almost gives a bijection between P_n(r mod l) and P_n(-r-2 mod l) (and moving the strip we can get other correspondences of this kind). But it has some fixed points — namely, paths that lie inside the strip 0≤y≤l-2 (aka walks on the path graph of length l-1 mentioned by Qiaochu Yuan).

Now to answer original question one only needs to recall that numbers of such paths for l=5 are exactly Fibonacci numbers.