Divide a line segment into four equal parts. Do nothing with the first three parts, but shade in the fourth. Now take the interval and append it to itself and shade in the last quarter of the new interval. Take the shaded quarter of the very first iteration and count the number of times it or any of its duplicates are not shaded by a larger segment. This is F. Observe that F(1)=1, and F(2)=1. Each time the segment is doubled, only half of the new length will be unshaded. Let s(n) be the sum of F(1) through F(n). Then each iteration of doubling adds F(n-2) to s(n-1). Thus F(n) = F(n-1) + F(n-2).

The original segment was divided into four parts, and each iteration doubled the segment. Thus, the interval corresponds to counting in binary. This can be seen as duplicating the existing numbers and appending a 0 on the first half, and a 1 on the second half. Thus the shaded segment corresponds to a binary number that ends in "11". In fact, any shaded segment corresponds to a binary number that contains "11".

Any binary number that contains "11" will yield a positive value when bitwise ANDed with itself divided by 2.

Iterate over the values from 0 to 4*2^n, taking each value bitwise ANDed with itself divided by 2. Then, by the above, the count of the number of 1's in the interval is equivalent to F(n-1).