More math help!

[The_OG_Nelta]

I'm trying to find the number of ways to pay 8$ into a vending machine where the machine only accepts 1$, 2$ and 5$

I need to do this with recursion

I understand that you denote an = # of ways to pay N dollars

and you do the recursion by finding the number of ways to pay 8$ with respect to the first coin you drop

The thing I'm confused about is how to iterate the initial conditions.

If this example is too hard, perhaps try to answer this question..

How many strings of N-digits contain an even number of zeroes

again, I understand how to setup the recursion to solve for an, but not the initial conditions.

[Awoir]

Does order matter?
Like is 5-2-1 different from 2-5-1?

[The_OG_Nelta]

Let me try to explain the first few steps to let you know what I mean by iterating the initial conditions.

First, I let an = number of ways to pay n dollars

now we solve by cases.

1) if the first coin dropped is 1$, then you have (an-1) ways of paying 8 dollars
2) if the first coin dropped is 2$, then you have (an-2) way sof pyaing 8 dollars
3) if the first coin dropped is 5$, then you have (an-5) ways of paying 8 dollars.

so now you can come up with a recursion formula as follows:

an = (an-1) + (an-2) ------------- for n<5

and

an = (an-1) + (an-2) + (an-5) ---- n>5

note: the n-x is a subscript

obviosly you need to solve for a8

but you need initial conditions to start the iteration from a2
to solve for a2, you need a1 and a0 to start off your iteration. using the 1st equation.

my notes say:

a0 = 1 -> pay nothing
a1 = 1 -> {1,1} {2,0}

I get how to do the rest, but not the initial conditions.