So I've been struggling for two days in proving this:
Let $X_n$ be a both time and space state discrete markov chain and let's define $\tau_j(k)$ as follows: \begin{equation} \tau_j(k)=\min\left[n>\tau_j(k-1)\right|X_n=j]. \end{equation} I want to prove that the following is true: \begin{equation} P[\tau_j(k)<\infty|\tau_j(k-1)<\infty,X_0=i]=P[\tau_j(1)<\infty|X_0=j]. \end{equation}
$$P(\tau_j(k) < \infty | \tau_j(k-1) < \infty, X_0 = i)\\ = \sum_{l = 1}^\infty P(\tau_j(k) < \infty | \tau_j(k-1) = l, X_0 = i)P(\tau_j(k-1) = l | \tau_j(k-1) < \infty) \\ = \sum_{l = 1}^\infty P(t_j(k) < \infty | X_l = j,\tau_j(k-1) = l)P(\tau_j(k-1) = l | \tau_j(k-1) < \infty) \\ = \sum_{l = 1}^\infty P(t_j(1) | X_0 = j)P(\tau_j(k-1) = l | \tau_j(k-1) < \infty) \\ = P(t_j(1) | X_0 = j) \sum_{l = 1}^\infty P(\tau_j(k-1) = l | \tau_j(k-1) < \infty) \\ = P(t_j(1) | X_0 = j) $$
Where the second equality is by Markov property, third by time homogeneity and the last by the fact that the decomposition of the event $\tau_j(k-1) < \infty$ must sum to unity.