TITLE: Recurrence Relation Models
QUESTION [0 upvotes]: 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.

REPLY [2 votes]: $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.
{"set_name": "stack_exchange", "score": 0, "question_id": 548637}