Recursion problem

Question

I need some help on these problems. I do not know where to begin. The book that I have does not explain much.

Can somebody walk me through on solving these type of problems? I already know the answers to these problems. I just want to know how to solve them using a tree.

Problem 1) A set T of numbers is defined recursively by

1. 2 belongs to T.
2. If x belongs to T, so does x+3 and 2*x.

Which of the following numbers belong to T? a) 6 b) 7 c) 19 d) 12

Problem 2) A set S of strings of characters is defined recursively by

1. a and b belong to S.
2. If x belongs to S, so does xb.

Which of the following strings belong to S? a) a b) ab c) aba d) aaab e) bbbbb

Book: Mathematical Structures for Computer Science

EDIT: new problem added.

Now, what about this problem:

Problem 3) A set M of numbers is defined recursively by:

1. 2 and 3 belong to M.
2. If x and y belong to M, so does x*y.

Do I create 2 separate nodes? One for 2 and one for 3?

Answer 1

Both problems would benefit from just getting starting on applying the rules a few times.

In problem (1) you've got two rules to apply to each existing member to generate new members (after which you can effectively forget that one).

$2\overset{\times 2}{ \longrightarrow} \color{red}4$
$2\overset{+3}{ \longrightarrow} \color{blue}5$
$\color{red}4\overset{\times 2}{ \longrightarrow} 8$
$\color{red}4\overset{+3}{ \longrightarrow} \color{orange}7$
$\color{blue}5\overset{\times 2}{ \longrightarrow} 10$
$\color{blue}5\overset{+3}{ \longrightarrow} 8$
$\color{orange}7\overset{\times 2}{ \longrightarrow} 14$
etc.

A few more steps of this will convince you of at least the answers to the question asked.

Problem (2) only has one rule, which is even easier and the pattern should become apparently really quickly.

$a\overset{\&\,b}{ \longrightarrow} ab$
$b\overset{\&\,b}{ \longrightarrow} bb$
$ab\overset{\&\,b}{ \longrightarrow} abb$
etc.