About Recurrence Relations.

Question

I need help in order to solve the following question,

Here RR is for Recurrence Relations.

Answer 1

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.

Answer 2

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.