Now, consider the following coin problem. So our goal is to prove that any integer amount starting from 8 can be paid using coins of denominations 3 and 5. Okay? So this is our problem, and let's try to investigate. So first of all, let's check whether 8 and 9 and 10 and 11 can be indeed paid. So this looks reasonable because 8 is 3 + 5, 9 is 3 + 3 + 3, 10 is 5 + 5, 11 is 3 + 3 + 5, so it seems to be possible. However, it is still not at all clear whether it is possible for all values. It is also not at all clear why are we talking about this problem in the lesson called recursion. Because recursion was about programs or about definitions. At the same time, what we are going to do is to prove that this is possible using recursion. And in fact, we are going to implement the program that is going to change any such amount into coins of denominations 3 and 5. So for this, as usual, let's think about these problems. So we know already that we can pay 8. But this immediately that we can also pay 11, right? Because 11 is just 8 + 3. So in a sense, we reduce the problem of change in 11 into coins to the problem of changing 8 into coins. But for 8, we that this is possible which means that for 8, for 11, it is also possible. Moreover, if you know how to change 8 then by adding just one single coin, you had a change for 11, right? And also 11 in terms, gives 14 then 17 then 20 and then so on. So an infinite number of amounts can be changed into points 3 and 5 just because 8 can be changed into 3 and 5, right? Then we would do the same trick with 9. So it seems we know how to change 9 then we know how to change 12, 15, 21 and so on. And 10 gives us 13, 16, 19, 22 and so on. Right? So this gives us the possibility to implement the following recursive procedure. We call the change, and it is given an amount that we need to change. And the first thing to do, we check whether the given amount is indeed greater than 8, right? Then if it is equal to 8 then we just return the representation of 8, the sum of 3 and 5. So we just return a list of two points. If it is equal to 9, we return three coins, 3, 3 and 3. If it is equal to 10, we return two coins, 5 and 5. On the other hand, if it is greater, then we do the following. We first subtract 3 from the amount. Then we make a recursive call which returns us the set of points needed to change the amount- 3, right? So we make a recursive call. We solve the same permutational problem. So with this point, we have some subset of coins, some list of coins that sum up to amount- 3. So if we add just one single coin with denomination 3 then we have a change for the whole amount, right? And this is exactly what we do here. We append 3 to coins, and we return the result in. Okay, so this is a recursive program, which changes any amount. And the fact that it changes any amount is guaranteed by the fact that if you get any number, which is greater than 8. And you start and you keep subtracting 3 from it, then at some point, you will reach either 8 or 9 or 10, right? So for this reason, this algorithm actually proves, this problem proves that any amount can be changed using coins with denominations 3 and 5. And it actually proves this constructively. Meaning that it not only proves that it is possible, it actually produces the answer for each possible amount.