← All solutions

There’s a relatively straightforward dynamic programming solution which is probably the first one typically comes up with, but here’s a much cooler solution found by Derek Kisman: we can think of the process of going from F (n − 1) to F (n) as a string replacement rule: every 1 becomes replaced by 10, and every 0 becomes replaced by a 1. In order to compute the number of occurrences of p in F (n), we can apply these rules backwards to obtain a shorter string p′ , and the task is now to find the number of occurrences of p′ in F (n − 1) (if p ended in a 1 there are two possibilities for p′ since we don’t know whether that last 1 came from a 1 or a 0 in F (n − 1)). Recursing this process, we are ultimately looking for the number of occurences of either 1 or 0 in F (n′ ) for some n′ < n, which simply equals f (n − 1) and f (n − 2), respectively.