Very nice problem. One hint is to look at the number of ways to pay for exactly n hours. I tried several small n's, and for each n I drew a binary tree. For each node, one child corresponds to paying $1, the other $2. Each tree node may be labeled with the amount left. After doing an exhaustive search of ways to pay in this manner, I noted that some parts of trees for larger n's are copies of trees for smaller n's.

Of course, this is just what I tried; this may not be the easiest or the most intuitive way to approach the problem.