Counting subsets with r mod 5 elements

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