I know similar questions have been asked before and I've had a look through them but I'm still struggling to understand, so please bear with me.
The question asks you to find a recurrence relation for A of n.
I'm not making the connection between the first sentence in either case and how this implies that this is equal to the number of strings in the previous term(s); n - 1 and n - 2.
This a question from an assignment for a Discrete Maths paper.
In the first case, there is a one to one map between the strings contributing to $a_n$ not starting with $0$ but with another fixed number say $1$ and the strings contributing to $a_{n-1}$. That is, every string contributing to $a_{n-1}$ gives a string contributing to $a_n$ by appending a $1$ at the left end, and vice versa. Since we can do this for all of $1,2,3,4$, we get a factor of $4$.
In the second case, there is a one-one correspondence between the strings contributing to $a_n$ beginning with $0$ and having a fixed second digit (say $1$) and the strings contributing to $a_{n-2}$. Specifically, given a string contributing to $a_n$ starting with $01$, it corresponds to the string formed by its last $n-2$ letters. Since we could have any of $1,2,3,4$ instead of $1$, there is again a factor of $4$.