In how many ways can the basketball be passed between four people so that the ball comes back to $A$ after seven passes? (Use recursion) There are four basketball players $A, B, C, D$. Initially, the ball is
with $A$. The ball is always passed from one person to a different
person. In how many ways can the ball come back to $A$ after seven
passes? (For example $A \mapsto C \mapsto B \mapsto D \mapsto A \mapsto B \mapsto C \mapsto A$ and $A \mapsto D \mapsto A \mapsto C \mapsto A \mapsto B \mapsto C \mapsto A$)
I know that it can be done considering cases (location and the number of passes received by $A$ in between). But I'm interested in learning some recursion. So, it would be good if some explicitly explains how to get the recursion. Not just the recursion, but how to "derive" it.
 A: Note that there are only two states:  either A has the ball or somebody else has it.  Define $f(n)$ as the number of ways to pass the ball $n$ times so that $A$ has it at the end and $g(n)$ as the number of ways to pass the ball $n$ times so that somebody else has it at the end.  We start with $f(0)=1, g(0)=0$ because after $0$ passes $A$ has the ball.  If somebody else has the ball there is $1$ way to pass it to $A$, so $f(n+1)=g(n)$.  If $A$ has the ball there are three ways to pass it to somebody else, while if somebody else has it there are two, so $g(n+1)=3f(n)+2g(n)$
A: Let $b_{i,n}$ be the number of ways to get the ball to player $i$ in $n$ passes, where $i = 1,2,3,4$ corresponds to $A,B,C,D$.  First you answer the question, "What is $b_{i,0}$ for each $i$?"  The answer should reflect the initial condition, which says that $A$ has the ball.  Hence $b_{1,0} = 1$ and $b_{j,0} = 0$ for $j \neq 1$.
The next question sets up the recursion: "What is $b_{i,n+1}$ in terms of $b_{j,n}$ (for all $j$)?"  For example, there are 3 ways to get the ball to $A$ ($j=1$) in two passes, and 2 ways to get the ball to everybody else ($j=2,3,4$) in two passes.  If the ball is in $A$'s hands after two passes, someone else will have it after the third pass.  However, if someone else has the ball after two passes, then that someone can pass it to $A$ (in exactly one way).  Hence there are $b_{1,3} = 6 = b_{2,2} + b_{3,2} + b_{4,2}$ ways to get the ball to $A$ in three passes.  On the other hand, $b_{2,3} = 7 = b_{1,2} + b_{3,2} + b_{4,2}$.
It should be not too difficult to write a general formula for $b_{i,n+1}$ at this point.  This formula will give you the recurrence, which is conveniently written in matrix form.
For the solution, there's more than one method.  Which one(s) have you seen?
A: Ross Millikan set up the recursion, so here we find the solution using a recursively defined function in Python:
def PassBall(m):
    if m == 0:
        return {'f':1, 'g':0}
    else:
        r = PassBall(m-1)
        return {'f':r['g'] ,'g':3*r['f'] + 2 * r['g']}

for n in range(0,8):
    print (n, PassBall(n))

Output:
0 {'f': 1, 'g': 0}
1 {'f': 0, 'g': 3}
2 {'f': 3, 'g': 6}
3 {'f': 6, 'g': 21}
4 {'f': 21, 'g': 60}
5 {'f': 60, 'g': 183}
6 {'f': 183, 'g': 546}
7 {'f': 546, 'g': 1641}

