recursive defined set Let $ S $ be a recursively defined set : \begin{align} 6 \in S\\ n \in S \rightarrow 4n+2 \in S , \\ n \in S \rightarrow n^{2} \in S  \end{align}. Prove that every element of $ S $ has a last digit 6 (end with 6) in their decimal expansion i.e; $ \ x \in \ S \ \ implies \ \ x \equiv 6 \ (mod \ 10 ) \ $. $$ $$ Given $ \ \ \ 6 \ \  \in S \  , \ \ 4n+2 \in S \ , \ \ n^{2} \in S $. From these we have to construct a formula f(n) so that $ f(n) \equiv 6 \ (mod \ 10) $. Please help me doing this.
 A: All elements in $S$ are natural numbers. Suppose that the statement is not correct, then let us consider the smallest element $x \in S$ which doesn't have $6$ as its last digit. 
If $x$ is a square of some number from $S$, then it means that there exists $n \in S$ such that $n^2 = x$. But $n < x$, so $n$ has $6$ as a last digit $\Rightarrow$ so does $x = n^2$. 
If $x$ was got as $x = 4n+2$ for some $n \in S$, then, again, $n < x$, so $n$ has $6$ as a last digit $\Rightarrow$ so does $x = 4n+2$.
So we have a contradiction, which means that our initial assumption that such $x$ exists was false.
A: Best way to do it is by induction:
If $n \equiv 6 \mod 10$ then $n^2 \equiv 36 \equiv 6 \mod 10$ and $4n +2 \equiv 4*6 + 2 \equiv 26 \equiv 6 \mod 10$.
That's it.
.....
But I didn't define $f(n)$.  I don't think you need to but... for $n \in \mathbb N$ (doesn't include zero).
Let $f(1) = 6$. $f(1) \equiv 6 \mod 10$.
If $n$ is even $f(n) = 4f(\frac n2)+ 2$ (if $f(\frac n2) \equiv 6 \mod 10$ then $f(n) \equiv 4*6 + 2\equiv 6 \mod 10$.)
If $n$ is odd but $n > 1$ then $f(n) = (f(\frac{n-1}2))^2$ (if $f(\frac{n=1}2)\equiv 6 \mod 10$ then $f(n)\equiv 6^2 \equiv 6 \mod 10$.)
....hmmm. using this definition I'm a little curious to find the first $f(n) = f(m); n \ne m$.  .... but not curious enough to do it...
