I am given a transition matrix for the markov chain on the space state $X=\{1,2\}$ $P=\begin{pmatrix} 1-a & a\\ b & 1-b \end{pmatrix}$ We are asked to find $P^n$ as a hint I am told to notice that: \begin{equation}p_n=P^n(1,1)=\mathbb{P}(X_n=1|X_0=1)\end{equation} and use recursion $$p_n=p_{n-1}(1-a)+(1-p_{n-1})b$$ So I understood that first hint is just form me to really see what am I calculating and that I have to do the same for (1,2), (2,1), (2,2) as well. And second is just total probability formula, because $X_{n-1}=2$ with probability $1-p_{n-1}$ we "get to" $X_n=1$ with prob. $b$ similarly $X_{n-1}=1$ with probability $p_{n-1}$ and we "get to" $X_n=1$ with prob. $1-a$.
I know how to solve this diagonalizing P, but I cannot do this the way they want me to i.e. solve the recursion. I tried to guess the formula and proved it inductively and I ended up with some ugly summation not worth quoting here, and failed proving inductively that it is right.
So the question is how to solve this recursion?
Informally, we have
\begin{align*} p_n &= p_{n - 1} (1 - a - b) + b \\ &= [p_{n - 2} (1 - a - b) + b] (1 - a - b) + b = p_{n - 2} (1 - a - b)^2 + b \sum_{k = 0}^1 (1 - a - b)^k \\ &\vdots \\ &= p_0 (1 - a - b)^n + b \sum_{k = 0}^{n - 1} (1 - a - b)^k \\ &= (1 - a - b)^n + b \left(\frac{1 - (1 - a - b)^n}{1 - (1 - a - b)} \right) \\ &= (1 - a - b)^n + \frac{b}{a + b} (1 - (1 - a - b)^n) \\ &= \frac{a (1 - a - b)^n + b}{a + b}. \end{align*}