Recursion definition

Question

Give a recursive defintion of the following set: $\{ 5^m 7^n \mid m, n \in N \}$

I don't have the slightest idea how to approach this question, id be really grateful if someone could provide me with guidance

Answer 1

Think about how you'd generate all the members of that set. You start with $1$. Then, given a number $x$ that you already know to be in the set, you add both $7x$ and $5x$ to the set. Formally, you can write that as $$\begin{eqnarray} A_0 &=& \{1\} \\ A_{n+1} &=& \{5x \,|\, x \in A_n\} \cup \{7x \,|\, x \in A_n\} \\ A &=& \bigcup_{n=0}^\infty A_n \text{.} \end{eqnarray}$$

Answer 2

Another way of putting fgp's answer (assuming that $N = \{0,1,2,\dots\}$): It's the set $X \subseteq N$ consisting of all $k \geq 1$ such that either $k = 1$, $k/5 \in X$, or $k/7 \in X$.

Answer 3

You can also order the set by first including all the $n+m=0$, then all the $n+m=1$, etc.

$$U_s = \bigcup_{m=0}^s 5^m7^{s-m}$$

$$A_0 = \{\}$$ $$A_s = A_{s-1} \cup U_{s-1}$$

Anyway you define your recursion, you are going to need either 2 recursive variables or 1 recursive variable and a quantified variable (like the variable of the union or set comprehension).