The adjacency matrix for is .

The third power is .

So it appears the your calculation for is two off.

If you square the matrix, you will see that you are correct for .

Suppose that denotes the number of paths of length n from a vertex to itself. Clearly because each point is adjacent to three other vertices. Here is an example: ABA, ACA, & ADA.

Suppose that denotes the number of paths of length n between two vertices.

Consider the two vertices D & B in the graph. If we want to know the number of paths of length (n+1) from D to B, then we must go through vertex A or C. So we can use any one of the paths from D to A of length n and add AB to any one. We have the same idea using vertex C. But we can also go directly to B from D by using any path from D to D of length n.

Thus we get

Now we need to find in terms of .

Any path from D to D of length n has the last edge AD, BD, or CD.

So count the number of the number of paths of length n-1 between two vertices.

Thus we have or .