TITLE: Is there a neat way to count this?
QUESTION [1 upvotes]: What is the number of  strings of length $n$ formed by the digits ${1,2,3,4,5}$ such that two consecutive entries are not same and $1$ and $2$ doesn't come consecutively ?
I tried inclusion exclusion but that is getting messy. Is there a neat way out ?

REPLY [3 votes]: Let $A_n$ be the number that end in $1$ or $2$; and $B_n$ the number that end in $3$, $4$ or $5$.
$A_1=2,A_2=8,B_1=3,B_2=15$.
Find a recursion for $A_{n+1}$ in terms of $A_n$ and $B_n$; and a similar recursion for $B_{n+1}$.
{"set_name": "stack_exchange", "score": 1, "question_id": 1664034}