Recursive definition of binary Strings

Question

I am have a bit of trouble on how I can provide a recursive definition for all binary strings that represent a number divisible by 4. I know that for such definitions you need a basis step and a recursion step. I know for a fact that a number is divisible by 4 if and only if the last 2 digits are even and they can be divided evenly by 4. I tried taking a stab at it and thought for the basis step all I can provide is something like

Basis Step: $\alpha$ is a binary string

Recursive Step: If $\beta$ $\in$ S .......

How could I represent that what I know about being divisible by 4 to finish this definition off??

Answer 1

Any binary number divisible by $4_{10}$ ends in $...100$. So just recursively pre-pend any binary digits in front of that.

$\alpha 100 \to \beta \alpha 100$ for $\beta \in \{ 0, 1 \}^k$.

Done!