Q: Markov chain probability with formula 1-p-q Consider $(\theta^{(n)}: n\ge 0)$, a markov chain in S={0, 1} with initial distribution $\pi^{(0)}=(\pi^{(0)}(0), \pi^{(0)}(1))$ and transition matrix P given by $P=\begin{pmatrix}1-p&p\\q&1-q\end{pmatrix}$. Using the relation $P(\theta^{(n)}=0)=\sum_{j\in S}P(\theta^{(n)}=0, \theta^{(n-1)}=j)$ for $n\ge 1$ and the Markovian property of the chain,
$$\begin{split}P(\theta^{(n)}=0) &= (1-p)P(\theta^{(n-1)}=0)+qP(\theta^{(n-1)}=1)\\
 &= (1-p-q)^n \pi^{(0)}(0) + q\sum_{k=0}^{n-1}(1-p-q)^k\end{split}$$
Been thinking about how they got the second step for a few days, but still stumped. Why's there $1-p-q$
I thought about

*

*going from the first expression to the second expression, in which case I could figure no substitution to connect the two


*how the second equation may make sense standalone, which I still had no success due to not knowing why there is 1-p-q
I found a formula, but it didn't help much: $P(\theta^{(n)}=y)=\sum_{x\in S}P^n(x, y)\pi^{(0)}(x)$

A: I guess they are proving by induction that
$$
\begin{split}P(\theta^{(n)}=0) = (1-p-q)^n \pi^{(0)}(0) + q\sum_{k=0}^{n-1}(1-p-q)^k\end{split}.
$$
In the second step they use the inductive assumption, namely the above formula for $n-1$. And it simplifies to the formula for $n$ and the proof is done. Notice that $P(\theta^{(n-1)}=1) = 1 - P(\theta^{(n-1)}=0)$.
$$P(\theta^{(n)}=0)
= (1-p)P(\theta^{(n-1)}=0)+qP(\theta^{(n-1)}=1) \\
= (1-p)P(\theta^{(n-1)}=0)+q\left(1-P(\theta^{(n-1)}=0)\right) \\
= (1-p-q)P(\theta^{(n-1)}=0) + q \\
= (1-p-q) \left(  (1-p-q)^{n-1} \pi^{(0)}(0) + q\sum_{k=0}^{n-2}(1-p-q)^k \right) + q\\
= (1-p-q)^{n} \pi^{(0)}(0) + \left(q\sum_{k=0}^{n-2}(1-p-q)^{k+1}\right) + q \\
= (1-p-q)^{n} \pi^{(0)}(0) + q\left(1+\sum_{k=1}^{n-1}(1-p-q)^{k}\right) \\
= (1-p-q)^{n} \pi^{(0)}(0) + q\sum_{k=0}^{n-1}(1-p-q)^{k}. 
$$
