Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\lbrace 2n+3m+1:n,m\in N\rbrace$ is the set of all positive integers except for $0$ and $2$. I need to know how to write its inductive definition.

This is part of the introduction on learning how to develop recursive functions using lambda calculus. I can do some of them but on others, such as this one, I get lost. How do you handle the multiple variables. Please explain how you got your answer as well since an answer doesn't do me much good if I don't know how to get it.

Here are two of the ones I know how to do.

$\lbrace 3n+2: n\in \mathbb N\rbrace$

Top Down: $n = 2; n - 3 \in S$

Bottom up: $2 \in S$; if $n \in S$, then $(n + 3) \in S$

Rule of Inference: $2 \in S$; if $n \in S$, then $(n+3) \in S$

$\lbrace(n,2n+1): n\in \mathbb N\rbrace$

Top Down: $(n,m)=(0,1);(n-1,m-2) \in S$

Bottom up: $(0,1) \in S$; if $(n,m) \in S$, then $(n+1,m+2) \in S$

share|improve this question
So, which of the three things "Top Down", "Bottom up", "Rule of Inference" is the inductive definition for $\lbrace3n+2:n\in N\rbrace$? –  Gerry Myerson Sep 1 '11 at 4:55
By the way, I edited a little TeX into the first line of your question. You can see how I did it, and then edit the rest yourself, if you like the way it looks. –  Gerry Myerson Sep 1 '11 at 4:57
@Gerry They are all inductive definitions. They all mean the same thing it's just different ways of writing it. Top down is the most important method because later in the class when I have to write programs that check to see if something is in a set, I would have to use Top down because of the way programming works. –  C Dawg Sep 1 '11 at 5:08

3 Answers 3

up vote 0 down vote accepted

A solution could be found by starting with $1$. Then, if $n\in S$, you require $n+f(n)\in S$ too, where $f(n)$ is 2 for $n=1$ and $1$ otherwise. One way to do this is to make use of the step function $\frac{x}{|x|}$, which is $-1$ for negative input and $+1$ for positive input. Inserting a horizontal shift so that the discontinuity is at $2$ rather than $0$, scaling down by 2 (since we want a span that's $1$ unit long, not $2$), inverting vertically since we want the larger jump to happen earlier, and shifting up by the proper amount ($\frac{3}{2}$)...

$$f(n) = \frac{3}{2}-\frac{n-2}{2|n-2|}$$

(Edited: I had it completely backwards the first time!)

So that means you can have: $1\in S$; if $n\in S$, then $n+\frac{3}{2}-\frac{n-2}{2|n-2|}\in S$.

EDIT: For moving down...

You just need a different step function: one with its discontinuity between $3$ and $4$. Also, it's negated from the one used for moving up.

$$g(n)= -\frac{3}{2}+\frac{n-3.5}{2|n-3.5|}$$

And then: $1\in S$; if $n\in S$, then $n-\frac{3}{2}+\frac{n-3.5}{2|n-3.5|}\in S$.

share|improve this answer
Of course, $f$ could just be defined piecewise with 'if's and 'then's, but I don't think that's what you are after. –  alex.jordan Sep 1 '11 at 6:12
How would I invert that for top down form? For top down I would need: n - f(n) where f(n) = -2 when n = 3 and -1 otherwise. –  C Dawg Sep 1 '11 at 22:54

How's this: 1 and 4 are in $S$; if $n$ is in $S$, then $n+2$ is in $S$.

share|improve this answer
The problem is that I need one definition that works for every number in the set. A small sample of the set is (1,3,4,5,6,7,8,9,10...). With n+2 starting at 1, I would only get the odd numbers and miss out on all the even numbers that are in the set. The problem is that it's every natural number except 0 and 2 and I just can't find a rule that will only skip those two numbers. I've been trying with top down and I've been working around the idea of something like n=1; ((n-2)+(n-3)) ∈ N and numerous variations of it but my definitions either skip numbers or don't skip the 0 and 2. –  C Dawg Sep 1 '11 at 5:49
@C Dawg: Gerry’s definition works for every number in the set, because he specified that both $1$ and $4$ are in $S$; $n+2$ gives you the odd natural numbers starting at $1$ and the even natural numbers greater than $2$ starting at $4$. –  Brian M. Scott Sep 1 '11 at 6:00
I think this answer is great. The OP might be objecting because he wants something that simultaneously indexes the set; i.e., has a single seed. @C Dawg: Is that what you are looking for? –  alex.jordan Sep 1 '11 at 6:22

The most straightforward bottom up definition description of $S=\lbrace 2n+3m+1:n,m\in N\rbrace$ can be read directly from the expression $2n+3m+1$. The base case is clearly $n=m=0$, giving $1 \in S$. The term $2n$ tells you that if $k \in S$, then $k + 2 \in S$, and similarly, the $3m$ term tells you that if $k \in S$, then $k + 3 \in S$: these rules correspond to incrementing $n$ and $m$, respectively, by $1$. In short:

  • $1 \in S$;
  • if $k \in S$, then $k+2 \in S$; and
  • if $k \in S$, then $k+3 \in S$.

This is not the most efficient recursive description of $S$, but it is the one that most directly matches the definition that you’ve been given. After you prove that $S$ is in fact the set of all positive integers except $2$, you can give a simpler recursive description $-$ Gerry Myerson’s, for instance.

I’m not familiar with your top down style of description, but if I’ve extrapolated correctly from your first example, the top down version of the bottom up description that I just gave is:

  • $n=1$;
  • $n-2 \in S$; and
  • $n-3 \in S$.

(Your top down version for $\lbrace(n,2n+1): n\in N\rbrace$ must be incomplete; I’m guessing that the rest of it should be $(n-1,m-2) \in S$.)

share|improve this answer

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.