Tetrahedron hopping

Let $N_{AB}(n)$ be the number of ways to go from one vertex to a different one in $n$ moves.

Let $N_{AA}(n)$ be the number of ways to go from one vertex to the same one in $n$ moves.

Then, clearly $N_{AB}(1) = 1$ and $N_{AA}(1) = 0$

Also, for $n>1$ , $N_{AB}(n) =N_{AB}(n-1)+2*N_{AA}(n-1)$ and $N_{AA}(n) = 3*N_{AB}(n-1)$

From this, it follows (proof left as an exercise to the reader! ;) ) that for odd $n$ , $N_{AA}(n) = (3^n-3)/4$ , and for even $n$ , $N_{AA}(n) = (3^n+3)/4$

Using these relations, we find that, $N_{AA}(17) = \boxed{32285040}$

A general procedure:

Note that we can construct an adjacency matrix $A$ corresponding to the graph represented by the tetrahedron, where $A_{ij}=1$ if $i\ne j$ and there is an edge between them; $A_{ij}=0$ , else. So the adjacency matrix for the tetrahedron is the following $A=\begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}$ Claim:The $(i,j)$ th entry of $A^n$ , gives the number of $n$ length paths from $i$ to $j$ in the graph corresponding to $A$ .

Proof Clearly the claim is true for $n=1$ . Let it be true for $n=k, k\ge 1$ . Now, note that $A^{k+1}_{ij}=\sum_{l}A^k{il}A_{lj}$ . Now, note that by induction hypothesis, $A^k_{il}A_{lj}$ denotes the total number of $k+1$ length paths from $i$ to $j$ , by first going from $i$ to $l$ in $k$ steps and then going from $l$ to $j$ in one step. Thus, $A^{k+1}_{ij}$ gives all possible $k+1$ length paths from $i$ to $j$ . Thus the claim is proved. $\blacksquare$

It is now clear that in our case, we need to find a diagonal element of $A^{17}$ . To do that, first observe that one can write, $A=11^T-I$ , where $1=[1\ 1\ 1\ 1]$ is the all $1$ vector, and $I$ is the $4\times 4$ identity matrix. Since, $A$ is symmetric, $A$ admits a unique diagonalization, i.e. $A$ can be written uniquely as $A=V\Lambda V^T$ , where $\Lambda$ is a diagonal matrix with the diagonal consisting of eigenvalues of $A$ , and $V$ is an orthonormal matrix with a set of eigenvectors of $A$ as its columns.

For our case, it is easy to check that $11^T$ has one eigenvalue $4$ , and others $0$ , so the eigenvalue matrix of $A$ is $\Lambda-I$ , where $\Lambda=\begin{pmatrix} 4 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$ The orthonormal eigenvector corresponding to eigenvalue $3$ of $11^T$ is also easy to see to be $1/2$ times the vector $1$ . Now, because of orthonormality of $V$ , we see that $A^2=(V(\Lambda-I)V^T)^2=V(\Lambda-I)V^TV(\Lambda-I)V^T=V(\Lambda-I)^2V^T,\cdots\ A^n=V(\Lambda-I)^n V^T$ Thus, writing the columns of $V$ as $e_1,e_2,e_3,e_4$ , corresponding to the eigenvalues of $4,0,0,0$ , we get $A^n=3^ne_1e_1^T+(-1)^n (\sum_{k=2}^4 e_ke_k^T)\\=3^ne_1e_1^T+(-1)^n(\sum_{k=1}^4 e_ke_k^T-e_1e_1^T)\\=3^ne_1e_1^T+(-1)^n(VV^T-e_1e_1^T)\\=(3^n-(-1)^n)e_1e_1^T+(-1)^n I\\=\frac{(3^n-(-1)^n)}{4} 11^T+(-1)^n I$ Thus, for $n=17$ , any diagonal element is $(3^{17}+1)/4-1=\boxed{32285040}$ .