Tetrahedral paths

Let $a_n$ be the number of paths of length $n$ from $O$ to $O$ and let $b_n$ be the number of paths from $O$ to any of the other vertices, say $A$ . We have $a_1=0$ and $b_1=1$ and the recursions $a_{n+1}=3b_n$ and $b_{n+1}=a_n+2b_n$ . A quick computation shows that $a_5=\boxed{60}$ .

The induction/recursion methods presented in other solutions are certainly the neatest and most informative way to go for general $n$ . However, this case is small enough to count.

The path can return to $O$ either once (just at the end) or twice. $p,q,r,s$ below stand for any of the points $A,B,C$ .

Suppose you want to make a path of length $n$ , the penultimate move (the move right before the last move) can either be a move from O to {A, B or C}, or a move from {A, B or C} to another from that same list. It cannot be a move straight to O, since any move made for the next move will leave the path's end somewhere other than O.

Supposing there is a given path of length $n-1$ , there can be made a path of length $n$ if you remove the last move in the $n-1$ sequence, you will have a path that starts on O and ends on some vertex other than O. You instead replace that move with a move from to any of the other 2 vertices from {A, B or C} (since you cannot move to the same location) and the last move is obviously to go straight to O.

Supposing there is given instead a path of length $n-2$ , you can simply append a move to any of the three other vertices {A, B or C} and straight back to O. The penultimate move in this case is a move from O to {A, B or C}.

Since in these cases, the penultimate move is different, the paths formed by these strategies will be different from each other, but the paths formed by these strategies are complete, meaning they cover every possible path of length $n$ . Thus we have a single recurrence relation for $p_n$ , the amount of paths of length n, $p_n = 2p_{n-1} + 3p_{n-2}$ .

Using the initial solution $p_2=3$ (or alternatively $p_1=0$ or $p_0=1$ , you can use this to find out that $p_3 = 6$ , $p_4 = 21$ , $p_5 = 60$ Now, the general solution to this recurrence relation is

$p_n = \frac{3(-1)^n+3^n}{4}$ .

Derivation or confirmation of this solution is left as an exercise to the reader (see the linear recurrence relations wiki , or just plug the formula into the recurrence relation, and confirm the initial value). Using this formula, you can go directly to the solution, or you can solve for an arbitrary path length.

Some interesting things to note: you can see that $3(-1)^n+3^n$ should always have a factor of 4, otherwise the $n$ 'th term would not be an integer. A side problem then could be to prove this very fact without using the recurrence relation

Write the adjacency matrix for this graph, and raise it to the fifth power, we can see the number of paths from O to O of length 5 from the corresponding entry of the matrix.