Recurrence relation paths traced on a tetrahedron

Question

I am attempting a recurrence relation question in which the number of possible length $n$ paths $a_n$ is being calculated. A path is defined as a traversal along a tetrahedron between connected vertices. All valid paths must return to the original vertex at the end of the path. The example given labels the vertices $ABCD$ and shows that the value of $a_2$ is $3$ - $ABA$, $ACA$ and $ADA$ are the only valid paths.

The question is what is the formula that defines this recurrence relation? The answer stated is $a_n=2a_{n-1}+3a_{n-2}$ but I don't understand where the $2a_{n-1}$ comes from. The $3a_{n-2}$ term makes sense as one could traverse any length two path - $3$ of them - and then do a path of length $n-2$ and this would be a valid path of length $n$.

Answer 1

The $2 a_{n-1}$ term can be described by taking any path, which must start with $AX$ where $X \in \{B,C,D\}$. Now, which ever one $X$ is, there are two others $Y$ and $Z$, for example if $X=B$ then $Y=C$ and $Y=D$. So you can replace $AX$ with either $AYX$ or $AZX$, which gives $2 a_{n-1}$ new paths.

But there's still an issue. The reason why this method counts every length $n$ path exactly once is:

• If a path starts $AXA$ then it is counted in the $3 a_{n-2}$ term --- just remove the initial $AXA$;
• If it starts $AXY$ then it is counted in the $2 a_{n-1}$ term --- just replace the initial $AXY$ by $AY$.