I think I know how to solve i. and ii., but not iii:
Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$.
(For i and ii): Prove that if $(a,b) \in S$, then $a+b$ is divisible by $3$.
i. Prove the basis step. ii. Prove the recursive step. State what you assume clearly.
Here is the tricky part:
iii. Show that the converse of the statement above is not true, i.e. if $a,b \in\Bbb N$, and $a+b$ is divisible by $3$, it does not follow that $(a,b) \in S$. Modify the recursive definition of $S$ to make the converse true.
iii. We can't get neither $(3,0)$ nor $(0,3)$, for instance, because from the first step on, both members of the pair are positive.
Also, by induction, one can prove that $(a,b)\in S,\ a+b=3n\ \implies |a-b|\le n$. It follows that no pairs of the form $(n-c,2n+c)$ are in $S$ if $0<c< n$.
One possibility to make it use up all $(a,b)\in\Bbb N\times\Bbb N$ is to extend the rules by: $$(a,b)\in S \implies (a,b+3)\in S,\ (a+3,b)\in S\,.$$ So that, if for a pair $(a,b)$ we have $a+b=3n$, then this is built in exactly the $n$th step.