Let$\left\{{X_{n}: n\in \mathbf{N}}\right\}$ be a Markov Chain in discrete time, with the hitting time being defined as $\displaystyle H^A=\inf\left\{{n\geq 0 : X_{n}\in A}\right\}$. Assuming $i\not \in A$, how do I prove that $\mathbf{E}\left(H^A|X_1=j;X_0=i\right)= 1 + \mathbf{E}\left(H^A|X_0=j\right) $ ?
Intuitively I understand why it is so.
I think I understand your confusion
$E(H^A|X_1=i,X_j=0) = E(H^A1_{\{H_A\geq 1\}}|X_1=j) = E(1+\tilde{H}^A|X_1=j)= 1+E(H^A|X_1=j)$
where $\tilde{H}^A$ is an independent copy of $H^A$.
The confusion comes from the notation. I do not like the notation you use. I think things are much clearer if you use the notaiton
$E_i$ to mean $E(.. |X_0=i)$. The difference is the following. In the latter, everything live on 1 probability space and $E_i$ for each $i$ in the sample space is a family of probability spaces. Markov property written in this form
$E_i(H^A\mathbb{1}_{\{H^A\geq 1\}}|X_1=j) = E_j(H^A\mathbb{1}_{\{H^A\geq 1\}}\circ\theta_1)=E_j((1+H^A\mathbb){1}_{\{H^A\geq 0\}})$
where $\theta_1$ is shifting time by 1. Hitting time under the operator behaves like $H^A\mathbb{1}_{\{H^A\geq 1\}}\circ\theta_1 =(1+H^A\mathbb){1}_{\{H^A\geq 0\}}$