Number of ways to pass balls such that whoever starts with the ball ends with the ball $4$ basketball players play a game of ball passing, with either one of them holding the ball at the start.
In each turn, the ball is passed from whoever is currently holding the ball to either of the other $3$ players, however, the players are not allowed to pass the ball back to who he received it from.
How many ways are there such that after $n$ turns, whoever starts with the ball ends with the ball?
I tried listing out the number of ways in terms of $n$ and there seems to be an exponential relationship, but I was unable to find the number of ways exactly in terms of $n$.
 A: Let $f(n)$ be the number of ways to get from A to A in exactly $n$ moves coming from C
Let $g(n)$ be the number of ways to get from A to B in exactly $n$ moves coming from C
Let $h(n)$ be the number of ways to get from A to C in exactly $n$ moves coming from C
(Note that these are essentially the only three possible cases: loop / different from previous / same as previous)
Now consider the first move, which has to go to B or D
$f(n) = 2 h(n-1)$ (In either case you have to get back to A, so that's essentially same)
$g(n) = f(n-1) + g(n-1)$ (If you go to B, it's a loop; if you go to D, it's different)
$h(n) = 2 g(n-1)$ (In either case it's different)
Now can you solve this set of simultaneous recursive relations?
A: Let ${\cal W}_n$ $\>(n\geq1)$ be the set of admissible words $w=(x_0,x_1,\ldots,x_n)$ over the alphabet $\{A,B,C,D\}$ with $x_0=x_n=A$. Our task is to compute the numbers $g_n:=\#{\cal W}_n$.
Let $n\geq4$ and consider a word $w\in{\cal W}_n$. The last four letters of this word are either $AXYA$ or $XYZA$, where $X$, $Y$, $Z$ are three different letters from $\{B,C,D\}$. Therefore $w$ can be written in one of the two forms  $$({\rm a}):\quad w=w'AXYA\qquad{\rm or\qquad (b):}\quad w=w'XYZA\ .$$ 
In  case (a) we have $w'A\in {\cal W}_{n-3}$. On the other hand it is easy to see that each $w'A\in {\cal W}_{n-3}$ can be extended in four admissible ways to a word $w'AXYA\in {\cal W}_n$. 
In case (b) we can cross out the $Z$ and obtain the word $w'XYA\in {\cal W}_{n-1}$. On the other hand, each word $w'XYA\in {\cal W}_{n-1}$ can be extended  in a unique way to $w'XYZA\in {\cal W}_n$ by insertion of a $Z$.
It follows that the $g_n$ satisfy the recursion
$$g_n=g_{n-1}+4 g_{n-3}\qquad(n\geq4)\ .\tag{1}$$
The characteristic polynomial of $(1)$ has the roots $2$ and $\lambda_\pm:={1\over2}\bigl(-1\pm i\sqrt{7}\bigr)$. Therefore
$$g_n= a\> 2^n + b\>\lambda_+^n +\bar b\>\lambda_-^n\qquad(n\geq4)\ ,$$
where $a$ and $b$ have to be determined from the initial values  $g_1=0$, $g_2=0$, $g_3=6$.
