PROBLEM: Count the number of 10 digit numbers with digits from $\{1, 2, 3, 4\}$ and no two adjacent digits differing by $1$.
I am able to provide a solution using recursion but it is a very tedious(non elegant) one using two recurrence relations.
I let $a_n, b_n, c_n, d_n$ be the number of $n$ digit numbers satisfying the conditions of the problem and ending in $1, 2, 3, 4$ respectively. Then its easy to see that I got the following recursions:
$b_{n+1}=b_n+a_n$; $a_{n+1}=2a_n+b_n$; $a_n=d_n$ and $b_n=c_n$ The first two give $b_{n+2}-3b_{n+1}+b_{n}=0$ with $b_1=1, b_2=2$. Now I can solve the recurrence and find $2(a_n+b_n)$ which is the required answer.
But I am looking for a neater or an alernative way of doing this problem (maybe with just one recurrence). So, please help.