Counting subsets with r mod 5 elements

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$)?

• In general your $P_n$ (r mod l) will be a linear combination of terms $(1+\zeta)^n\pm (1+\zeta^{-1})^n$ where $\zeta$ runs through the $l$-th roots of unity. When $l=5$ then these involve powers of $2$ and also powers of the golden ratio, as that is involved in $\cos \pi/5$ and $\cos 2\pi/5$. – Robin Chapman Aug 2 '10 at 11:04
• @Robin Yes, I thought about it (although I was too lazy to carry out actual proof from this) but it's more like solving recurrence relation (packed into generating function, but anyway) and it would be nice to have a combinatorial proof. – Grigory M Aug 2 '10 at 11:25
• Take the graph whose vertices are the vertices of a regular l-gon and whose edges are its edges. Then, for example, P_n(0 mod l) is the number of walks of length n on this graph which begin and start at a particular vertex. The bijection is that going left corresponds to having a particular element in your subset and going right corresponds to not having it. The Fibonacci numbers admit a similar interpretation (on more than one graph!) so one might be able to do something from here. – Qiaochu Yuan Aug 2 '10 at 17:52
• In particular, Fibonacci numbers count walks on the path graph of length 4, which is the one I think will be relevant to this problem. – Qiaochu Yuan Aug 2 '10 at 20:02
• The proof of the Rogers-Ramanujan conjecture in Andrews and Eriksson's book Integer Partitions books.google.co.uk/… relies, in effect, on a $q$-analogue of the relation between Fibonacci numbers and the differences between the "Pn(r mod 5)". – Robin Chapman Aug 6 '10 at 19:29

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).