About Recurrence Relations. I need help in order to solve the following question,

Here RR is for Recurrence Relations.
 A: Let $a_n$ be the number of strings of length $n$ with an odd number of $1$'s.
Let $b_n$ be the number of $n$-strings with an even number of $1$'s.
We have the following recurrences:
$$a_{n+1}=3a_n+b_n,\tag{1}$$
and
$$b_{n+1}=a_n+3b_n.\tag{2}$$
To justify Recurrence (1), note that we get a string of length $n+1$ with an odd number of $1$ in two ways: append $0$, $2$, or $3$ to an $n$-string with an odd number of $1$'s or (ii) append a $1$ to an $n$-string with an even number of $1$'s. The justification of Recurrence (2) is very similar. 
Now there are many ways to proceed. I would express Recurrences (1) and (2) in matrix form, and use matrix manipulations to find a general expression for $(a_n,b_n)$. Or else we can note that $b_n=4^n-a_n$, and obtain from (1) the recurrence
$$a_{n+1}=2a_n+4^n,\tag{3}$$
which you probably have the tools to solve. Or else I would note that from (1) we have $b_n=a_{n+1}-3a_n$. So from (2) we have $b_{n+1}=a_n+3b_n=3a_{n+1}-8a_n$,
Now bumping up the subscripts of (1) by $1$, we get $a_{n+2}=3a_{n+1}+b_{n+1}=
6a_{n+1}-8a_n$. That yields the second-order recurrence
$$a_{n+2}=6a_{n+1}-8a_n.\tag{4}$$
We can solve this by using the characteristic polynomial $x^2-6x+8=0$, and for the initial conditions noting that $a_0=a_1=1$.  
Two suggestions, plus the matrix one. And there are others, such as generating functions. I do not know which ones are stressed in your course. 
A: Note that total number of strings in $\Sigma^n$ is $4^n$. Let $a_n$ be the number of strings containing odd number of 1's. Then number of strings containing even number of 1's is $4^n-a_n$.
Consider any string of length $n$ containing odd number of 1's. Now, there could be two cases i) a string may start with 0,2,3  ii) a string may start with 1. 
What is the number of strings of first type? First place is filled up by one of the 3 characters. The remaining $n-1$ characters in those string contain odd number of 1's. Number of strings of length $n-1$ and having odd number of 1's can be computed recursively which is $a_{n-1}$. Thus number of strings of first type is 3*$a_{n-1}$.
What is the number of strings of second type? In this case the first character can be only 1. The remaining $n-1$ characters in those string contain even number of 1's. Number of strings of length $n-1$ and having even number of 1's can be computed recursively which is $4^n-a_{n-1}$, which is same as the number of strings of second type.
Thus total number of strings in $\Sigma^n$ having odd 1's, $$a_n = 3a_{n-1}+4^n-a_{n-1}=2a_{n-1}+4^n$$
For solution of this recurrence you can refer to Expansion method. 
