Recurrence Relation Models

Question

Find a recurrence relation for $a_n$, the number of ways to give away $1$, $2$, or $3$ for $n$ days with the constraint that there is an even number of days when $1$ is given away.

Answer 1

$a_{n+1}=2a_{n}+(3^{n}-a_{n})$.

The intuition behind this is that if you have a list of $n$ numbers with an even number of $1$'s then you can add $2$ or $3$ at the end and it still has an even number of $1$'s.

Since the number of lists of $n$ numbers with all elements of the list $1,2$ or $3$ is $3^n$ then that means that there are $3^n -a_n$ that don't have an even number of $1$'s. That means if we add $1$ at the end it will have an even number of $1$'s.