I generally understand how to do this but I'm having trouble with a formal proof.
"Consider an $M/M/1/m+1$ queue with exponential arrivals rate $\lambda$, exponential service rate $\mu$, and finite waiting room capacity $m$.
Let $X_{n}$ be the number of customers in the system just after the $n$th departure. Show that $\{X_n; \: n \geq 0\}$ is a Markov Chain with state space $E = \{0,...,m\}$ and derive it's transition matrix $P$.
I understand the definition of a Markov Chain says that $$P\{X_n = x_{n} | X_{n-1} = x_{n-1}, .... X_{0} = x_{0}\} = P\{X_{n} = x_{n} | X_{n-1} = x_{n-1}\}$$ or that given the present, the future is independent of the past.
How can that be shown for this particular queue though? As far as showing the state space $E = \{0,...,m\}$ I can reason it out that there are only $m$ states that this chain can be in since there are only $m$ spots in the waiting room and therefore anyone else must leave, but again not sure how to formally prove it.
My thoughts are that since this is a birth-death process, the system can only increase by one, decrease by one, or remain the same. And the transition matrix would have rows with
$\mu_{i} - (\lambda_{i}+\mu_{i}) \lambda_i$ (besides the first and last rows)
Is this the correct way to proceed, or is this a different scenario since we are considering the number of customers in the system "just after the $n$th departure."