Okay, let's call the number of ways in which you can the bill of n dollars.

Note that if we want to pay a bill of n+1 dollars we can add a coin of a dollar to n dollars, this can be done in ways, now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

(1)

Now for this to always make sense we define if and (there's only one way of paying nothing) and then is defined by (1) if