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 .