Consider a $\xi_n$ be a Markov chain. With $\mathbb{P}(\xi_{n+1} = k+1| \xi_n = k) = p$ and $\mathbb{P}(\xi_n = k| \xi_{n-1} = k) = 1 - p$. Let $\tau_{k} = \min\{n : \xi_n = k\}$.
We need to prove that $\tau_k$ is Markov's chain.
I've thought that $\mathbb{P}(\tau_{n} = m_{n}|\tau_{n-1} = m_{n-1}, \tau_{k_1} = m_{k_1} \dots \tau_{k_l} = m_{k_l}) = p(1-p)^{m_{k_l} - 1}\cdot p (1-p)^{m_{k_{l+1}} - m_{k_{l}} - 1} \cdot \dots \cdot p(1-p)^{m_{n}-m_{n-1}-1} = p^{k}(1-p)^{m_n - m_{n-1}-1}$.
But firstly I used independence of $\tau_k$ and there is occur parameter $k$.
Where is my fault?
First of all, the property you need to verify for a Markov chain is $$ P(\tau_n=m_n|\tau_{n-1}=m_{n-1},\tau_{n-2}=m_{n-2},\dots,\tau_1=m_1)=P(\tau_n=m_n|\tau_{n-1}=m_{n-1})\tag1\label1 $$ The LHS is given by $$ \frac{P(\tau_n=m_n,\tau_{n-1}=m_{n-1},\tau_{n-2}=m_{n-2},\dots,\tau_1=m_1)}{P(\tau_{n-1}=m_{n-1},\tau_{n-2}=m_{n-2},\dots,\tau_1=m_1)} $$ To find the numerator, note that the event occurs if and only if we have $$ \xi_1=\xi_2=\dots=\xi_{m_1-1}=0,\\ \xi_{m_1}=\xi_{m_1+1}=\dots=\xi_{m_2-1}=1,\\ \vdots\\ \xi_{m_{n-1}}=\xi_{m_{n-1}+1}=\dots =\xi_{m_n-1}=n-1,\\ \xi_{m_n}=n. $$ Using the given transition probabilities for the $\xi$ Markox chain, the probability of the numerator is $$ (1-p)^{m_1-1}p(1-p)^{m_2-m_1-1}p\cdots (1-p)^{m_n-m_{n-1}-1}p=(1-p)^{m_n}\cdot (p/(1-p))^n $$ Similarly, the denominator is $(1-p)^{m_{n-1}}\cdot (p/(1-p))^{{n-1}}$. Dividing, we get that the LHS of $\eqref1$ is $$ (1-p)^{m_n-m_{n-1}-1}p\label2\tag2 $$ For the RHS, we need $$ \frac{P(\tau_n=m_{n},\tau_{n-1}=m_{n-1})}{P(\tau_{n-1}=m_{n-1})} $$ This is the hard part. Let's start with $P(\tau_{n-1}=m_{n-1})$. There are $m_{n-1}$ increments of the form $\xi_k\to \xi_{k+1}$ for $k=0,1,2,\dots,m_{n-1}-1$. Among the first $m_{n-1}-1$ increments, we must choose $n-2$ of these to be increases, where $\xi_{k+1}=\xi_k+1$. Then, the last increase must be from $\xi_{m_{n-1}-1}$ to $\xi_{m_{n-1}}$. There are $\binom{m_{n-1}-1}{n-2}$ ways to do this. Each of these paths has probability $(1-p)^{m_{n-1}-n-1}p^{n-1}$. Therefore, $$ P(\tau_{n-1}=m_{n-1})=\binom{m_{n-1}-1}{n-2}(1-p)^{m_{n-1}-n-1}p^{n-1}\tag3\label3 $$ For the numerator, we count paths whose first $m_{n-1}-1$ steps have $n-2$ increases, followed by an increase, then $m_n-m_{n-1}-1$ non-increases, then an increase. Therefore, $$ P(\tau_{n-1}=m_{n-1}\cap \tau_n=m_n)=\binom{m_{n-1}-1}{n-2}(1-p)^{m_{n-1}-n-1}p^{n-1}(1-p)^{m_n-m_{n-1}-1}p\tag4\label4 $$ Dividing $\eqref 3$ by $\eqref 4$, the result is exactly $\eqref 2$.