a) Write down the adjacency matrix, F.

This part I can do. (Using the convention that loops count as 1 edge)

$\displaystyle F = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}$

The ordering of the vertices are $\displaystyle v_1, v_2, v_3, v_4$ for both rows and columns.

b) Explain why the number of paths of length $\displaystyle 2^n$ which begin and end at $\displaystyle v_1$ is always one more than the number of walks of length $\displaystyle 2^n$ which begin at $\displaystyle v_1$ and end at $\displaystyle v_2$.

I'm stuck on this part.

This is what I have done so far:

So I have computed $\displaystyle F^2 = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix}

$

And I have also computed $\displaystyle F^4 = \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix} \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix} = \begin{bmatrix} 21 & 20 & 20 & 20 \\ 20 & 21 & 20 & 20 \\ 20 & 20 & 21 & 20 \\ 20 & 20 & 20 & 21 \end{bmatrix}

$

Now we can see the that entry in $\displaystyle (v_1, v_1)$ is always 1 more than the entry in $\displaystyle (v_1, v_2) $

But how do I generalise this for all $\displaystyle F^{2^n}$?

Thanks!