A set S is defined recursively by

Question

A set $S$ is defined recursively by

Basis step: $0 \in S$

Recursive step: if $a \in S$, then $a + 3 \in S$ and $a + 5 \in S$.

Questions:

1. Determine the set $S \cap \{ a \in \mathbb Z \mid 0 < a < 12 \}$.
2. Prove that every integer $a ≥ 8$ is contained in $S$.

Which steps do I need to take ?

Answer 1

The set $S$ is equivalent to the set of all integers of the form $3n+5k$ for some $n,k\in\Bbb Z_{\ge 0}$.

For 1, you simply find which of the integers from the set $\{1,2,\ldots,11\}$ are also in $S$, or i.e. are also of the form $3n+5k$ for some $n,k\in\Bbb Z_{\ge 0}$.

2 is a direct result of Frobenius Coin Problem (also called Chicken McNugget Theorem or Postage Stamp Problem), which states:

If $a,b>0, (a,b)=1$, then the largest integer not of the form $an+bk$ for some $n,k\in\Bbb Z_{\ge 0}$ is $ab-a-b$.

Or you can simply see $3n, 3n+5, 3n+10$ with $n\in\Bbb Z_{\ge 0}$ generate all the integers $\ge 8$.

Answer 2

1. $\{3,5,6,8,10,9,11\}$

2 Consider three cases: $n=3k$, $n=3k+1$, and $n=3k+2=3(k-1)+5$ (Note that $3\in S$.)

Answer 3

The set $$ S':=\{0,3,5,6\}\cup\{\,k\in \mathbb Z\mid k\ge 8\,\}$$ is readily showsn to fulfill the conditions: It contains $0$ and if it contains $a$ it also contains $a+3$ and $a+5$. Hence certainly $S\subseteq S'$. Assume $S\ne S'$ and let $n$ be the minimal element of $S'\setminus S$. Certainly $n\notin\{0,3,5,6,8,9,10\}$ as these are immeditaly shown to be in $S$ (e.g., $0\in S\implies 5=0+5\in S\implies 8=5+3\in S$). Therefore $n\ge 11$. But then $n=k+3$ for some $k\ge 8$, where $k\in S'$ and by minimality of $n$ also $k\in S$. Hence $n=k+3\in S$, contradiction. We conclude that indeed $S=S'$, hence immediately the second task and $\{3,5,6,8,9,10,11\}$ for the first task.