Ways to Pass around a ball Five people are passing a ball amongst themselves. The ball starts with Alonzo. Each person who has the ball passes it onto someone else. After the eighth pass, the ball returns to Alonzo. Find the number of possible sequences of passes.
I know that since there are 8 passes, there are $4^8$ ways of passing the ball when there are no restrictions and after $7$ passes there would be $4^6$ ways to pass the ball back to Alonzo. How do I continue?
 A: Let's work recursively, restricting to those paths that start with $A$ (we put $A$ in the $0^{th}$ slot of the string).
Let $a_n$ be the number of paths of length $n$ that end in $A$.  To fix the notation, let's say that the initial $A$ is not counted in the length.  So, we have $a_1=0$ for example, since we can't put $A$ in slot $1$.
Let $b_n$ be the number of paths of length $n$ that do not end in $A$.  Then, $b_1=4$ for example.
As you remark, we have $$a_n+b_n=4^n$$
Recursively, we have $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$
That's already enough to solve your problem, and we get $$\boxed{a_8=13108}$$  A little extra work shows that $$a_n=\frac {4^n+4\times (-1)^n}5$$
A: Hint:
Let $a_n$ be the number of possible sequences of $n$ passes, where Alonzo starts with the ball, and Alonzo gets it back after the $n$th pass. Then $a_1 = 0$ and $a_2 = 4$.
Suppose we have a sequences of $n$ passes, where Alonzo starts with the ball, and each person who has the ball passes it onto someone else, but the last pass does not have to be to Alonzo. There are 4 choices for each pass, so there are $4^n$ possible sequences. In $a_n$ of these sequences, Alonzo is the last person to have the ball, which means there are $4^n - a_n$ sequences where Alonzo is not the last person.
Now use recursion. Note that Alonzo can't have the ball on the $n-1$th pass.
