The following exercise comes from the book Probability, Markov Chains, Queues, and Simulation.
Let $(X_n)_{n \ge 0}$ be a two-state Markov chain, whose transition probability matrix is given by $$ \begin{pmatrix} 1-p & p \\ q & 1-q \\ \end{pmatrix} $$ with $0 < p, q < 1$. Use the fact that ${P}^{n+1}={P}^n*P$ to show that $p_{11}^{(n+1)}=(1-p-q)p_{11}^{(n)}+q$.
I struggle with a few things. First of all, what is the exact difference between the powers ${(n+1)}$ and ${n+1}$ ? My assumption is that the former refers to transitioning to the other state, the latter is just putting to the power of $n + 1$, but the book does not mention it explicitly. If this is right, then is $p_{11}^{(n+1)}$ equal to $(1-p)^{(n+1)}$ ? What should be the next step? Thanks in advance.
As I have mentioned in my comment, in this case $p^{(n+1)}_{11}$ means the probability that the MC comes back to state $1$, starting from $1$, at its $n+1$th step.
Please consider
$$ \begin{pmatrix} p^{n+1}_{11} & p^{n+1}_{12} \\ p^{n+1}_{21} & p^{n+1}_{22} \\ \end{pmatrix} = \begin{pmatrix} p^{n}_{11} & p^{n}_{12} \\ p^{n}_{21} & p^{n}_{22} \\ \end{pmatrix} \begin{pmatrix} 1-p & p \\ q & 1-q \\ \end{pmatrix} $$
If you solve RHS of the equation, then
$p^{n+1}_{11} = p^{n}_{11}(1-p) + p^{n}_{12}q = p^{n}_{11}(1-p) + (1-p^{n}_{11})q =(1-p-q)p_{11}^{(n)}+q$.