0

I'm preparing for an upcoming exam on Discrete Maths, and I've come across the following past exam question which I don't quite understand:

An ATM dispenses only \$20 and \$50 notes. Let M be the set of amounts of money that the ATM can dispense

Write down a recursive definition of M

As I understand it, a recursive statement is something in the form of: $a_{n} + a_{n-1} - 5a_{n-2} = 0$

I do understand what a recurrence relation is basically - and I know how to solve a recurrence given initial statements $a_{0}$ and $a_{1}$ but I'm finding these types of questions a bit confusing as there doesn't seem to be any standard algorithm or technique for it

What confuses me even more with this question is the answer that is given is:

If \$m belong to M then \$$(m+20)$ belong to M and \$$(m+50)$ belong to M

Which is not really in the form that I'm more familiar with - but I suspect it can also be rewritten in the normal form?

Arvin
  • 1,733

1 Answers1

3

The difference here is that usually we have a sequence of numbers defined recursively, and here you have a set defined recursively. Here is one way to "standardize" this in terms you know:

Let us define a sequence $M_n$ of sets in the following way: $M_1=\{0\}$ and $M_{n+1}=M_n\cup (M_n+20)\cup (M_n+50)$, where $M_n+20$ means the set obtained from $M_n$ by adding 20 to every element.

Now define $M=\bigcup_{n=1}^\infty M_n$.

This is the closest way to bring this to a form you know. However, if you are given a test question like this, I guess they'll expect solution like the one you quoted.

Gadi A
  • 19,265
  • 1
    To put it another way, "recursive" just means things are defined in terms of things already defined. So, your "recursive statement" defines $a_n$ as $-a_{n-1}+5a_{n-2}$, and the ATM answer is that a member of $M$ is 20 or 50 more than a previously obtained member of $M$. – Gerry Myerson Jun 20 '11 at 09:20
  • Hmmm, I see, so M being the set of amounts of money that the ATM can dispose means it is the set containing: {0, 20, 40, 60, 70, 90...} and:

    $M_{1} = 0$, $M_{2} = 0 \cup (0+20) \cup (0+50)$

    And keep going to build the set that way. That makes sense. I'm still not confident enough to be able to figure it out for a different question, but I'll see how I go. thanks!

     – Arvin Jun 20 '11 at 09:40