[MUSIC] Here is our next example. It is called a vending machine problem. Suppose you have sufficiently many coins of 5 cents nickels. 10 cents, dimes. And 25 cents, quarters. And you have a vending machine selling, say, kinds of soda. And suppose that kind of soda costs $1. And the question is, in how many ways can you pay a certain amount, say, $1? In how many ways, Can you pay, $1 or any other amount? So since you have a vending machine, the order of throwing coins into the machine is important. So, say, if you're paying 5+10+10+3 quarters, This is not the same as paying, say, 10, then a quarter, then again 10, then 5, and then 2 quarters. We'll consider these two configurations as different ones. Okay, it is obvious that we only can pay amounts in cents which are divisible by 5. So denote a number of ways of paying 5n cents. Number of ways, To pay 5n cents by A(n). Okay, so what can we say about this, This sequence? So if we're interested in the number of ways to pay $1, this will be A(20). Okay [COUGH] let us form the following table. So here we will have n. And below we will have A(n). So if n is equal to 5, Then this is just 5 cents. And 5 cents can be paid in a unique way. So for n equal to 2, well, 10 cents can be paid either by one 10 cent coin or by two 5 cent coins. So this is 2. 15 cents can be paid in three ways. Okay, for 4, the number of ways to pay 20 cents is equal to 5. And so far, we have the Fibonacci sequence. Okay, we also formerly say that the number of ways of not paying anything will be 1. We will need this in a minute. So if our A(n) coincides with the Fibonacci numbers, and this is pretty clear. Because we had our previous description that the Fibonacci number is equal to the number of compositions, to the number of presentations of n as the sum of 1s and 2s. And paying 5n cents by nickels and dimes is exactly a composition of 5n into 1s corresponding to nickels and 2s corresponding to dimes. And if the amount that we're paying is less than 25 cents, we cannot use quarters. Okay, so what happens now? What happens if, We want to pay 25 cents? So this can be done in several ways. So how to pay, 25 cents? Well, the first possibility is just to pay 1 quarter. And this can be done in a unique way. Then, another possibility is that, as our first coin, we use a dime. And then this means that we need to pay another 15 cents. And this can be done in three possible ways. So if we pay 10 cents plus something, this can be done in three ways. So this is A(3). And if the first coin that we use is a nickel, this means that we have A(4) = 5 possibilities, To pay another 20 cents. So the total number is 1 plus 3 plus 5, that is 9. Okay, so what about n equal to 6? In how many ways can we present 6 as a sum of 5s, 1s, and 2s? So same question about 30 cents. So if we pay a quarter at first, we have A(1), just one possibility. If we start with a dime. We have 5 possibilities. If we start with a nickel, then the number of possibilities is 9. So this makes 15. From this, we can already deduce the recurrence of relation for A(n). Namely, A(n), the number of ways of paying 5n cents by nickels, dimes, and quarters is equal to A(n-1). Which corresponds to using a nickel as the first coin. + A(n-2), which corresponds to using a dime first. + A(n-5), which means that the first coin you use is a quarter. So here is our recurrence relation. And it looks pretty similar to their relation for Fibonacci numbers. But in this case, the nth term in this sequence depends, not only from the previous two, but from the previous five of them. So this is called a recurrence relation of order five. And now, we will give a general definition of a recurrence relation. [MUSIC]
