Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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 9: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 9:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.