Let $\mathbf{X}$ be a Markov chain on a square find $p_{1,1}(n)$ Consider a square like this
$$\begin{array}\\
1 & - & 2\\
| &   & |\\
3 & - & 4
\end{array} $$
such that you can go from each state with chance $\tfrac{1}{2}$ to the neighbouring states. So we have the following transition matrix 
$$P = \begin{pmatrix}0 & \tfrac{1}{2} & \tfrac{1}{2}& 0\\
\tfrac{1}{2} & 0 & 0 & \tfrac{1}{2}\\
\tfrac{1}{2}&0 & 0 & \tfrac{1}{2}\\
0 & \tfrac{1}{2} & \tfrac{1}{2}& 0 \end{pmatrix}. $$
Let $p_{i,j}(n)$ be the position $(i,j)$ in the matrix $P^n$. I want to find $p_{1,1}(n)$. 
This is my approach:


*

*Diagonalize P, the eigevalues of $P$ are $-1,1,0,0$ therefore $P = U D U^{-1} $ where 
$$D = \begin{pmatrix}1 & 0 & 0 & 0\\
0 & -1 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\ \end{pmatrix} $$
Thus $P^n = U D^n U^{-1}$.

*We know that $p_{1,1}(0) = 1$ and $p_{1,1}(1) = 0$


I would say that $p_{1,1}(n) = A + (-1)^n B$ for $A,B \in \mathbb{R}$. But this is obviously not true because $A = B = \tfrac{1}{2}$ and therefore
$$p_{1,1}(2) = \frac{1}{2} + \frac{1}{2} = 1. $$ 
This is not possible.
I intuitively see that there is symmetry, you can't go back to your start position in odd steps. But I want to make this more formal with linear algebra. I don't see why 
$$p_{1,1}(n) = \frac{1}{2}A + \frac{1}{2}(-1)^n B = \frac{1}{2} + \frac{1}{2}(-1)^n. $$
I guess this is true because two eigenvalues are zero. But I haven't found something that states this.

The mistake is in the equation $p_{1,1}(n)=A+(-1)^nB$. Instead, it should be $A+(-1)^nB+0^nC$, where $0^n$ is defined to be $1$ if $n=0$ and $0$ for integers $n>0$.
EDIT: By the way, this equation is derived as follows:
\begin{align*}
p_{1,1}(n)&=e_1^TP^ne_1 \\
&= e_1^TUD^nU^{-1}e_1\\
&= e_1^TU\begin{pmatrix}1^n & 0 & 0 & 0 \\ 0 & (-1)^n & 0 & 0 \\ 0 & 0 & 0^n & 0 \\ 0 & 0 & 0 & 0^n\end{pmatrix}U^{-1}e_1
\end{align*}
where $e_1=(1,0,0,0)^T$. Then, since $e_1$ and $U$ are constant (i.e., not depending on $n$), expanding this out gives an equation of the form $p_{1,1}(n)=A+(-1)^nB+0^nC$.
